代码之家 › 专栏 › 技术社区 › Jesse Emond

指针问题的C++矢量

pointers c++

Jesse Emond · 技术社区 · 15 年前

目前我正在尝试用C++实现A*路径查找算法。

我的指针有点问题。。。我通常想办法避免使用它们,但现在我想我必须使用它们。

所以假设我有一个“node”类(与*无关)实现如下:

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;
    }
};

现在,我想要一个节点列表,其中包含所有已经或正在考虑的节点。看起来是这样的:

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]);

显然有一些不明确的行为在发生,但我看不出在哪里。有人能告诉我,我对指针的不理解哪里破坏了这段代码,为什么?

5 回复 | 直到 15 年前

Andrew Shelansky 15 年前

所以,这里的第一个问题是,你使用的是向量中单个节点的地址。但是,随着时间的推移,当您向向量中添加更多的节点对象时,这些指针可能会变得无效,因为向量可能会移动节点。

(向量从预先分配的某个大小开始,当您填满它时,它会分配一个新的、更大的存储区域,并将所有元素移动到新位置。我敢打赌,在您的情况下,只要将第二个节点添加到节点,它就会执行此操作。)

Nathan Monteleone 15 年前

一个问题是,push-back可以强制重新分配向量,即创建一个较大的内存块,将所有现有元素复制到该较大的块,然后删除旧块。从而使指向向量中元素的任何指针失效。

sbi 15 年前

问题是,每次添加到向量时,可能需要 . 如果它这样做了,它会分配一个新的存储,复制所有内容,并删除旧的存储, 所有的目标。

作为解决问题的方法,你可以

通过保留避免重新分配 nodes.reserve(42) )
转 nodes std::list (它不会使迭代器或指向不受更改直接影响的元素的指针失效)
商店索引

除了你的问题,还值得一提:

以下划线开头的标识符的合法使用相当有限。你的是合法的,但如果你不知道确切的规则,你可能想避免使用它们。
你的比较运算符不会告诉你它不会改变它的左参数。此外,运算符对其操作数的处理是平等的(即不修改它们,与之相反,例如, += ),通常最好作为自由函数实现,而不是作为成员函数实现。

Nim 15 年前

只需添加到现有的答案中;不要使用原始指针,而是考虑使用某种形式的智能指针,例如,如果boost可用,则考虑使用shared-ptr。

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

和

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

因此,您只需要创建一个Node实例,它是为您“管理”的。在Node类中,您可以为父节点选择一个shared_ptr(如果要确保在移除所有子节点之前父节点不会被清理,或者可以将其设置为弱的_ptr)。

使用共享指针也有助于缓解在多个容器中存储“句柄”的问题(即。您不必担心所有权问题—只要删除所有引用,对象就会被清除)。

Alexander Rafferty 15 年前

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