CODEWITHSUNDEEP
c++listiteratorstd-pair
Milo Lu
Milo Lu

Reputation: 3366

How to erase a pair<int,int> element in a list

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(n2), instead of O(n), right?

Upvotes: 0

Views: 7396

Answers (2)

user4581301
user4581301

Reputation: 33952

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

Upvotes: 2

Michael Oliver
Michael Oliver

Reputation: 1412

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

Upvotes: 0

Related Questions