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++向量指針問題

回答

相關問題