erase max element from STL set

Question

This is a follow-up on a previous question I had ( http://stackoverflow.com/questions/3313301/complexity-of-stl-max-element ).

I want to basically pop the max element from a set, but I am running into problems.

Here is roughly my code:

set<Object> objectSet;

Object pop_max_element() {
    Object obj = *objectSet.rbegin();
    set<Object>::iterator i = objectSet.end()--; //this seems terrible
    objectSet.erase(i); //*** glibc detected *** free(): invalid pointer
    return obj;
}

Earlier I tried objectSet.erase(objectSet.rbegin()); but the compiler complained that there was no matching function (I'm guessing it doesn't like the reverse_iterator). I know there is no checking for an empty set, but it's failing when objectSet.size() >> 0.

Answer 1

You're pretty close, but you're trying to do a little too much in that iterator assignment. You're applying the post-decrement operator to whatever end returns. I'm not really sure what that does, but it's almost certainly not what you want. Assign the result of end to i, and then decrement it to get the last element of the set.

set<Object>::iterator i = objectSet.end();
--i;
Object obj = *i;
objectSet.erase(i);
return obj;

Answer 2

You need to do this:

set<Object> objectSet;

Object pop_max_element() {
    Object obj = *objectSet.rbegin();
    set<Object>::iterator i = --objectSet.end(); // NOTE: Predecrement; not postdecrement.
    objectSet.erase(i); //*** glibc detected *** free(): invalid pointer
    return obj;
}

Answer 3

The statement

set<Object>::iterator i = objectSet.end()--;

means 'assign end() to i then decrement a temporary variable that is about to be thrown away'. In other words it's the same as set<Object>::iterator i = objectSet.end();, and I'm sure you recognise you cannot erase end(), because it points to one past the end. Use something like this instead:

assert(!objectSet.empty()); // check there is something before end
set<Object>::iterator i = objectSet.end();
--i;
objectSet.erase(i);

and that's okay, it's a legitimate way to essentially reproduce .back() for a set.

Also, reverse iterators have a base() member to convert to a normal iterator and I guess you can only erase normal iterators - try objectSet.erase(objectSet.rbegin().base()).