С++: вектор указателя теряет ссылку после push_back()

В моем коде a есть глобальный вектор объекта Node и локальный вектор указателей Node:

#include<cstdio>
#include<cstdlib>
#include<vector>

using namespace std;

class Node {
    int n;

public:
    Node(int i) : n(i);
    int getN() { return n; }
};

vector<Node> v;

int main() {
    vector<Node*> p;
    v.push_back(Node(1));
    p.push_back(&v[0]);
    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

Я вставил объект Node в глобальный вектор и вставил указатель этого объекта в локальный вектор. Вывод моего кода выше:

first node id : 1

Однако, если я изменю свою основную функцию на это:

int main()
{
    vector<Node*> p;
    v.push_back(Node(1));
    p.push_back(&v[0]);
    v.push_back(Node(2));
    p.push_back(&v[1]);
    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

Код печатает значение мусора:

first node id : 32390176

Я не могу понять проблему. Изменяет ли структура данных vector ссылки каждого объекта после вставки? Как я могу это исправить?

Ответ 1

"Изменяет ли вектор ссылки после вставки?"

Возможно, да. std::vector может перераспределять его (кучу) хранилище при добавлении /push_back() дополнительных элементов, аннулируя все указатели:

Итератор [чтение: указатель] Недействительность

(для операций) push_back, emplace_back... Если вектор изменил емкость, все из них (т. все итераторы недействительны]. Если нет, то только end().

"Как я могу это исправить?"

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

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

Недействительность Iterator

Как правило, итераторы массива никогда не теряют силу на протяжении всего жизненного цикла массива.

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

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

_{PS. Если вектор имеет пользовательский распределитель, то все, что я написал, может быть неактуальным.}

Ответ 2

Что вы делаете, это поведение undefined для вашего вектора p, потому что вектор v может изменять, где хранятся его объекты.

A std::vector память смежна, поэтому после ряда push_backs она может выделять новую блочную память и копировать ее содержимое в новый блок. Это приведет к недействительности всех указателей, которые указывали на старую ячейку памяти.

Ответ 3

Да, a push_back() для вектора аннулирует все ссылки (и указатели) на элементы в этом векторе, если он должен перераспределять. Существует множество способов обойти это. Если вы знаете, что ваш вектор будет иметь определенное количество узлов, вы можете использовать reserve(). В вашем примере вы можете зарезервировать два элемента:

int main()
{
    v.reserve(2);
    .
    .
    .
}

Это гарантирует, что вектор предварительно выделил достаточное количество хранилища, чтобы он не перераспределялся.

Если вы не знаете размер раньше времени, вам придется что-то изменить в своем подходе. Вы можете использовать std::deque вместо std::vector, так как std::deque не отменяет ссылок при использовании push_back(). Вы можете хранить индексы вместо указателей. Или вам, возможно, понадобится нажать все узлы в вектор, прежде чем создавать указатели.

int main()
{
    v.push_back(Node(1));
    v.push_back(Node(2));

    vector<Node*> p;
    p.push_back(&v[0]);
    p.push_back(&v[1]);

    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

Ответ 4

Вы наткнулись на один из великих известных "темных углов" С++: великая "итерационная аннулирование". Определенно ознакомьтесь с этим:

Правила аннулирования Iterator

В частности, вы поражаете эту реальность:

vector: все итераторы и ссылки до точки вставки не подвержен влиянию, , если новый размер контейнера больше, чем предыдущий емкость (в этом случае все итераторы и ссылки недействительны)[23.2.4.3/1]

(акцент мой)

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