注文したSTLコンテナ内の接頭辞で始まるすべての文字列（非ASCII文字以外）を検索します

Question

std::string（数十万エントリ）の巨大なSTLコンテナがあります。私は現時点でvectorを使用していますが、私は変更して嬉しいです。内容はアルファベット順にソートされ、アルファベットの小文字a-z とñで構成されています。

const std::string& prefixを受け取り、そのような接頭辞で始まる最初の要素と最後の要素を指す最初の要素を指す1組の反復子を返す関数を実装しようとしています。条件に一致する文字列がない場合は、2つの同一イテレータを返します。ベクトルが膨大であるため、検索に効率が必要なので、バイナリ検索のためにそれを使用したいと考えています。

私が探しているのはstd::lower_boundだと思いますが、ñを扱うことができるstd::stringを比較する関数がありません。

Answer 1

std::equal_rangeで等しい値の全範囲を取得できます。コレクションに少なくとも1つの一致する文字列がある場合、範囲の終わりを過ぎて1つずつ、イテレータのペアを返します。文字列が存在しない場合は、その文字列が存在する場合にその位置に属する直後の最初の位置に2つの等しいイテレータを与えます。

同一の部分文字列を探すだけであれば、（最初のN文字の）通常の文字列比較がうまくいくはずです。入力文字列のペアのようなものをサポートしたい場合、それらの間のすべての入力を検索したいので、 "m *"から "o *"（ "ñ*"文字列2つの間にあると扱われる）、少し好奇心を持たなければなりません（通常は、文字コードをインデックスとして、それぞれの位置の値として相対的な順序で照合テーブルを作成します）。