0

一意でないキーと値のペアを格納するソリューションが必要です。キーを繰り返したくない (スペース効率) と、ルックアップ速度に集中したい (新しいデータを挿入する効率はそれほど重要ではありません)。ここでは std::multimap を使用します。ただし、いくつかの範囲基準を満たすキーを検索する必要があります。

最も複雑な例: キーは文字列で、値は重要ではありません。「Lol」で始まるすべての値を調べたいと思います。または、キーが「bar」と「foo」の間にあるすべての値を見つけたいと思います。

マルチマップでできますか？私の 2 番目の考えは、値のベクトルを指す、並べ替えられたベクトルを使用することです。そんな感じ：

std::vector<std::string, std::vector<T>> sorted_vec;

そうすれば、検索条件を簡単に満たすことができます。しかし、私はルックアップのパフォーマンスを本当に気にしています。それは正しいアプローチですか？

4

3 に答える 3

2

はい、std::multimap を使用できます。範囲ベースのクエリを完了するには、ヘッダー ファイル アルゴリズムで std::lower_bound と std::upper_bound の 2 つのアルゴリズムを使用できます。

于 2013-04-07T03:28:50.757 に答える
1

または、キーが「bar」と「foo」の間にあるすべての値を見つけたいと思います。

Boost をお持ちの場合は、boost::flat_map (単なるヘッダーのみのライブラリ)を使用することをお勧めします。一般に、コンパクト性/局所性が優れているため、 std::mapよりもルックアップが優れています。

それ以外の場合は使用

vector<pair<string,value>>
or
vector<pair<string,vector<value>>> //(for re-use of keys)
// instead of pair, you may use just struct if you concerned with lexicographical compare

プラスstd::sort

プラス std:: equal_range / lower_bound

于 2013-04-07T02:46:45.920 に答える
0

パトリシア トライを使用する必要があります。

非標準ですが、 libstdc++ に 1 つあります。

標準のコンテナーに固執する場合は、並べ替えられたベクター ソリューションが最適だと思います。

于 2013-04-07T02:51:50.960 に答える