std::map の反復順序は既知ですか (標準で保証されていますか)? 質問する

std::map の反復順序は既知ですか (標準で保証されていますか)? 質問する

つまり、 の要素はキーに従ってソートされていることがわかっていますstd::map。したがって、キーが整数であるとします。を使用してstd::map::begin()からまで反復処理する場合、標準では、キーを持つ要素が昇順でソートされて反復処理されることが保証されますか?std::map::end()for


例:

std::map<int, int> map_;
map_[1] = 2;
map_[2] = 3;
map_[3] = 4;
for( std::map<int, int>::iterator iter = map_.begin();
     iter != map_.end();
     ++iter )
{
    std::cout << iter->second;
}

これは印刷されることが保証されています234か、それとも実装によって定義されますか?


実際の理由:キーstd::mapを持つ がありますint。非常にまれな状況では、キーが具体的な値より大きいすべての要素を反復処理したい場合がありますint。確かに、それがstd::vectorより良い選択のように思えますが、私の「非常にまれな状況」に注意してください。


編集: の要素がstd::mapソートされていることはわかっています。指摘する必要はありません (ここの回答のほとんどについて)。質問にも書きました。
コンテナーを反復処理するときの反復子と順序について尋ねていました。回答してくれた @Kerrek SB に感謝します。

ベストアンサー1

はい、それは保証されています。さらに、は比較演算子によって決定される*begin()最小要素と*rbegin()最大要素を提供し、式が true となる2 つのキー値aと は等しいとみなされます。デフォルトの比較関数は です。b!compare(a,b) && !compare(b,a)std::less<K>

順序付けは幸運なボーナス機能ではなく、むしろデータ構造の基本的な側面です。順序付けは、2 つのキーが同じかどうかを判断 (上記のルールによる) し、効率的な検索 (基本的には要素の数に対数的な複雑さがあるバイナリ検索) を実行するために使用されます。

おすすめ記事