从STL集中擦除最大元素

Question

这是我之前的一个问题(STL max_element的复杂性)的后续跟进.

我想基本上从一组中弹出最大元素,但我遇到了问题.

这大致是我的代码:

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

早些时候我试过,objectSet.erase(objectSet.rbegin());但编译器抱怨没有匹配的功能(我猜它不喜欢reverse_iterator).我知道没有检查空集,但是当objectSet.size()>> 0时它失败了.

Answer 1

你非常接近,但你试图在迭代器分配中做太多.您将后递减运算符应用于任何end返回.我不确定那是什么,但几乎肯定不是你想要的.分配结果end来i,和然后递减它得到了一组的最后一个元素.

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

Answer 2

你需要这样做:

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

该声明

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

表示'将end赋值给i然后递减一个即将丢弃的临时变量'.换句话说,它是相同的set<Object>::iterator i = objectSet.end();,我相信你会认识到你不能擦除end(),因为它指向一个结尾.使用这样的东西代替:

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

这没关系,这是一个合法的方式来重新.back()集合一组.

另外,反向迭代器有一个base()转换为普通迭代器的成员,我想你只能删除正常的迭代器 - 试试objectSet.erase(objectSet.rbegin().base()).