erase max element from STL set

This is a follow-up on a previous question 开发者_运维百科I had ( 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.

---

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;

---

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;
}

---

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()).