C++ вектор проблемы указателей

Question

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

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

Так скажем, у меня есть «узел» класс (не связанные с А *) реализован следующим образом:

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 х) и родитель (указатель на другой узел), используемый для навигации по узлам с родительскими указателями.

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

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 к вашему вектору, эти указатели могут стать недействительными, поскольку вектор может перемещать узлы.

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

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

Answer 2

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

Answer 3

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

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

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

---

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

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

Answer 4

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

Answer 5

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

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

и

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

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

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