0

わかりましたので、Graph クラスを作成しています。アルゴリズムを実行して、この夏の後半に空き時間があるときに GUI を追加できるようにしたいと考えています。現在、ベクトルの配列 (頂点ごとに 1 つ) として実装されている adjList があります。各ベクトルは、関連付けられた各頂点から他の頂点に向かうエッジを表すポインターのリストです。次のように、Graph クラスの保護されたメンバーとして宣言されます。

std::vector <Node*> *adjList;
adjList = new std::vector<Node*>[V];

補足質問があります。ここに、ポインターを保持するベクトルの配列 (ポインターを介して) があります。これが配列ではなく、ノード ポインターの単一ベクトルへのポインターである場合は、次のようにコンストラクターを呼び出すことができます。

adjList = new std::vector<Node*>(10);

これにより、ベクトル内の動的配列のデフォルト サイズを指定できますが、コンストラクターを呼び出すことができないか、少なくとも配列がある場合に正しい構文を取得できないようです。

今、私の主な関心事です。ポインター配列内のこれらの各ベクトルについて、addVertex メソッドで new 演算子を呼び出して、各ベクトルに多数のノード ポインターを追加します。ここで、これらすべての割り当て解除を正しく処理する必要があります。これが C++ でどのように機能するかについては理解していると思いますが、ポインターが扱いにくいことはわかっているので、このコード ベースに多くを追加する前に誰かに見てもらいたいと思いました。いくつかの検索で、私が持っているものとまったく同じものを見つけることができませんでした. ここに私の解放があります：

for(int i =0; i < V; i++)
    for (unsigned int j = 0; j < adjList[i].size(); j++)
        delete adjList[i][j];
delete adjList;

これですべてのメモリが解放されますか。また、これを確実に確認する簡単な方法はありますか。デバッグ中に new を使用して割り当てられたメモリ量をカウントするにはどうすればよいですか?

[編集: 詳細情報を追加して更新]

これは、擬似コードで指定された実装したいアルゴリズムの1つを示すGoogle Booksへのリンクです。このバージョンの幅優先検索は、隣接リスト (ポインターのリストの配列) で動作します。隣接リストを使用して各ノードに属性が割り当てられるため、ポインターを使用する必要があります。

実行後に各ノードに保存された BFS アルゴリズムからこれらの属性を保持したいと考えています。おそらくノードにインデックスを付け、並列配列を使用して属性を格納するなど、他の方法でこれを行うことができることを私は知っています。しかし、この疑似コード (リンクの BFS 用) と同様に機能するコードが必要でした。

4

2 に答える 2

2
  1. なぜベクトルの配列を使用しているのですか?
  2. なぜベクトルへのポインターを維持しているのですか?
  3. なぜポインターのベクトルを維持しているのですか?

これら 3 つの決定はすべてコストがかかり、ベクター クラスのメモリ管理機能を直接無効にします。ベクターは、内部で拡張できる単なる配列ではなく、RAIIと呼ばれるパターンを介してメモリを管理します。

ポインターのベクターを作成すると、そのベクターは破棄時にポインターが参照するメモリをクリーンアップできないため、deleteベクターのすべての要素を呼び出す必要があります。

ベクターへのポインターを作成する場合、ベクターがデストラクタで割り当てたメモリの割り当てを解除するという事実を利用することはできません。deleteしたがって、メモリ リークを防ぐためにベクトルを呼び出す必要があるため、ここでもベクトルのメモリ管理機能を無効にします。

ベクトルの配列を維持するとき...まあ、あなたはすでにベクトルを使用していvector<vector<T>>ます。

ベクター型は、特に現在発生している種類の問題を回避するために、舞台裏で動的にメモリを割り当てます。確かに、自分のメモリを管理することはできます (割り当てたのとは逆の順序で割り当てを解除するだけで、それを把握しているように見えます)。

ここでの設計目標がわかりません。単純に a を使用してvector<vector<Edge>>、これらの問題を完全に解決してみませんか?

class Edge {
    // whatever
}

class Graph {
private:
    // when instances of this class go out of scope, 
    // all of the memory allocated to these vectors is deallocated for you!
    vector<vector<Edge>> vertices;  
}
于 2012-05-02T04:54:35.560 に答える
0

ポインターを介して内部オブジェクトに多数のインデックスを付けてクラスを構築している場合、メモリ位置でオブジェクトを1 回だけ削除することを保証する 1 つの方法は、メモリ プールを保持することです。たとえば、std::vector<Node*> Graph::memPoolメンバーを持つことができます。を削除するときは、個々のノードの のインデックスではなく、 のGraphすべてを削除します。新しいノードが作成されるたびに、それをメモリ プールに追加するだけです。Graph::memPooladjList

現在の例では、2 つのノードに同じノードへのエッジがある場合、無効なメモリ ロケーションを削除できます。

もう 1 つの方法は、ポインターの代わりに番号付きインデックスを使用することです。グラフにはノードのマスター ベクトルがあり、各ノードの隣接リストにはベクトル インデックスが保持されます。

class Graph
{
    std::vector<Node> all_nodes;
    ...
};

struct Node
{
    std::vector<size_t> adjList;
    SomeDataType nodeData;//e.g. node cost, weight, reward, etc
    ...
};

この場合、明示的な解放は必要ありません。ポインターを使用する場合と同様に、グラフからノードを削除するには、隣接リストをスキャンしてインデックスを更新する必要があります。

于 2012-05-02T05:20:22.323 に答える