Why Does a Push_Back on an Std::List Change a Reverse Iterator Initialized with Rbegin

Why does a push_back on an std::list change a reverse iterator initialized with rbegin?

The standard says that iterators and references remain valid during an insert. It doesn't say anything about reverse iterators. :-)

The reverse_iterator returned by rbegin() internally holds the value of end(). After a push_back() this value will obviously not be the same as it was before. I don't think the standard says what it should be. Obvious alternatives include the previous last element of the list, or that it stays at the end if that is a fixed value (like a sentinel node).

---

Technical details: The value returned by rend() cannot point before begin(), because that is not valid. So it was decided that rend() should contain the value of begin() and all other reverse iterators be shifted one position further. The operator* compensates for this and accesses the correct element anyway.

First paragraph of 24.5.1 Reverse iterators says:

Class template reverse_iterator is an iterator adaptor that iterates from the end of the sequence defined
by its underlying iterator to the beginning of that sequence. The fundamental relation between a reverse
iterator and its corresponding iterator i is established by the identity:

&*(reverse_iterator(i)) == &*(i - 1).

std list reverse-iterator's past-the-end iterator gets invalidated, if list is empty

Reverse iterators are not the container's iterators, not directly. They are defined in terms of the container's iterators.

In general, a reverse iterator has a base "normal" iterator. The element the reverse iterator refers to is not the element the base one refers to, but rather the element before the base iterator's element. (This is because there is no iterator one-before-begin)

rend is reverse(begin). On an empty list, begin==end. So rend is reverse(end).

When you insert into the list, no iterators are invalidated. Your copy of rend remains reverse(end), but calling rend again returns reverse(begin). And they are no longer equal.

To me, this seems surprising but I would assume it is compliant. The C++ standard could not reasonably avoid this "bug".

why do values returned by std::end() change as the container changes, but not with std::begin()?

To get the last element's iterator, it can be achieved by: std::prev(std::end(l)). Your code stored the end iterator and dereference it, it's UB.

And the doc of std::list::end:

Returns an iterator to the element following the last element of the
container, This element acts as a placeholder; attempting to access it
results in undefined behavior.

For std::begin, we get the iterator to the first element of the container, it's safe the deference it and gets the corresponding element.

#include <iostream>
#include <list>
#include <unordered_map>

int main() {
  std::list<int> l;
  std::unordered_map<int, std::list<int>::iterator> listItems;

  for (int i = 0; i < 5; i++) {
    l.push_back(i);
    listItems[i] = std::prev(std::end(l));
  }

  for (int i = 0; i < 5; i++) std::cout << *(listItems[i]) << " ";
  std::cout << std::endl;
}

Online demo

Why did my pointer to a std::vector's element change its value after push_back()?

push_back invalidates pointers, references, and iterators to existing elements.

That's because of the contiguity guarantee. push_back increases the size of the vector, and if the capacity of the internal buffer isn't sufficient to hold a new item immediately after the existing ones, in order to maintain contiguity, they all have to be moved to a new larger buffer.

If you want to continue accessing an element after future calls to push_back, your options are to access it by index in a vector, or use a container with no contiguity guarantee, such as std::list.

Inserting to std::list using reverse iterator changes the value of the original reverse iterator

I would avoid using reverse iterators (in general, and in particular for anything other than a sequential transversal). Forward and reverse iterators work differently, in the case of a forward iterator into a list, the iterator tracks the node that you access through operator*, but in the reverse case the iterator tracks the next element in the list. The act of dereferencing a reverse iterator obtains the predecessor of the node referred by the iterator and extracts the value from that. Graphically (f is a forward iterator, r is a reverse iterator)

  f
1 2 4
    r

Both the forward iterator f and the reverse iterator r will yield 2 when dereferenced, but the node they track is different. When you insert using r you insert between 2 and 4, but the underlying iterator is left pointing to the node holding the 4:

  f
1 2 3 4
      r

Now if you dereference r, the same process as above applies. The predecessor of the current node is obtained, and the value printed, except that now the predecessor of 4 is 3 and that is what you get.

Is this expected behaviour. If so how can reverse iterator be used to insert items to a list (Or is it useless in this regard)?

Yes, this is expected behavior. How can a reverse iterator be used to insert items to a list? Understanding how it works.

---

Related Topics