0

我正在构建一棵树，并且我有一个Node包含两个或三个整数、一个向量和一个指针的类。向量存储Node实例，如下 - 命名Node为A：

class A {
public:
    A(A *parent) :
    _parent(parent) {
    }
    std::vector<INSTANCES_OF_A> v;
private:
    A *_parent;
};

我确实可以使用：

class A {
public:
    A(A *parent) :
    _parent(parent) {
    }
    std::vector<A *> v;
private:
    A *_parent;
};

// Insertion
A a;
a.v.push_back(new A(&a));

或者：

class A {
public:
    A(A *parent) :
    _parent(parent) {
    }
    std::vector<A> v;
private:
    A *_parent;
};

// Insertion
A a(NULL);
a.v.push_back(A(&a));

在第一种情况下，除了实例本身之外，我会为每个指向A.

在第二种情况下，这 4~8 个字节将被保存，但以下场景配置：

  • a.v.push_back(A(&a))推回-动态分配，我想-从A(&a);构建的实例
  • 向量将推回这些元素，但一旦达到临时限制，向量将被重新分配，它可能会被移动；
  • 移动向量会改变在构造每个成员实例期间建立的地址A关联A *_parent。

约束：

  • 我不知道初始向量的确切大小；
  • 每次发生矢量重新分配时重新处理/重建链接必然会产生过多的额外处理。

问题：

有没有办法解决这个悬空指针问题，尊重这两个限制？或者，有没有更好的方法来解决这个问题？

4

2 回答 2

0

我们不知道您打算如何处理您的A对象，以及它们是否相对较大。例如，如果它们可以链接在一起（通过存在于vanother 的向量中A），那么第二选择是一个坏主意。A如果您的班级包含多个成员，而且他们的内存非常饥饿，这也是一个坏主意。正如您所指出的，这可能会导致矢量调整大小移动大量数据。最重要的是，您的信息可能会因为具有A绝对相等成员的不同实例而变得多余。

我会通过存储指向您的A实例的指针或引用来采用第一种方法，但您必须注意范围。例如，不要添加如下指针：

void inSomeFunc(A& a)
{
    A b(NULL); // consider using nullptr if you can compile in C++11
    a.v.push_back(&b); // pushing the memory address of local variable 'b'
} // b goes out of scope, so the &b in a.v becomes invalid

在这种情况下，如果您尝试访问添加的元素，v最终可能会出现运行时错误。

也许就您的目标提供更准确的信息以获得更具体的答案。

编辑附加信息：

构建树（尤其是具有 n 个子节点）的常用方法是存储指向子节点的指针。如果你有一个静态树，也许你可以直接存储节点而不是指针（构建一次并且永远不会修改：只读）。而且，如果您有大量的孩子，它最终会为矢量调整大小做很多工作。

除了特定情况外，拥有一个常量树并不是那么有用，因此绝对好的方法是存储指向节点的指针。这使得对树的修改更快（您只需管理从向量中添加和删除指针）并且与管理对象一样简单。您唯一需要关心的是内存处理。您的节点必须在堆上分配并由析构函数释放或在您确定它们不会超出范围的地方声明为局部变量（不推荐）。

我会做这样的事情：

class A {
public:
    A(A *parent) :
    _parent(parent) {}

    /* This will recursively free all the nodes in your tree but BEWARE :
       it would probably not work if you have loops in your tree          */
    ~A()
    {
        for(int i = 0; i < v.size(); ++i)
            if(v[i] != NULL)
                delete v[i];
    }

    void addChild(A *node)
    {
        v.push_back(node);
    }

    A* addNewChild()
    {
        A* a = new A(this);
        addChild(a);
        return a;
    }

    // others accessors you need, for example operator[]

private:
    A *_parent;
    std::vector<A *> v;
};
于 2013-03-15T20:12:32.610 回答
0

请注意，它push_back会复制一个对象，因此您push_back编辑到向量的对象的地址对向量来说是没有意义的。是的，如果向量类的存储内存太少，它会重新分配内存。树的经典方法是存储指针。您可能会发现可以实现自己的向量，以便手动重新分配它，从而能够相应地更改所有孩子的父母。

存储指向数据的std::vector指针，否则不允许包含vector<A>在A. 所以你有这些“悬空”指针（它们不是悬空的，对我来说更“冗余”）。

另请注意，在内存中移动实际数据可能很耗时，并且还会增加内存碎片（如果您关心冗余指针，那么它对您来说一定很重要）。

如果您正在为内存不是非常有限的非嵌入式系统编程，我建议使用第一种方法，使用显式指针。否则你会浪费时间。正常时间与记忆。

于 2013-03-15T20:16:55.193 回答