C++向量指针问题

我正在尝试使用C++实现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]);

显然存在不确定的行为怎么回事，但我不能设法看到。有人请告诉我，我对指针缺乏理解的地方会破坏这段代码，为什么？

来源

2010-10-11 Jesse Emond

所以，你在这里的第一个问题是，您使用的载体之一的各个节点的地址。但是，随着时间的推移，当您向矢量添加更多节点对象时，这些指针可能会失效，因为矢量可能会移动节点。

（矢量从某个预先分配的大小开始，当你填充它时，它会分配一个新的，更大的存储区域并将所有元素移动到新的位置。我打赌你的情况下，只要你的第二个节点添加到节点，它是这样做的举动。）

是否有一个原因，为什么你不能存储索引，而不是原始指针？

来源

2010-10-11 20:37:59

哇，我从来没有想过使用索引而不是指针，我一定会尝试一下，因为“节点”向量将永远不会删除元素。 – 2010-10-11 20:42:55

的一个问题是的push_back可以强制向量的重新分配，即，它造成较大的内存块中，将所有存在的元素到该较大的块，然后删除旧的块。这会使向量中的元素无效。

来源

2010-10-11 20:37:46

的问题是，每次添加到载体时，它可能需要扩大其内部存储器。如果是这样，它分配一个新件的存储，拷贝所做的一切，并删除旧的，无效迭代器和指针其所有的对象。

至于解决你的问题，你可以通过预留足够的空间，无论是前期

避免重新分配（nodes.reserve(42)）

转nodes成std::list（不失效迭代器或指向不直接受变化影响的元素的指针）

商店索引而不是指针。

除了你的问题，但仍然值得一提：

标识符的合法使用开始下划线是相当有限的。你的是合法的，但如果你不知道确切的规则，你可能想避免使用它们。

您的比较运算符不会告诉它不会更改其左边的参数。另外，运营商平等对待他们的操作数（即不修改它们，而不是像+=）通常最好作为自由函数来实现，而不是作为成员函数来实现。

来源

2010-10-11 20:38:35 sbi

感谢您的答案！为什么我需要一个对象和一个指针在我的真实代码中，我有一个封闭的和一个开放的列表，保存信息关于已经考虑的节点和要考虑的节点。所以，我首先将一个节点添加到打开列表中，并且在考虑时将其从打开的列表中删除并将其放入关闭列表中。所以我添加了一个名为map的矢量，用于保存节点对象。打开和关闭的列表只保留指向地图向量内的对象的指针。你有什么想法，我怎么能以更好的方式实现这一点？ – 2010-10-11 20:48:11

@Jesse：我添加了一些想法。 – sbi 2010-10-11 20:55:33

你的代码对我来说看起来不错，但请记住，当节点超出范围时，列表将变为无效。

来源

2010-10-11 20:45:25

只是增加了现有的答案;代替原始指针，考虑使用某种形式的智能指针，例如，如果boost可用，请考虑shared_ptr。

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

和

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

因此，你只需要创建节点的一个实例，它是“托管”给你的。在Node类中，你可以选择父类的shared_ptr（如果你想确保父节点不会被清除，直到所有的子节点都被删除，或者你可以创建一个weak_ptr。

使用共享指针还可以帮助缓解您希望在多个容器中存储“句柄”的问题（即，您不一定需要担心所有权 - 只要所有引用都被删除，则该对象将被清除）

来源

2010-10-11 21:36:34 Nim

C++向量指针问题

回答

相关问题