views:

793

answers:

4

Consider:

#include <map>

int main()
{
    std::map< int, int > m;
    m[ 0 ] = 0;
    m[ 1 ] = 1;

    m.erase( 0 );  // ok
    m.erase( 2 );  // no-op
    m.erase( m.find( 2 ) );  // boom!
}

(OK, so the title talks abouting erasing an end() iterator, but find will return end() for a non-existent key.)

Why is erasing a non-existent key OK, yet erasing end() blows up. I couldn't see any explicit mention of this in the standard?

I've tried this on VS2005 (throws an exception in debug configuration) and GCC 4.0.1 (100% CPU). Is it implementation dependent?

Thanks.

+16  A: 

'end()' is not an interator into the map. It's effectively 'one past the end' of the map. The iterator version wants an iterator to something in the map. The 'key' version of erase does the lookup and protects itself against key not found, the iterator version assumes you aren't trying to break stuff.

Michael Kohne
"assumes you aren't trying to break stuff"... I understand, I was hoping erase(it) would do a simple check that it != end()
Steve Folly
Not an unreasonable thought, it's just that many parts of the STL containers don't want the overhead of such checks. In cases like erase, the iterator is probably been used for something else before you wanted to erase the entry, so they leave out the check for end - because you probably already did it. In the key case, it's more likely that the caller doesn't know if the key is in the map or not, so they do the check.
Michael Kohne
+11  A: 

For erase(key), the standard says that all elements with value key are removed. There may of course be no such values. For erase(it) (where 'it' is a map iterator), the standard says that the element pointed to by it is removed - unfortunately, if it is end() it does not point to a valid element and you are off in undefined behaviour land, as you would be if you used end() for any other map operation. See section 23.1.2 for more details.

anon
To clarify: there are different overloads of erase(), and the iterator version requires a valid element.
rlbond
erase(it) is equivalent to erase(it, ++iterator(it)), which helps me to see that erase(it) is invalid with it=map.end(). You would need another iterator after .end().
Johannes Schaub - litb
Can anyone provide a link to the standard?
Paul Morie
The final Standards documents are not available on-line, but you can see an early draft here: http://www.open-std.org/jtc1/sc22/wg21/docs/wp/html/oct97/
anon
+1  A: 

Here is a quick example of how I use the STL map with iterators while removing. I also do the same thing when performing an insert. Personally I like using typedef to specifically define the map, but the choice is yours.


typedef std::map... MapType;

MapType the_map;

MapType::iterator it = the_map.find ("key");
if (it != the_map.end()) {
  // Do something productive.
  the_map.erase (it);
}

MapType::iterator it = the_map.find ("new_key");

// Does not exist.
if (it == the_map.end()) {
  the_map.insert (std::make_pair ("new_key", 10));
}

Hope this helps!

John Bellone
+1  A: 

Instead of the example given in a previous post...

MapType::iterator it = the_map.find ("new_key");

// Does not exist.
if (it == the_map.end()) {
  the_map.insert (std::make_pair ("new_key", 10));
}

which does two tree traversals, use...

pair<MapType::iterator, bool> rc = the_map.insert(make_pair("new_key", 0));
if (rc.second)
    rc.first.second = 10;

That way you do one tree traversal and you have the iterator ready to roll for other stuff.

tim