c++ - 逆順でマルチマップを検索する

Question

マルチマップ (C/C++ STL) を対数複雑度で逆順に検索する方法はありますか?

Answer 1

あなたの質問は 2 つの方法で解釈できます。同じキーを持つ一連の要素を挿入したことを意味し、そのキーを持つ最後に挿入された要素を見つけたい場合はequal_range(key)、 を試すことができます。これは、イテレータのペア (最初の要素を指すもの、その他は最後）。multimapただし、同じキーを持つ要素が格納される順序について保証があるかどうかはわかりません。

multimapまたは、逆の順序でトラバースしたい場合は、 と を使用rbegin()しrend()て逆のイテレータを取得できます。

Answer 2

a は基本的にツリー表現であるため、唯一の検索メカニズムはツリーをトラバースすることであると確信していmultimapます。「前方」と「後方」はありません。

で最初に一致する要素、lower_boundで最後の一致の 1 つ前upper_bound、または でキーに一致する全範囲を検索できますequal_range。編集:これらのメソッドはすべて対数的複雑度で実行されます。

必要なものについて詳しく教えていただけますか？

Answer 3

upper_bound通常どおりandを使用できlower_boundますが、反復コードを逆にすることができます。

最後に一致する要素は次のように検出されます。

ub = m.upper_bound(1);
lb = m.lower_bound(1);
if (ub != lb) {
  --ub;
  return ub->second;
}

または、1回のルックアップで:

ub = m.upper_bound(1);
if (ub != m.begin()) {
  --ub;
  if (ub->first == 1) {
    return ub->second;
  }
}

Answer 4

std::multimapでキーを見つけるための検索アルゴリズムを探していると思います。

1. キーの中に任意のキーO(log n)を見つけることを保証しますmultimapn

2. O(1)によって保持される最大のキーであるキーを見つけることを保証します。multimap

そのようなものは組み込まれていません。ほとんどの (すべて?) マルチマップはバランスの取れたツリーとして実装され、 への呼び出しはmultimap::find()最初にマップの中央をテストします。これは、ツリーのルートがそこにあるためです。ノイズの多い を実装すると、自分の目で確かめることができますoperator<。

が指すキーをテストするだけで、要件rbegin()をmultimap::find()満たすことができますか?

「最後に挿入された」とは、実際にマップに最後に追加された要素を意味する場合、それを見つける方法はまったくなくmultimap、他の連想コンテナーは挿入の順序に関する情報を保持しません。