2

現在、次のようなベクトルのベクトルを使用しています。

typedef pair<int, int> vertex;
vector < vector<vertex> > adj_list(n); // n is number of vertices

// Input graph
for (int i = 0; i < edges; i++ )
{
   cin >> source >> target >> weight;
   vertex v(target, weight);
   adj_list[source].push_back(v);
}

リストのベクトルです。

vector < list<vertex> > adj_list(n);

より良いオプション？はいの場合、なぜですか? 私の主な関心事は、ダイクストラのアルゴリズムを実装するために、隣接リストを効率的に作成し、特定の頂点に接続されているすべての頂点を高速に読み取れるようにすることです。

4

3 に答える 3

2

そのためには、 std::deque<> を使用します。これは、途中から要素を削除する必要がない可能性が高いためです (これが、誰かが std::list<> を使用したい理由です)。std::vector<> や std::list<> よりも効率的です。連続したメモリ (ベクトル) とリムーバブル アイテム (リスト) を使用すると、コストがかかります。ベクトルとポインターの逆参照/リストの散在するメモリのサイズ変更にコストがかかります。

参照: http://www.gotw.ca/gotw/054.htm

アルゴリズム コンテストを対象としている場合、STL ベースのデータ構造がどれだけのメモリを消費するかに驚くかもしれません。

于 2012-12-31T20:10:21.703 に答える
2

あなたの要求は、迅速な挿入と迅速な反復です。漸近的には、 と の間に違いはありませvector<vector<T> >んvector<list<T> >。

  • list<T>は双方向にリンクされたリストであるため、すべての挿入に時間がかかりO(1)、反復にはO(1)要素ごとに時間がかかります。
  • vector<T>配列であり、すべての挿入にO(1)(償却された) 時間 [1] がかかり、反復にはO(1)要素ごとに時間がかかるように実装されています。

操作の定数はおそらく異なりますが、それはプロファイリングで確認する必要があります。

vector<vector<T> >ただし、のすべての要素はvector<list<T> >前方ポインターと後方ポインターも保持するため、空間効率は を優先します。したがって、おそらく を使用したいでしょうvector<vector<T> >が、一般的なケースで再割り当てを回避する方法で (時間を節約するため)、予約しすぎないようにします (スペースを節約するため)。

外側のベクトルについては、それを呼び出すことができます。.reserve(n)ここでn、 はグラフ内の頂点の数です。

内部ベクトルの場合は少し難しく、データがこのプロシージャにどのように供給されるかに大きく依存します。

[1] の実装はvector<T>、再割り当てのたびに容量を 2 倍にする必要があるため、再割り当てにかかる時間はO(1+2+4+...+n/4+n/2+n) = O(n(1/n+2/n+4/n+...+1/4+1/2+1)) <= O(1+1/2+1/4+...)) = O(2n)です。nそのため、要素に分散されているため、挿入にはO(1)(償却された) 時間がかかります。

于 2012-12-31T20:15:48.523 に答える