c++ - マップエントリの順序を学習するC ++

Question

キーを文字列として持つマップがある場合。どの文字列がマップのどの場所にあるかを知るにはどうすればよいですか? たとえば、'cats' は最初のエントリで、'dogs' は 2 番目のエントリです。犬がマップの 2 番目のエントリであることをどのように知ることができますか? 地図を調べて注文を検索/確認する必要がありますか、それとももっと簡単な方法はありますか?

Answer 1

いずれにせよ、これ以上のことはできません。その理由は 2 つあります。

a) std::map にはその中にツリーがあるため、最初はツリーの葉には線形順序がなく、部分的な順序しかありません (もちろん、2 つのキーを比較することはできますが、一般的なバイナリ ツリーではそれを行うことはできません -それが複雑さの理由です）。

b) std::map には双方向イテレータがあるため、効果的なイテレータ演算を行うことはできません。次のようにできます。

typedef map<string, int> MyMapT;
MyMapT data;
// ...
auto it = data.find("dog");
if (it == data.end()) {
  // don't have such a key
}
auto position = distance(data.begin(), data.end());

残念ながら、距離関数は双方向イテレータに対して O(n) 時間で機能するため、これは最善の方法ではありません。繰り返しますが、これは std::map 内のツリー構造によるものです。