What does the C++ standard says for algorithms when first <= last is not fulfilled?

Question

What does the official C++ standard says about the algorithms when the condition first <= last is not fulfilled, first and last being the iterators passed to one of the standard algorithms?

I see three possibities:

• The algorithms are required to check the condition so that if it not fullfilled, the algorithm do not do anything
• The algorithms are required to throw an exception
• This is undefined behaviour, so... anything can happen

I am puzzled, because in the algorithms description I don't see a requires clause concerning first and last.

EDIT1: This was a simplification of the question. A more exact version is "what happen to the algorithms when last is not reachable from first by successively applying operator++?

EDIT2: I am asking this question because I am implementing an specialization of std::reverse and I was wondering whether I should check this condition, or if I can allow the function to do something completely wrong when last is not reachable from first?

Answer 1

The text you're looking for is in the iterators section (emphasis mine):

[iterator.requirements.general]/7-8

An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j. If j is reachable from i, they refer to elements of the same sequence.

Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i,i) is an empty range; in general, a range [i,j) refers to the elements in the data structure starting with the element pointed to by i and up to but not including the element pointed to by j. Range [i,j) is valid if and only if j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.

The standard explicitly says here that passing an invalid (not fulfilled) range to standard algorithms results in undefined behaviour. The algorithms themselves do specify ranges in the [first, last) format.

Note that /7 disallows swapping the arguments for random access iterators because you cannot apply ++first over and over to reach last.