How to erase reverse_iterator correctly when erase and push

I have a list container, which looks like:

std::list<int> l = {1,2,3,4,5,6,7,8};

i often erase elements, so i choose std::list.

but, i also want to find the elemnt in O(1), so i record the reverse_iterator.

For Example:

  l.push_back(9);
  auto s = l.rbegin();  // record the iterator of 9, in order to erase it in the future fastly.
  cout << *s << endl;
  l.push_back(10);
  auto s2 = l.rbegin();

but when i erase like this:

l.erase(std::next(s).base());  // s the iterator of 9, in my brain

i want to erase 9, but actually, it erase 10.

I have two questions:

why i should use next? actually my *s can get the element, which is different with .end().

how can i make the erase happen in my previous saved iterator?

CodePudding user response：

Since the iterator of the list is a bidirectional iterator, instead of using reverse_iterator, you can just use --l.end() to get the last valued iterator.

std::list<int> l = {1,2,3,4,5,6,7,8};
l.push_back(9);
auto s = --l.end(); // record the iterator of 9
l.push_back(10);
l.erase(s); // erase the iterator of 9

Demo.

CodePudding user response：

l.rbegin().base() == l.end(), which is not the position of the last element, but the end of the list. and push_back again won't affect this existing iterator, it is still pointing to the end of the list.

Then std::next(l.rbegin()).base() == l.end() - 1, which now is pointing to the last element 10.

So if you want to remember the position of the 9, you better use a normal iterator instead of a reverse one, or, use a reverse iteractor whose base pointing to 9, and that should be auto s = std::next(l.rbegin()), and erase it as l.erase(s.base()).

the rule is &*r == &*(i-1)