Вставляет ли элемент в вектор повреждение указателя на вектор?

Question

В программе для моделирования логических вентилей Я переключился с использованием массивов

node N[1000]; 

векторам

vector<node> N; 

И моя программа действительно работал совершенно перед использованием векторов, но теперь печатаемых неправильные результаты, поэтому я попытался отладки и я узнал, что ошибка происходит здесь:

node* Simulator::FindNode(string h) 
{ 
    int i; 
    for(i = 0; i < NNodes; i++) 
    { 
     if (N[i].getname() == h) 
     { 
      return &N[i]; 
     } 
    } 

    node n ; 
    N.push_back(n); 
    N[NNodes].setname(h); 
    NNodes++; 
    return &N[NNodes-1]; //why?because of NNodes++ 
} 

// ... 

node* inp1; 
node* inp2; 
node* out; 
string NodeName; 

inp_file >> NodeName; 
inp1 = FindNode(NodeName); 
s1 = inp1; 

inp_file >> NodeName; 
inp2 = FindNode(NodeName); //inp1 is destroyed here 

inp_file >> NodeName; 
out = FindNode(NodeName); //inp2 and inp1 are destroyed here 

При вызове FindNode на 1-й раз, 1-й указатель I np1 указывает на нужное место, которое равно &N[0].

При вызове FindNode второй раз указатель inp1 указывает на мусор, а второй указатель inp2 указывает на нужное место &N[1].

При звонке FindNode в третий раз оба 1-го и 2-го указателей (inp1, inp2) указывают на мусор! И третий указатель указывает на нужное место.

Зачем это произошло?
Как работает вектор, когда я вставляю в него элементы и какие указатели следует использовать для указания объектов векторов?

Answer 1

Несколько вещей.

Прежде всего, насколько я могу судить NNodes просто отслеживает размер. Но для этого у вас есть std::vector::size(). Затем вы используете его, чтобы получить последний вставленный элемент, но вы можете просто использовать std::vector::back() для этого: return &N.back();.

Также ваш параметр передается по значению, когда он, вероятно, должен быть передан посредством const-reference: const string& h. Это позволяет избежать ненужных копий, и вообще * вы должны передавать вещи с помощью ссылки на const, а не по значению.

И это плохо:

node n; 
N.push_back(n); 
N[NNodes].setname(h); 

node, вероятно, следует иметь конструктор, который принимает const string& и устанавливает имя во время инициализации. Таким образом, вы никогда не может иметь узел без имени, например:

node n(h); 
N.push_back(n); 

Или более лаконична:

N.push_back(node(h)); 

Намного лучше.

Во-вторых, да, vector может аннулировать указатели на элементы; а именно, когда необходимо увеличить пропускную способность вектора. Если вы можете, reserve() вместимость вверх, чтобы избежать перераспределения. В вашем случае вы не можете, так что вы можете пройти два разных маршрута.

Первый маршрут: a level of indirection. Вместо того, чтобы прямо указывать на вещи, введите их индекс в массив. Обратите внимание, что, хотя их адрес может измениться, их местоположение внутри вектора не будет. У вас было бы Simulator::FindNode возвращение size_t и возврат N.size() - 1. Добавьте участника, как node& GetNode(size_t index), который просто делает return N[index]; (будет проверка ошибок, если вы пожелаете). Теперь, когда вам нужен член, передайте индекс этому члену GetNode, и вы получите ссылку на этот узел назад.

Другой маршрут - изменить ваш контейнер. Например, вы можете использовать deque. Это не имеет непрерывного хранения, но это очень похоже на vector. push_back и pop_back все еще O (1), и он по-прежнему обладает хорошей кэш-связностью. (И, кстати, deque торгует смежное хранение способности к push_front и pop_front в O (1) время, а)

Важно то, что deque будет не ТЕРЯЮТСЯ указатели во время толчка или попа-операции из любых конец.Он работает с гибридом векторных списков, где вы получаете куски хранения для связанных друг с другом элементов. Измените основное хранилище на deque (и не принимайте и не помещайте что-либо посередине), и вы можете указать на все просто.

Однако, из того, что я могу сказать, у вас ужасно неэффективная карта. Вы сопоставляете имена с узлами. Вероятно, вы должны просто использовать std::map, который имеет точный интерфейс, который вы пытаетесь воссоздать. Вы даже можете указать на любой элемент на карте, который никогда не делает ничего недействительным.

_{* Правило, проходят по константной-ссылки, если тип не является примитивной (встроенный как int, double и т.д.), если размер типа меньше sizeof(void*), или если вы будете нуждаться его копия в любом случае.}

То есть, не делайте этого:

void foo(const std::string& s) 
{ 
    std::string ss(s); // make a copy, use copy 
} 

Но сделать это:

void foo(std::string s) // make a copy, use copy 
{ 
} 

Answer 2

Да, он может перераспределить весь буфер, что делает все указатели в старом местоположении недействительными.

Вы можете ограничить это путем предварительного распределения, но это действительно просто повышение производительности. Лучше использовать индексы вместо необработанных указателей.

Answer 3

Когда вектор растет, он перераспределяется, что фактически аннулирует все указатели на элементы вектора.

Если вы заранее знаете, сколько элементов у вас будет в векторе, вы можете использовать метод reserve() для предварительного выделения пространства.

Answer 4

Возвращение указателя на внутренний член STL, вероятно, не самая лучшая идея. Когда вы даете объект контейнеру STL, вы в основном отказываетесь от контроля над ним. Вы говорите, что STL может перемещать его, поскольку он считает нужным поддерживать обещания, которые дает вам контейнер. Возврат индекса, где расположен узел, - это лучшая идея, о которой упомянул Стивен Судит.

Как только вы получите индекс, вы можете создать функцию, которая возвращает копию содержимого интересующего вас узла. Таким образом, вы также поддерживаете инкапсуляцию данных контейнером STL, не позволяя кому-либо изменять его содержимое.

Answer 5

Да, вставки будут аннулировать старые указатели на векторные элементы при перераспределении. Если вы хотите сильно использовать стабильные указатели, вы можете переключиться с вектора на deque. Он предлагает очень похожий интерфейс с вектором и может расти без перераспределения и перемещения предыдущего содержимого путем выделения дополнительных фрагментов.

Цена, которую вы платите за использование дека вместо вектора, является еще одним уровнем косвенности при случайном доступе. В зависимости от вашего использования это может быть совершенно неуместным. Вы должны перебирать deque весь deque, если необходимо, используя итераторы. Это будет так же быстро, как итерация над вектором.

Прибыль: нулевые перераспределения!

Answer 6

Представьте, что вам нужно написать код на основе массива, чтобы он мог, возможно, изменить размер массива.

Представьте, как вы это сделаете.

Представьте, что произойдет с устаревшими указателями.

Внесите свой код, чтобы использовать индексы, а не указатели, или гарантировать, что перераспределение не произойдет, в зависимости от ситуации.