3

次のようなクエリを使用してレコードを検索するために、データベースでインデックスが使用されるのと同じ方法を使用する STL、ブースト、または同様のコンテナーを探しています。

select * from table1 where field1 starting with 'X';

また

select * from table1 where field1 like 'X%';

std::map を使用することを考えましたが、「等しい」フィールドではなく、「で始まる」フィールドを検索する必要があるため、使用できません。それに加えて、複数のフィールドで動作する必要があるため (たとえば、各「レコード」には 6 つのフィールドがあります)、それぞれに個別の std::map が必要になります。

ソートされたベクトルまたはリストを作成し、バイナリ検索を使用することもできます (各ステップでセットを 2 つに分けて、中央の要素を読み取り、それが「X」より大きいか小さいかを確認します)。車輪を再発明せずに使用できるコンテナーを作成しましたか?

4

2 に答える 2

10

Boost.Multi-Indexを使用すると、複数のインデックスで管理でき、std::set/map のように lower_bound を実装します。フィールドに対応するインデックスを選択し、それがマップまたはセットであるかのように行う必要があります。

次は、いくつかのイテレータを取得するために使用できる一般的な関数に続きます。最初の項目は特定の接頭辞で始まる最初の項目、2 番目は次の接頭辞で始まる最初の項目、つまり検索の終わりです。

template <typename SortedAssociateveContainer>
std::pair<typename SortedAssociateveContainer::iterator, 
          typename SortedAssociateveContainer::iterator> 
starts_with(
  SortedAssociateveContainer const& coll, 
  typename SortedAssociateveContainer::key_type const& k)
{
  return make_pair(coll.lower_bound(k), 
                   coll.lower_bound(next_prefix(k));
}

どこ

  • next_prefix は、SortedAssociateveContainer コンパレータに基づく辞書式順序を使用して、次のプレフィックスを取得します (もちろん、この関数を完全に汎用にするためには、さらに引数が必要です。質問を参照してください)。

の結果はstarts_with、任意のレンジ アルゴリズムで使用できます ( Boost.Rangeを参照) 。

于 2010-04-22T11:17:23.977 に答える
5

std::mapまたはstd::set、文字列以外のデータがない場合。プレフィックス文字列を渡してlower_bound、その時点以降にソートされる最初の文字列を取得します。次に、最後に到達するか、プレフィックスで始まらない要素が見つかるまで、マップを順方向に繰り返します。

于 2010-04-22T10:40:10.673 に答える