C++11 reverse iterator with while loop

Question

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

Your code has undefined behaviour because you alter the list which invalidates all iterators. Also please don't use global variables. — Swordfish, Sep 07 '18 at 09:28
@Swordfish "*you alter the list wich invalidates all iterators*" - No it doesn't; ["References and iterators to the erased elements are invalidated. Other references and iterators are not affected."](https://en.cppreference.com/w/cpp/container/list/erase). — luk32, Sep 07 '18 at 09:31
@DanielLangr it does and becomes invalid. Sorry for the wrong wording of my previous comment, not \*all\* iterators become invalid. — Swordfish, Sep 07 '18 at 09:34
@Swordfish Ye, only the one removed, though it's being referenced at the next step, so it's enough. — luk32, Sep 07 '18 at 10:20
@luk32 "so it's enough" what is that supposed to mean? after `remove(it->name());` accessing it by `it->name()` is undefined behaviour. Strictly also `it != objs.rend()` is. — Swordfish, Sep 07 '18 at 10:28
It's enough invoke UB. I meant it doesn't have to invalidate everything. Invalidating the element which is meant to go away is enough to invoke UB. I find it way more subtle than breaking "whole container" (i.e. all iterators). — luk32, Sep 07 '18 at 10:35

The Vee · Answer 1 · 2018-09-07T12:44:43.830

3

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.

edited Sep 07 '18 at 12:44

answered Sep 07 '18 at 09:31

The Vee

11,420
5
27
60

Ok, I get that it is invalidated. Could you elaborate on 'like the same it jumping to the next element'. How would this happen if it is invaled? I have tested this for over a 100000 times and the next iteration always just prints "kevin" which is the next element. – rinn2883 Sep 07 '18 at 09:43
That was just a rephrasal of what you said (or observed) happened. It's not an example I came up with. – The Vee Sep 07 '18 at 09:45
I don't know much about the behavior of invalidated iterators. If it is invalid shouldn't it be similar like calling a function on a nullptr or is that a wrong assumption? – rinn2883 Sep 07 '18 at 09:48
calling an invalid iterator is undefined behaviour. In your case the implementation of your standard library happens to leave the iterator pointing at the correct item so works but you can' t rely on that. – Alan Birtles Sep 07 '18 at 10:02
Don't make _any_ assumption, @rinn. There is no deterministic behaviour. It's pure chance that comes down to how the container and iterators happen to be implemented, or what's in your memory, or how many cats are within your city's official limits. Just code to spec and don't worry about it. – Lightness Races in Orbit Sep 07 '18 at 10:24
Iterator invalidation rules: https://stackoverflow.com/q/6438086/560648 – Lightness Races in Orbit Sep 07 '18 at 10:26

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

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.

C++11 reverse iterator with while loop

2 Answers2