STL vector vs map erase

Question

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?

Answer 1

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".

Answer 2

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

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

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.

Answer 3

The inconsistency is due to use. vector is a sequence having an ordering over the elements. While it's true that the elements in a map 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.

Answer 4

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.

Answer 5

erase will return an iterator in C++0x. If you can cope with the standardeze, this is defect report 130. So the standards comittee seems to think that this was a mistake.