How to erase a pair element in a list

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

error: no matching function for call to 'std::list<std::pair<int, int> >::erase(std::reverse_iterator<std::_List_iterator<std::pair<int, int> > >&)'
li.erase(it);

If the li.erase(it) is replaced by li.remove(*it), the code works fine. However, all the value will be removed., and the algorithm become O(n²), instead of O(n), right?

Possible duplicate of [How to call erase with a reverse iterator](http://stackoverflow.com/questions/1830158/how-to-call-erase-with-a-reverse-iterator) — Alan Stokes, Dec 04 '15 at 23:59

score 2 · Answer 1 · answered Dec 04 '15 at 22:48

Erasing while iterating is a bad, bad idea. If it is no longer in the list, what will ++it do? Good question! I don't know, but it's not what you want unless you got unlucky. Why is it unlucky if the program works? Because it doesn't, and next time it might do something completely different.

So pretty much all of the loop-based iterate and delete approaches that seem to work (li.remove(*it) and li.erase( --(it.base()) ) actually don't.

Normally I pitch the erase-remove idiom to solve that problem, but the reverse iterator makes this a mess if you try to use C++'s built-in tools. Plus in this case the answer to remove_if is always true.

For the problem posed above, don't even try. Instead, print li.back() and then li.pop_back() until the list is empty.

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

score 0 · Answer 2 · edited May 23 '17 at 12:19

You can replace li.erase(it) with li.erase(it.base()).

std::list.erase does not allow a reverse_iterator as an argument, so you first need to convert the reverse_iterator into an iterator.

And you're correct, as far as I can tell, about the O(n^2) and O(n) analysis.

EDIT:

Actually, according to this similar answer: How to call erase with a reverse iterator

What you should really do is li.erase( --(it.base()) )

How to erase a pair element in a list

2 Answers2