c++ - STL 矢量与地图擦除

Question

在 STL 中，几乎所有容器都有擦除功能。我的问题是在向量中，擦除函数返回一个指向向量中下一个元素的迭代器。地图容器不这样做。相反，它返回一个 void。有谁知道为什么会出现这种不一致？

Answer 1

见http://www.sgi.com/tech/stl/Map.html

Map 有一个重要的属性，即在 map 中插入一个新元素不会使指向现有元素的迭代器失效。从映射中擦除元素也不会使任何迭代器无效，当然，除了实际指向正在被擦除的元素的迭代器。

在擦除时返回迭代器的原因是您可以随时迭代列表擦除元素。如果擦除项目不会使现有迭代器无效，则无需执行此操作。

Answer 2

eraseiterator在 C++11 中返回一个。这是由于缺陷报告 130造成的：

表 67 (23.1.1) 说 container::erase(iterator) 返回一个迭代器。表 69 (23.1.2) 说除了这个要求之外，关联容器还说 container::erase(iterator) 返回 void。那不是补充。这是对需求的更改，其效果是使关联容器无法满足容器的需求。

标准委员会接受了这一点：

LWG 同意返回类型应该是迭代器，而不是 void。（亚历克斯·斯捷潘诺夫也同意。）

（LWG = 图书馆工作组）。

Answer 3

不一致是由于使用。vector是一个对元素进行排序的序列。虽然确实 a 中的元素map也根据一些比较标准进行了排序，但这种排序从结构中并不明显。没有从一个元素到下一个元素的有效方法（高效 = 恒定时间）。事实上，遍历地图是相当昂贵的。迭代器的创建或迭代器本身都涉及遍历整个树。这不能在O ( n ) 中完成，除非使用堆栈，在这种情况下所需的空间不再是恒定的。

总而言之，根本没有便宜的方法可以在擦除后返回“下一个”元素。对于序列，有一种方法。

此外，Rob 是对的。Map 不需要返回迭代器。

Answer 4

顺便说一句，MS Visual Studio C++ (Dinkumware IIRC) 附带的 STL 提供了一个映射实现，该实现带有一个erase将迭代器返回到下一个元素的函数。

他们确实注意到这不符合标准。

Answer 5

我不知道这是否是答案，但一个原因可能是定位下一个元素的成本。遍历地图本质上是“慢”的。