STL矢量vs地图擦除

Question

在STL中,几乎所有容器都具有擦除功能.我的问题是在向量中,erase函数返回一个指向向量中下一个元素的迭代器.地图容器不会这样做.相反,它返回一个空白.有人知道为什么会有这种不一致吗？

Answer 1

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

Map具有重要的属性,即将新元素插入到映射中不会使指向现有元素的迭代器无效.从地图中删除元素也不会使任何迭代器无效,当然,除了实际指向正在被删除的元素的迭代器之外.

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

Answer 2

eraseiterator在C++ 11中返回一个.这是由于缺陷报告130:

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

标准委员会接受了这个:

LWG同意返回类型应该是迭代器,而不是无效.(Alex Stepanov也同意.)

(LWG =图书馆工作组).

Answer 3

不一致是由于使用.vector是对元素具有排序的序列.虽然a map中的元素也是按照某种比较标准排序的,但这种排序在结构上是不明显的.没有有效的方法可以从一个元素到另一个元素(有效=恒定时间).事实上,迭代地图是相当昂贵的; 迭代器的创建或迭代器本身涉及遍历整个树.这不能在O(n)中完成,除非使用堆栈,在这种情况下所需的空间不再是恒定的.

总而言之,在擦除之后根本就没有廉价的方法来返回"下一个"元素.对于序列,有是一种方式.

另外,罗布是对的.Map不需要返回迭代器.