С ++ вектор проблем с указателями

Question

В настоящее время я пытаюсь реализовать алгоритм поиска пути A * с использованием C ++.

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

Допустим, у меня есть класс "узла" (не связанный с A *), реализованный так:

class Node
{
public:
    int x;
    Node *parent;

    Node(int _x, Node *_parent)
        : x(_x), parent(_parent)
    { }

    bool operator==(const Node &rhs)
    {
        return x == rhs.x && parent == rhs.parent;
    }
};

У него есть значение (в данном случае int x) и родительский элемент (указатель на другой узел), используемый для навигации по узлам с указателями родителя.

Теперь я хочу иметь список узлов, который содержит все узлы, которые были или рассматриваются. Это будет выглядеть так:

std::vector<Node> nodes;

Мне нужен список, который содержит указатели, указывающие на узлы в списке узлов . Объявлено так:

std::vector<Node*> list;

Однако я определенно не правильно понимаю указатели, потому что мой код не будет работать. Вот код, о котором я говорю:

std::vector<Node> nodes;//nodes that have been considered
std::vector<Node*> list;//pointers to nodes insided the nodes list.

Node node1(1, NULL);//create a node with a x value of 1 and no parent
Node node2(2, &node1);//create a node with a x value of 2 and node1 being its parent

nodes.push_back(node1);
list.push_back(&nodes[0]);

//so far it works

//as soon as I add node2 to nodes, the pointer in "list" points to an object with
//strange data, with a x value of -17891602 and a parent 0xfeeefeee
nodes.push_back(node2);
list.push_back(&nodes[1]);

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

Answer 1

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

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

Есть ли причина, по которой вы не можете хранить индексы вместо необработанных указателей?

Answer 2

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

Answer 3

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

std::vector<boost::shared_ptr<Node> > nodes;

и

std::list<boost::shared_ptr<Node> > list;

Следовательно, вам нужно создать только один экземпляр Node, и он будет "управляемым" для вас.Внутри класса Node у вас есть опция shared_ptr для родителя (если вы хотите, чтобы родительский узел не очищался до тех пор, пока не будут удалены все дочерние узлы, или вы можете сделать это слабым_ptr.

Использование общих указателей также может помочь устранить проблемы, когда вы хотите хранить «дескрипторы» в нескольких контейнерах (т.е. вам не обязательно беспокоиться о владении - пока все ссылки удалены, объект будет очищен).

Answer 4

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

В качестве решения вашей проблемы вы можете либо

• избежать перераспределения, резервируя достаточно места заранее (nodes.reserve(42))
• превращает nodes в std::list (который не делает недействительными итераторы или указатели на элементы, на которые изменения напрямую не влияют)
• store индексы вместо указателей.

---

Помимо вашей проблемы, но все же стоит упомянуть:

• Легальное использование идентификаторов, начинающихся с подчеркивания, довольно ограничено.Ваши законны, но если вы не знаете точных правил, вы можете не использовать их.
• Ваш оператор сравнения не сообщает, что он не изменит свой левый аргумент.Кроме того, операторы, относящиеся к своим операндам одинаково (т.е. не изменяющие их, в отличие, скажем, +=), обычно лучше всего реализовывать как свободные функции, а не как функции-члены.

Answer 5

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