While reading Eric Niebler's range proposal,
I've come across the term sentinel as replacement for the end iterator.
I'm having a difficult time understanding the benefits of sentinel over an end iterator.
Could someone provide a clear example of what sentintel brings to the table that cannot be done with standard iterator pairs?
"A sentinel is an abstraction of a past-the-end iterator. Sentinels are Regular types that can be used to denote the end of a range. A sentinel and an iterator denoting a range shall be EqualityComparable. A sentinel denotes an element when an iterator i compares equal to the sentinel, and i points to that element." -- N4382
I think sentinels work as functions in determining the end of a range, instead of just the position?
Sentinel simply allows the end iterator to have a different type.
The allowed operations on a past-the-end iterator are limited, but this is not reflected in its type. It is not ok to * a .end() iterator, but the compiler will let you.
A sentinel does not have unary dereference, or ++, among other things. It is generally as restricted as the weakest iterators one past the end iterator, but enforced at compile time.
There is a payoff. Often detecting the end state is easier than finding it. With a sentinel, == can dispatch to "detect if the other argument is past the end" at compile time, instead of run time.
The result is that some code that used to be slower than the C equivalent now compiles down to C level speed, such as copying a null terminated string using std::copy. Without sentinels, you either had to scan to find the end before the copy, or pass in iterators with a bool flag saying "I am the end sentinel" (or equivalent), and check it on ==.
There are other similar advantages when working with counting based ranges. In addition, some things like zip ranges1 become easier to express (the end zip sentinel could hold both source sentinels, and return equal if either sentinel does: zip iterators either only compare the first iterator, or compare both).
Another way of thinking about it is that algorithms tend to not use the full richness of the iterator concept on the parameter passed as the past the end iterator, and that iterator is handled way differently in practice. Sentinel means that the caller can exploit that fact, which in turn lets the compiler exploit it easier.
1 A zip range is what you get when you start with 2 or more ranges, and "zip" them together like a zipper. The range is now over tuples of the individual range elements. Advancing a zip iterator advances each of the "contained" iterators, and ditto for dereferencing and comparing.