c++ - STL ベクトル vs マップ消去

Question

STL では、ほとんどすべてのコンテナに消去機能があります。私が持っている質問はベクトルにあります.erase関数はベクトル内の次の要素を指す反復子を返します. マップ コンテナはこれを行いません。代わりに、void を返します。なぜこの矛盾があるのか​​ 知っている人はいますか？

Answer 1

http://www.sgi.com/tech/stl/Map.htmlを参照してください。

Map には、新しい要素をマップに挿入しても、既存の要素を指す反復子が無効にならないという重要な特性があります。マップから要素を消去しても、消去される要素を実際に指している反復子を除いて、反復子は無効になりません。

消去時にイテレータを返す理由は、要素を消去しながらリストを繰り返し処理できるようにするためです。項目を消去しても既存の反復子が無効にならない場合は、これを行う必要はありません。

Answer 2

eraseiteratorC++11 ではan を返します。これは、欠陥レポート 130によるものです。

表 67 (23.1.1) は、container::erase(iterator) が反復子を返すことを示しています。表 69 (23.1.2) によると、この要件に加えて、連想コンテナーは、container::erase(iterator) が void を返すことも示しています。これは追加ではありません。これは要件の変更であり、連想コンテナがコンテナの要件を満たさなくなるという影響があります。

標準化委員会はこれを受け入れました。

LWG は、戻り値の型が void ではなくイテレータであるべきであることに同意しています。（アレックス・ステパノフも同意見です。）

(LWG = ライブラリ ワーキング グループ)。

Answer 3

不一致は使用によるものです。vector要素の順序付けを持つシーケンスです。mapa の要素も何らかの比較基準に従って順序付けされていることは事実ですが、この順序付けは構造から明らかではありません。ある要素から次の要素に移動する効率的な方法はありません (効率的 = 一定時間)。実際、マップを反復処理するには非常にコストがかかります。イテレータの作成またはイテレータ自体のいずれかが、完全なツリーのウォークを伴います。これは、スタックが使用されない限り、 O ( n ) では実行できません。スタックが使用されている場合、必要なスペースは一定ではなくなります。

全体として、消去後に「次の」要素を返す安価な方法はありません。シーケンスの場合、方法があります。

さらに、ロブは正しいです。Map がイテレータを返す必要はありません。

Answer 4

余談ですが、MS Visual Studio C ++（Dinkumware IIRC）に同梱されているSTLはerase、イテレーターを次の要素に戻す関数を備えたマップ実装を提供します。

彼らはそれが標準に準拠していないことに注意します。

Answer 5

これが答えかどうかはわかりませんが、次の要素を見つけるコストが理由の 1 つかもしれません。マップの反復処理は、本質的に「遅い」ものです。