What's the difference between a sentinel and an end iterator?

Question

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?

Answer 1

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 ranges¹ 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.

---

¹ 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.

Answer 2

Sentinels and end iterators are similar in that they mark the end of a range. They differ in how that end is detected; either you're testing the iterator itself, or you're testing the data value at the iterator. If you're already performing tests on the data, a sentinel can allow your algorithm to finish "for free" without any additional tests. This can either simplify the code, or make it faster.

A very common sentinel is the zero byte that is used to mark the end of a string. There's no need to keep a separate iterator for the end of the string, it can be determined as you work with the characters of the string itself. The downside of this convention is that a string cannot contain a zero character.

Note that I wrote this answer before reading the proposal in the link; this is the classic definition of a sentinel which may not agree with the definition proposed there.