0 
std::vector<std::string> vec1, vec2, vec3, vec4;
//populate all vectors, all have the same size
//vec1 has different values

ここで、vec1に「foo」などの「キー」が与えられた場合、他のベクトルから対応する文字列をすばやく取得するにはどうすればよいですか。

これは、vec1のさまざまなキーを使用して何度も実行する必要があるため、この操作は高速である必要があります。

vec1の要素をインデックス値（0,1,2,3,4 ...）にマップするマップを作成する必要がありますか？

これはC++でどのように最適に行われますか？

4

2 に答える 2

2

「すぐに」が何を意味するかによります。

値による取得の複雑さが気になる場合は、代わりにstd::unordered_set(一定の検索と挿入/削除時間) または(対数検索std::setとstd::multiset挿入/削除時間、重複が許可されている 2 つ目)などの連想コンテナーの使用を検討することをお勧めします。のvector。

ただし、vector要素を格納するためにメモリの連続した領域を割り当てるため、線形アクセスではキャッシュ ヒット率が高くなることは言うまでもありません。したがって、複雑さは悪化しますが、アクセスは一般的に「高速」であり、std::findorなどの通常の STL アルゴリズムを使用std::find_if()して、特定の値に一致する要素や特定の述語を満たす要素を見つけることができます。

多くの場合、データの局所性により、複雑さの悪化を補うことができます。ここで重要なのは、常に測定を繰り返して、最高のパフォーマンスを実現するソリューションを決定することです。

とはいえ、最適なソリューションは全体的なワークロードに依存する可能性があります。ベクトルの要素ごとの反復をまったく行っていますか? どのくらいの頻度で要素を位置で取得する必要がありますか? これらが頻繁な操作でない場合、ベクトルは必要ないかもしれません。さらに、それらのベクトルはどのくらいの頻度で更新されますか? これらのベクトルの要素を値で検索する必要がある頻度はどれくらいですか? あなたの質問はこれについて多くを語っていません。

メモリのオーバーヘッドが問題にならない場合は、別のマップをインデックスとして作成し、冗長構造を維持することを検討できます。vectorただし、 が挿入と削除で頻繁に更新される場合は、インデックスと の一貫性を確保するvectorのが面倒になる可能性があります。

于 2013-02-10T15:42:26.340 に答える
1

あなたが本当に欲しいのはstd::unordered_map<std::string, std::tuple<std::string, std::string, std::string>>. std::vectorこれにより、 s が同じ長さでなければならないという不変条件を維持する必要がなくなります。また、他の文字列の一定時間のルックアップも提供します。例えば、

typedef std::tuple<std::string, std::string, std::string> value_type;
std::unordered_map<std::string, value_type> map;

// Populate the map
map["foo"] = std::make_tuple("first", "second", "third");
// ...

std::get<0>(map["foo"]); // Get the first string that "foo" maps to

std::vector4 つの sを使用して設計を変更したくない場合は、 std::findandを使用して最初std::distanceの のインデックスを見つけ、次にそのインデックスを他のものに使用する必要があります。"foo"std::vector

auto key_it = std::find(std::begin(vec1), std::end(vec1), "foo");
int index = std::distance(std::begin(vec1), key_it);
std::string s2 = vec2[index];
std::string s3 = vec3[index];
std::string s4 = vec4[index];
于 2013-02-10T15:42:17.267 に答える