STL 矢量与地图擦除

Question

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

Answer 1

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

地图具有将新元素插入地图中的重要属性不会使指向现有元素的迭代器无效。从地图上删除元素也不会使任何迭代器无效，除了迭代器外，实际上指向要删除的元素的迭代器。

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

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 是对元素进行排序的序列。虽然 a 中的元素确实是 map 也根据一些比较标准排序，这种排序从结构中是不明显的。没有有效的方法从一个元素移动到下一个元素（有效=恒定时间）。事实上，迭代地图的成本相当高；迭代器的创建或迭代器本身都涉及遍历整个树。这不能在 氧(n），除非使用堆栈，在这种情况下所需的空间不再是恒定的。

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

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

Answer 4

顺便说一句，MS Visual Studio C++ (Dinkumware IIRC) 附带的 STL 提供了一个地图实现，其中包含 erase 函数返回一个迭代器到下一个元素。

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

Answer 5

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