Reference invalidation after applying reverse_iterator on a custom made iterator

reverse_iterator does not work with so-called “stashing iterators”, iterators that returns references to things within themselves. The operator* of reverse_iterator makes a copy of the wrapped iterator, decrements it, and returns the result of dereferencing the copy. Hence, if dereferencing iterator returns a reference to something inside itself, the reference will become dangling.

An attempt was made in the C++11 specification to make it work, but it turns out that it’s impossible to implement without adding massive overhead* for non-stashing iterators, so the specification was reverted to the C++03 version.

* To support “stashing iterators”, an additional data member must be added that stores the decremented current iterator, doubling the size of reverse_iterator; and then some form of synchronization must be used since operator * is const – and so must be simultaneously callable from multiple threads without causing a data race – but must modify this additional data member. That’s a lot of overhead to add to all reverse_iterators for such an uncommon use case.

Leave a Comment