Common vs Non-Common Ranges in C++

In modern C++ (introduced in C++20), the Ranges library categorizes iterable sequences primarily into common ranges and non-common ranges based on the types returned by their beginning and ending markers. A common range requires begin() and end() to yield the exact same type, maintaining backward compatibility with traditional iterator-pair designs. In contrast, a non-common range allows end() to return a distinct type known as a sentinel. This article examines the mechanical differences between these two models, why sentinels were introduced, and how to convert non-common ranges to common ranges when interfacing with legacy APIs.

The Core Difference: Iterators vs. Sentinels

In pre-C++20 code, iterating over an element sequence required two iterators of the identical type:

template <typename Iterator>
void process(Iterator begin, Iterator end);

C++20 generalized this model. A range is now defined by an iterator returned by begin() and a sentinel returned by end(). The sentinel does not have to be an iterator; it only needs to support equality comparison (== and !=) with the iterator type to signal when iteration should terminate.

Common Ranges

A range R is a common range if its iterator type and sentinel type are identical. Formally, it satisfies the std::ranges::common_range concept:

template <class T>
concept common_range = ranges::range<T> && 
                       std::same_as<ranges::iterator_t<T>, ranges::sentinel_t<T>>;

All standard containers from C++98 to C++17 (such as std::vector, std::list, std::array, and std::string) are common ranges because their .begin() and .end() member functions return the same iterator type.

std::vector<int> vec{1, 2, 3};
auto it = vec.begin();   // std::vector<int>::iterator
auto sent = vec.end();   // std::vector<int>::iterator
// decltype(it) is identical to decltype(sent) -> Common Range

Non-Common Ranges

A range is a non-common range when its sentinel type differs from its iterator type:

decltype(std::ranges::begin(r)) != decltype(std::ranges::end(r))

The sentinel serves purely as an endpoint predicate rather than an iterator that traverses or points to a distinct memory address.

auto view = std::views::iota(0) 
          | std::views::take_while([](int n) { return n < 5; });

auto it = view.begin(); // Returns an internal iota iterator
auto sent = view.end(); // Returns a sentinel containing the predicate
// decltype(it) != decltype(sent) -> Non-Common Range

Why Non-Common Ranges Exist

The separation of iterator and sentinel types provides significant performance and functional benefits:

1. Elimination of Pre-computation (Lazy Evaluation): When reading a null-terminated C-string, traditional iterators require calculating strlen() beforehand to construct the end iterator. A sentinel simply checks if *it == '\0', scanning the string in a single pass without prior traversal.
2. Infinite and Unbounded Sequences: Ranges like std::views::iota(0) can produce values indefinitely. A sentinel can pair with a runtime condition (e.g., std::views::take_while) without needing a materialized ending element.
3. Optimized Code Generation: Sentinels often carry no state (empty structs), allowing compilers to optimize loop boundary checks better than state-heavy end iterators.

Adapting Non-Common to Common Ranges

Because legacy algorithms (such as std::sort or custom iterator-based templates) require both markers to have identical types, passing a non-common range directly to these functions results in a compilation error.

To solve this, C++20 provides std::views::common. This range adaptor wraps a non-common range and converts it into a common range by producing a unified iterator type that internally knows how to check for the sentinel.

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    auto is_even = [](int i) { return i % 2 == 0; };
    
    // take_while creates a non-common range
    auto non_common = std::views::iota(0) 
                    | std::views::take_while([](int i) { return i < 10; });

    // static_assert fails: non_common is not a common_range
    // static_assert(std::ranges::common_range<decltype(non_common)>);

    // Convert to a common range
    auto common_view = non_common | std::views::common;

    static_assert(std::ranges::common_range<decltype(common_view)>);

    // Now compatible with legacy iterator-pair algorithms
    std::vector<int> target;
    target.insert(target.end(), common_view.begin(), common_view.end());
}

Summary Comparison