In C++20, why may a range's end() return a different type from its begin(), and what is that end type called?
answer
- end is a test, not a position
- range-for changed in C++17
- sentinel_for in C++20
- unreachable_sentinel and default_sentinel
basics
~20 sA sentinel. A C++20 range is an iterator plus a sentinel, any type that can be compared with the iterator, so the end can be a condition such as reaching a null character or a count rather than a known position.
solid answer
~40 sClassic algorithms take two iterators of the same type, which forces you to know the end position up front: a null-terminated string needs a `strlen` pass before `std::find`. C++20 generalizes a range to an iterator `I` and a **sentinel** `S` that satisfies `std::sentinel_for<S, I>`: `S` is semiregular and `it == s` is valid. The sentinel can encode "next character is `'\0'`", "n elements consumed" (`std::counted_iterator` with `std::default_sentinel`) or "never" (`std::unreachable_sentinel`, whose `==` always returns false). Range-for has accepted different `begin` and `end` types since C++17; the `std::ranges` algorithms take an `(I, S)` pair. The catch is legacy code: `std::find(r.begin(), r.end(), x)` needs both arguments of one type, so it rejects a range whose end is a sentinel.
code
cpp · 35 lines#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
struct NulSentinel {};
struct CharIter {
using value_type = char;
using difference_type = std::ptrdiff_t;
const char* p = nullptr;
char operator*() const { return *p; }
CharIter& operator++() { ++p; return *this; }
CharIter operator++(int) { auto t = *this; ++p; return t; }
bool operator==(const CharIter&) const = default;
friend bool operator==(CharIter it, NulSentinel) { return *it.p == '\0'; }
};
static_assert(std::forward_iterator<CharIter>);
static_assert(std::sentinel_for<NulSentinel, CharIter>);
int main() {
const char* title = "Ballad";
CharIter first{title};
auto it = std::ranges::find(first, NulSentinel{}, 'l'); // no strlen pass first
std::cout << (it.p - title) << '\n'; // 2
int samples[] = {3, 0, 7};
auto zero = std::ranges::find(samples, std::unreachable_sentinel, 0); // caller promises a 0 exists
std::cout << (zero - samples) << '\n'; // 1
std::counted_iterator c(samples, 2);
for (; c != std::default_sentinel; ++c) std::cout << *c << ' ';
std::cout << '\n';
}go deeper
Recall the word sentinel: an end marker that you compare an iterator with, which in C++20 need not be an iterator itself.
Explain std::sentinel_for, why a null-terminated string or a counted range fits it better than an end iterator, and that range-for accepts it since C++17.
Recognize a mismatch where legacy algorithms reject a range with a sentinel end, and decide between ranges algorithms, a common-range adaptor, or computing an end iterator.
Decide whether a codebase's own containers and generators expose sentinel-based ranges, given the gains in single-pass and unbounded sequences against compatibility with pre-C++20 algorithms.
## The problem with an end iterator Before C++20, every standard algorithm took a range as two iterators of the **same type**: `std::find(first, last, value)`. The end had to be a position you could name in advance. For a vector that is free, but many sequences do not know where they end until they get there: - a null-terminated C string, which ends where a `'\0'` appears; - input read from a stream, which ends when the read fails; - "the next n elements" of some longer sequence; - a search you know will succeed, where checking for the end is wasted work. To use classic algorithms on a C string, you first call `strlen` to compute an end pointer, scanning the data twice. ## Sentinels: the end as a condition C++20 generalizes the definition. A **range** is an iterator plus a **sentinel**: an object that marks the end and can be compared with the iterator. The sentinel may be the same type as the iterator, as it is for every standard container, or a different type entirely. The standard expresses this with the concept `std::sentinel_for<S, I>`, which in C++20 and C++23 requires: 1. `I` is an iterator (`std::input_or_output_iterator`); 2. `S` is `std::semiregular`, so it can be default-constructed and copied; 3. `i == s` is a valid comparison yielding a boolean, in both directions. The C++26 draft adds a fourth requirement, that `S` is not an integer-like type, so a count can never be mistaken for a sentinel. A range is empty when `begin == end`; otherwise the iteration runs until an incremented iterator compares equal to the sentinel. For a C string the sentinel type is often an empty struct, and `it == sentinel` simply tests `*it == '\0'`. No length is ever computed. ## The standard sentinels | name | meaning | |---|---| | `std::default_sentinel` | the end of a sequence that knows when it is exhausted, such as `std::counted_iterator` after n steps | | `std::unreachable_sentinel` | never: `operator==` always returns `false`, so the algorithm performs no end check | | a container's `end()` | the familiar case where the sentinel is an iterator of the same type | `std::unreachable_sentinel` is a deliberate trade. If the caller can prove the value is present, for example a buffer that always ends with a terminator, the loop saves one comparison per step. If the proof is wrong, the algorithm runs off the data, which is undefined behaviour. ## Where sentinels are accepted - **Range-based `for`.** Since C++17 the range-for rewrite declares the begin and end variables separately, so `begin()` and `end()` may return different types. Compiled as C++14, Apple clang accepts such a loop only as an extension and warns that different return types are a C++17 extension. - **The `std::ranges` algorithms.** They take an iterator-sentinel pair, or a whole range: `std::ranges::find(first, sentinel, value)`. - **Classic algorithms do not.** `std::find`, `std::sort` and the rest still require one iterator type for both ends. A range whose `end()` returns a sentinel is called a non-common range, and passing `r.begin(), r.end()` to a classic algorithm fails to compile. The options are to use the ranges algorithm, to adapt the range with a view that produces a common range, or to compute an end iterator. ## Writing a sentinel for your own iterator A minimal C string range needs an iterator with `value_type`, `difference_type`, prefix and postfix `++`, `*` and `==` between iterators, plus an empty sentinel struct with an `operator==` against the iterator. With those, `static_assert(std::forward_iterator<CharIter>)` and `static_assert(std::sentinel_for<NulSentinel, CharIter>)` both pass, and the type works with `std::ranges::find` and range-for. In C++20, defining `operator==` alone is enough: the compiler synthesizes `!=` and the reversed argument order. ## Why this matters in practice Sentinels show up whenever a sequence's end is a condition rather than a position: parsers walking a null-terminated buffer, network code reading until a delimiter, generators producing values until some state is reached, and bounded windows over longer data with `std::counted_iterator`. They also explain a class of compile errors when C++20 ranges meet older code that assumes `begin()` and `end()` share a type. ## What interviewers listen for Name the term, sentinel, and the concept, `std::sentinel_for`. Explain that it lets the end be a test instead of a precomputed position, give a concrete case such as a C string or `std::counted_iterator` with `std::default_sentinel`, mention that range-for accepted it in C++17, and know that classic algorithms reject such ranges. Adding the `std::unreachable_sentinel` trade-off is a mark of depth.
- What happens if a range with a sentinel end is compiled as C++14 and used in a range-for?Before C++17 the range-for rewrite required `begin` and `end` to have the same type; C++17 declares them as two separate variables, so they may differ. Apple clang with `-std=c++14` accepts it only as an extension and warns: 'begin' and 'end' returning different types ('CharIter' and 'NulSentinel') is a C++17 extension.
- When is std::unreachable_sentinel safe to use?Only when the caller can prove the search ends inside the data, for example a buffer that always ends with a known terminator. Its `operator==` returns false for any iterator, so the algorithm never checks bounds; if the value is absent it reads past the buffer, which is undefined behaviour. It trades one comparison per step for a precondition.
- Says begin() and end() must always return the same type
- Thinks a sentinel is just another name for the end() iterator
- Believes std::unreachable_sentinel adds a bounds check
- Expects std::find(r.begin(), r.end(), x) to accept any C++20 range
- Says sentinels were introduced by range adaptors and only work with views
Assumes C++20 for std::sentinel_for, std::default_sentinel and std::unreachable_sentinel; range-for has accepted different begin and end types since C++17.