2

整数0...N-1から何らかのタイプのリストへのマッピングを頻繁に表す必要がありますT。個々のリストには、要素を動的に最後に追加する必要があります。N通常、事前にわかっています (ただし、コンパイル時ではありません)。個々のリストにすばやくアクセスする必要があります。

私は通常、 を使用してこれを実装しvector<vector<T> > my_map(N)、 を使用my_map[key].push_back(val)して要素を追加します。

2 つの質問があります。

これは、そのようなマップを実現するための効率的で推奨される方法ですか?

また、要素の連続性とサイズ変更への影響についても疑問に思います。たとえば、 で要素を追加しmy_map[key].push_back(val)、 でサイズを変更する必要があるとmy_map[key]しkey != N-1ます。my_mapこれは、内容を連続させておくために、ベクター全体のコピーをトリガーしますか? それともmy_map、ヒープ上のベクトルへのポインタで内部的に実現されていますか?

これはSTLの実装に依存する可能性があることを認識しています。私は主に、Visual Studio 2010 と Linux の GCC のメカニズム (および速度への影響) に関心があります。

アップデート

コメントの中で、@PeterWoodstd::dequeはリストのコンテナとして私を指摘しました。asと比較するために非科学的なベンチマークをvector< deque<T> >行いvector< vector<T> >ました。どちらも、30 個の要素を持つ 100 万個のリストと、それぞれ 3000 個の要素を持つ 10,000 個のリストの時間を計りました。私のテストは、このタイプのデータ構造の典型的なアプリケーション シナリオを反映していることに注意してください。unsigned intT

次のように機能するランダムアクセスの「ビルドアップ」の時間を計りました。

vector<ContainerT> my_map(numKeys);
vector<unsigned int> random_keys(numKeys);
for (unsigned int i=0; i<numKeys; ++i) random_keys[i] = i;
random_shuffle(random_keys.begin(),random_keys.end());

for (auto pKey=random_keys.begin(); pKey!=random_keys.end(); ++pKey)
{
  for (unsigned int i=0; i<listSize; ++i)
  {
    my_map[*pKey].push_back( rand() );
  }
}

そして、ランダムに選択されたリストから 3,000 万のランダムな要素をクエリするタイミングを計りました。

結果

deque多くの小さなリストの構築はわずかに高速ですが、両方のシナリオのベクトルよりもクエリが遅くなります。vector< vector<T> >私は自分のタイプの問題のために一緒にいると結論付けています。

deque

Keys: 1000000, list size: 30
Mean time buildup: 1.29517 seconds
Mean time query: 4.17624 seconds

Keys: 10000, list size: 3000
Mean time buildup: 0.998761 seconds
Mean time query: 5.052 seconds


vector

Keys: 1000000, list size: 30
Mean time buildup: 1.5347 seconds
Mean time query: 1.63043 seconds

Keys: 10000, list size: 3000
Mean time buildup: 0.604954 seconds
Mean time query: 1.58328 seconds
4

3 に答える 3

2

これは、そのようなマップを実現するための効率的で推奨される方法ですか?

これは、そのようなマップを実装するための完全に合理的な方法だと思います。

また、要素の連続性とサイズ変更への影響についても疑問に思います。たとえば、 で要素を追加しmy_map[key].push_back(val)、 でサイズを変更する必要があるとmy_map[key]しkey != N-1ます。my_mapこれは、内容を連続させておくために、ベクター全体のコピーをトリガーしますか? それともmy_map、ヒープ上のベクトルへのポインタで内部的に実現されていますか?

いいえ、それは外部ベクトル全体のコピーをトリガーしません。サブベクトルのみが連続しています。ベクトル全体は一般的にそうではありません。

my_mapメンタル モデルに関する限り、単一の連続した 2D 配列ではなく、1D 配列へのポインターの配列と考えることができます。

于 2013-03-13T10:58:18.127 に答える
0

ベクトル オブジェクトを外側のベクトルにコピーします。ただし、これらのベクトル内のヒープ上のオブジェクトは再割り当てされません。

于 2013-03-13T10:59:05.037 に答える
0

通常、各 std::vector は、型 T のオブジェクトの配列を割り当てるメモリを指す内部ポインターを保持します。

my_mapこのようなタイプ T のベクトルのベクトルでは、外部ベクトルはそのような配列へのポインタのベクトルとしてのみ見ることができるため、内部ベクトルのサイズを変更しても外部ベクトルのサイズは変更されません (この例では)。内側のベクトル配列は、外側のベクトル以外のメモリ位置にあります。

同じ理由で、あなたの内部ベクトル間に連続性はありませんmy_map

于 2013-03-13T10:59:07.407 に答える