Decrementing an off the end iterator

Question

I was reading today about how for containers that support bidirectional iteration, this piece of code is valid:

Collection c(10, 10);
auto last = --c.end();
*last;

That got me thinking, is it required that when submitting a pair of bidirectional iterators [beg, end) to an algorithm in the STL that --end is defined? If so, should the result be dereferenceable?

ie

void algo(T beg, T end){
    //...
    auto iter = --end;
    //...
    *iter;
} 

Answer 1

If the algorithm requires a range defined by bidirectional iterators first and last, then --last needs to be valid under the same conditions that ++first does -- namely that the range isn't empty. The range is empty if and only if first == last.

If the range isn't empty, then --last evaluates to an iterator that refers to the last element in the range, so *--last indeed also needs to be valid.

That said, there aren't all that many standard algorithms that require specifically a bidirectional iterator (and don't require random-access). prev, copy_backward, move_backward, reverse, reverse_copy, stable_partition, inplace_merge, [prev|next]_permutation.

If you look at what some of those do, you should see that typically the algorithm does decrement the end-of-range iterator and dereference the result.

As James says, for containers the function end() returns an iterator by value. There is no general requirement that for iterators that --x should be a well-formed expression when x is an rvalue of the type. For example, pointers are bidirectional iterators, and a function declared as int *foo(); returns a pointer by value, and --foo() is not a well-formed expression. It just so happens that for the containers you've looked at in your implementation, end() returns a class type which has operator-- defined as a member function, and so the code compiles. It also works since the container isn't empty.

Be aware that there is a difference in this respect between:

auto last = --c.end();

vs.

auto last = c.end();
--last;

The former decrements an rvalue, whereas the latter decrements an lvalue.

Answer 2

You read wrong. The expression --c.end() is never authorized. If the iterator isn't at least bidirectional, it is, in fact, expressedly forbidden, and requires a compiler error. If the collection is empty, it is undefined behavior. And in all other cases, it will work if it compiles, but there is no guarantee that it will compile. It failed to compile with many early implementations of std::vector, for example, where the iterator was just a typedef to a pointer. (In fact, I think formally that it is undefined behavior in all cases, since you're violating a constraint on a templated implementation. In practice, however, you'll get what I just described.)

Arguably, because it isn't guaranteed, a good implementation will cause it to fail to compile, systematically. For various reasons, most don't. Don't ask me why, because it's incredibly simple to get it to fail systematically: just make the operator-- on the iterator a free function, rather than a member.

EDIT (additional information):

The fact that it isn't required is probably a large part of the motivation behind std::next and std::prev in C++11. Of course, every project I've worked on has had them anyway. The correct way to write this is:

prev( c.end() );

And of course, the constraints that the iterator be bidirectional or better, and that the container not be empty, still hold.