C++11 reverse iterator with while loop

I know the code isn't good practice, so the question is not about that. I just want to understand how the following example works. Notice I don't do anything with the iterator when I call remove, so when the loop goes to the next iteration how is it pointing to the next element?

#include <string>
#include <list>
#include <algorithm>
#include <iostream>

class Obj;
std::list<Obj> objs;

class Obj
{
public:
  Obj(const std::string& name, int age)
  : name_(name), age_(age)
  {}

  std::string name()
  {
    return name_;
  }

  int age()
  {
    return age_;
  }
private:
  std::string name_;
  int age_;
};


void remove(const std::string& name)
{
  auto it = find_if(objs.begin(), objs.end(),[name] (Obj& o) { return (o.name() == name); });
  if (it != objs.end())
  {
    std::cout << "removing " << it->name() << std::endl;
    objs.erase(it);
  }
}

int main()
{
  objs.emplace_back("bob", 31);
  objs.emplace_back("alice", 30);
  objs.emplace_back("kevin", 25);
  objs.emplace_back("tom", 45);
  objs.emplace_back("bart", 37);
  objs.emplace_back("koen", 48);
  objs.emplace_back("jef", 23);
  objs.emplace_back("sara", 22);

  auto it = objs.rbegin();
  while (it != objs.rend())
  {

   std::cout << it->name() << std::endl;

   if (it->name() == "tom")
   {
      remove(it->name()); //notice I don't do anything to change the iterator
   }
   else
   {
     ++it;
   }
  }
  return 0;
}

Following is the output:

sara
jef
koen
bart
tom
removing tom
kevin
alice
bob
728x90

2 Answers C++11 reverse iterator with while loop

You invalidate the iterator by removing the object it addresses (regardless of whether you use the value of it for that purpose). If you try to access it after that, the behaviour is undefined (read: anything can happen, like the same it jumping to the next element, or your program crashing). You can't rely on this on any other behaviour.

7 months ago

My other answer was not right. The observed behaviour is due to the implementation of reverse_iterator. From cppreference:

std::reverse_iterator is an iterator adaptor that reverses the direction of a given iterator. In other words, when provided with a bidirectional iterator, std::reverse_iterator produces a new iterator that moves from the end to the beginning of the sequence defined by the underlying bidirectional iterator.

For a reverse iterator r constructed from an iterator i, the relationship &*r == &*(i-1) is always true (as long as r is dereferenceable); thus a reverse iterator constructed from a one-past-the-end iterator dereferences to the last element in a sequence.

(emphasis mine). See also [reverse.iterator].

OK, what this means for us: when a reverse iterator it points to "tom", it actually wraps around a forward iterator to the next element, "bart". When you derefer it, it takes an element preceding the wrapped iterator, i.e., one before "bart", which indeed is "tom".

When you remove "tom", the wrapped iterator does not change. (Neither it is invalidated.) It still points to "bart". When you derefer the reverse iterator, it looks for what precedes "bart", which now is "kevin".

This means you don't really cause undefined behaviour. You would if you called remove("bart") at line 60.

7 months ago