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

Question

В настоящее время я действительно застрял в том, как решить следующую проблему:

struct node {
    int a;
    node* b;
}

У меня будет два корневых узла без родителей, а затем еще несколько узлов, указывающих на их родителей

vector<node> IholdAllTheNodes;

node noparent1; <--- these get returned from a method
node noparent2;

IholdAllTheNodes.pushback(noparent1);
IholdAllTheNodes.pushback(noparent2);

node withparent1; <---- i am happily points to noparent1
node withparent2; <-----i am happily points to noparent2

Никаких проблем, все работает потрясающе

IholdAllTheNodes.pushback(withparent1) <<<< oops this causes all the pointers to move.

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

Мой вопрос заключается в том, как просто добавить больше узлов в мой вектор узлов, не перемещая указатели исходных узлов. (Я не могу получить фиксированный размер для вектора)

если у кого-то есть время, чтобы объяснить, почему, несмотря на добавление pushback в конец списка векторов, местоположение предыдущей информации меняется?

Answer 1

Вы можете позвонить резерв

IholdAllTheNodes.reserve(MAX_SIZE);

заранее, чтобы избежать перераспределения. Это требует, чтобы вы знали MAX_SIZE заранее.

В качестве альтернативы,

• предлагается : сделать его контейнером для указателей
• сделать его std::vector<shared_ptr<node> > (похожим, но менее эффективным)
• сделать его std::vector<node*> (похожим, но утомительным и подверженным ошибкам) ​​
• предлагается : избегайте указателей, если можете. Адресация узлов по индексу size_t ( integer ) в IholdAllTheNodes вместо

Answer 2

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

Как и предлагалось в других ответах, используйте любые указатели для хранения ваших узлов в векторе.Я бы порекомендовал boost::ptr_vector<node> или std::vector<boost::shared_ptr<node> >

РЕДАКТИРОВАТЬ:

Просто не согласен с reserve рекомендациями:

Это опасно.Вы должны поместить большие жирные предупреждения во все возможные места, чтобы люди, которые будут изменять этот код в будущем, не могли его пропустить.Потому что, когда вы добавите более MAX_SIZE элементов к вашему вектору, ваш космический корабль сгорит на Солнце.В этом случае я бы рекомендовал использовать boost::array, поскольку он имеет фиксированный размер (что делает ваше предположение более очевидным) и перехватывает переполнение буфера по крайней мере в сборках отладки

Answer 3

Позвоните IholdAllTheNodes.reserve() с определенным размером, и это гарантирует, что дальнейшие вставки не сделают недействительными указатели, пока не будет достигнута такая зарезервированная сумма.