STL ベクトルとマップ消去

Question

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

Answer 1

見る http://www.sgi.com/tech/stl/Map.html

MAPには、新しい要素をマップに挿入しても、既存の要素を指すイテレーターを無効にしない重要なプロパティがあります。マップから要素を消去しても、もちろん消去されている要素を実際に指しているイテレーターを除き、反復因子を無効にしません。

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

Answer 2

erase を返します iterator C++11では。これは、に起因するものです 欠陥レポート 130:

表 67 (23.1.1) には、container::erase(iterator) がイテレータを返すことが記載されています。表 69 (23.1.2) では、この要件に加えて、連想コンテナーは、container::erase(iterator) が void を返すとも述べています。それは追加ではありません。これは要件の変更であり、関連付けられたコンテナがコンテナの要件を満たさなくなる影響があります。

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

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

(LWG = 図書館ワーキンググループ)。

Answer 3

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

全体として、消去後に「次の」要素を戻す安価な方法はありません。シーケンスについては、 は 離れて。

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

Answer 4

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

彼らは、それが規格に準拠していないことを指摘しています。

Answer 5

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