データベースのような検索用のコンテナ

Question

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

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

また

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

STD :: MAPを使用することを考えましたが、テキストで「始める」フィールドを検索する必要があり、「等しい」ものではなく、テキストを「始める」フィールドを検索する必要があるためにできません。それに加えて、複数のフィールドで動作する必要があります（たとえば、各「レコード」には6つのフィールドがあります）ので、それぞれに個別のSTD ::マップが必要です。

ソートされたベクトルまたはリストを作成して、バイナリ検索を使用できます（中央の要素を読み、「x」よりも多かれ少なかれあるかどうかを確認することで、各ステップで2つのセットを破壊します）が、準備が整っているかどうかは疑問です。ホイールを再発明せずに使用できる容器を作った？

Answer 1

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)

Answer 2

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