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

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 2

erase returns an iterator in C++11. This is due to defect report 130:

Table 67 (23.1.1) says that container::erase(iterator) returns an iterator. Table 69 (23.1.2) says that in addition to this requirement, associative containers also say that container::erase(iterator) returns void. That's not an addition; it's a change to the requirements, which has the effect of making associative containers fail to meet the requirements for containers.

The standards committee accepted this:

the LWG agrees the return type should be iterator, not void. (Alex Stepanov agrees too.)

(LWG = Library Working Group).

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

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