0

私はツリーを構築しており、Node2 つまたは 3 つの整数、ベクトル、およびポインターを含むクラスを持っています。ベクターは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));

最初のケースでは、インスタンス自体とは別に、への各ポインタに 4 ～ 8 バイトを余分に割り当てますA。

2 番目のケースでは、これらの 4 ～ 8 バイトが保存されますが、次のシナリオが構成されます。

  • a.v.push_back(A(&a))プッシュバック -- 動的に割り当てていると思います -- から構築されたインスタンスA(&a)。
  • ベクターはこれらの要素を押し戻しますが、一時的な制限に達すると、ベクターは再割り当てされ、移動される可能性があります。
  • Aベクトルを移動すると、A *_parentメンバーの各インスタンスの構築中に構築されたアドレスの関連付けが変更されます。

拘束:

  • 初期ベクトルの正確なサイズがわかりません。
  • ベクトルの再割り当てが発生するたびにリンクを再処理/再構築すると、余分な処理が必要になります。

質問:

これらの 2 つの制限を考慮して、このダングリング ポインターの問題を回避する方法はありますか? または、この問題に対するより良いアプローチはありますか?

4

2 に答える 2

0

push_backはオブジェクトのコピーを作成するため、ベクトルに指定したオブジェクトのアドレスはpush_backベクトルにとって意味がないことに注意してください。はい、ベクトル クラスは、記憶域に対してメモリが少なすぎる場合、メモリを再割り当てします。ツリーへの古典的なアプローチは、ポインターを格納することです。独自の種類のベクターを実装して手動で再割り当てし、それに応じてすべての子の親を変更できる場合があります。

はデータへのポインターも格納します。そうしないと、に含めることはstd::vectorできません。とにかく、これらの「ぶら下がっている」ポインターがあります（ぶら下がっているのではなく、私にとっては「冗長」です）。vector<A>A

また、メモリ内の実際のデータの移動には時間がかかり、メモリの断片化も増加する可能性があることに注意してください (冗長なポインターが気になる場合は、それが重要になるはずです)。

メモリが極端に制限されていない非組み込みシステム用にプログラミングしている場合は、明示的なポインターを使用する最初のアプローチを使用することをお勧めします。そうしないと、時間が失われます。通常時対記憶。

于 2013-03-15T20:16:55.193 に答える
0

オブジェクトをどうするつもりなのか、Aオブジェクトが比較的大きいかどうかはわかりません。たとえば、それらが (v別の のベクトル内に存在することによってA) 一緒にリンクできる場合、2 番目の選択は悪い考えです。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 に答える