STL 矢量与地图擦除
在STL中几乎所有的容器都有擦除功能。 我的问题是在向量中,擦除函数返回一个指向向量中下一个元素的迭代器。 地图容器不执行此操作。 相反,它返回一个空值。 有人知道为什么会出现这种不一致吗?
In the STL almost all containers have an erase function. The question I have is in a vector, the erase function returns an iterator pointing to the next element in the vector. The map container does not do this. Instead it returns a void. Anyone know why there is this inconsistancy?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
顺便说一句,MS Visual Studio C++ (Dinkumware IIRC) 附带的 STL 提供了一个带有
erase
函数的映射实现,该函数返回到下一个元素的迭代器。他们确实注意到这不符合标准。
Just as an aside, the STL shipped with MS Visual Studio C++ (Dinkumware IIRC) provides a map implementation with an
erase
function returning an iterator to the next element.They do note it's not standards conforming.
我不知道这是否是答案,但一个原因可能是定位下一个元素的成本。 迭代地图本质上是“慢”的。
I have no idea if this is the answer, but one reason might be with the cost of locating the next element. Iterating through a map is inherently "slow".
不一致是由于使用造成的。
vector
是一个对元素进行排序的序列。 虽然map
中的元素确实也是根据某种比较标准排序的,但这种排序从结构中并不明显。 没有有效的方法从一个元素移动到下一个元素(有效=恒定时间)。 事实上,迭代地图的成本相当高; 迭代器的创建或迭代器本身都涉及遍历整个树。 这不能在 O(n) 内完成,除非使用堆栈,在这种情况下所需的空间不再恒定。总而言之,根本没有便宜的方法可以在擦除后返回“下一个”元素。 对于序列,有一种方法。
此外,罗布是对的。 Map 不需要返回迭代器。
The inconsistency is due to use.
vector
is a sequence having an ordering over the elements. While it's true that the elements in amap
are also ordered according to some comparison criterion, this ordering is non-evident from the structure. There is no efficient way to get from one element to the next (efficient = constant time). In fact, to iterate over the map is quite expensive; either the creation of the iterator or the iterator itself involves a walk over the complete tree. This cannot be done in O(n), unless a stack is used, in which case the space required is no longer constant.All in all, there simply is no cheap way of returning the “next” element after erasing. For sequences, there is a way.
Additionally, Rob is right. There's no need for the Map to return an iterator.
erase
在 C++11 中返回一个iterator
。 这是由于缺陷报告 130:标准委员会接受了这一点:
(LWG = 图书馆工作组)。
erase
returns aniterator
in C++11. This is due to defect report 130:The standards committee accepted this:
(LWG = Library Working Group).
请参阅http://www.sgi.com/tech/stl/Map.html
在擦除时返回迭代器的原因是,您可以在删除元素时迭代列表。 如果删除项目不会使现有迭代器无效,则无需执行此操作。
See http://www.sgi.com/tech/stl/Map.html
The reason for returning an iterator on erase is so that you can iterate over the list erasing elements as you go. If erasing an item doesn't invalidate existing iterators there is no need to do this.