如何擦除一对 列表中的元素

Question

list<pair<int,int>> li{{5,6},{7,8},{9,10}};
for(auto it=li.rbegin();it!=li.rend();++it) {
    cout << (*it).first << (*it).second << '\n';
    li.erase(it);
}

错误：没有匹配函数来调用'std :: list <std :: pair <int，int >>> :: erase（std :: reverse_iterator <std :: _ List_iterator <std :: pair <int，int >> >>＆ ）” li.erase（它）;

如果li.erase(it)被li.remove(*it)取代，代码工作正常。但是，所有的值都将被删除。算法变为O（n2），而不是O（n），对吗？

Answer 1

迭代时擦除是一个坏主意。如果it不在列表中，++it会做什么？好问题！我不知道，但除非你不走运，否则这不是你想要的。如果程序有效，为什么不吉利？因为它没有，下次它可能会做一些完全不同的事情。

所以几乎所有基于循环的迭代和删除方法似乎都有效（li.remove(*it)和li.erase( --(it.base()) )实际上没有。

通常我会调整erase-remove idiom来解决这个问题，但是如果你试图使用C ++的内置工具，那么反向迭代器会让它变得一团糟。此外，在这种情况下，remove_if的答案总是如此。

对于上面提出的问题，甚至不要尝试。相反，打印li.back()然后li.pop_back()直到列表为空。

while (!li.empty()) {
    cout << li.back().first << li.back().second << '\n';
    li.pop_back();
}

Answer 2

你可以用li.erase(it)替换li.erase(it.base())。

std::list.erase不允许使用reverse_iterator作为参数，因此您首先需要将reverse_iterator转换为iterator。

就我所知，你对O（n ^ 2）和O（n）分析是正确的。

编辑：

实际上，根据这个类似的答案：How to call erase with a reverse iterator

你真正应该做的是li.erase( --(it.base()) )