Краткий ответ

Это обеспечивается концепцией sentinel в библиотеке C++20 Ranges. Алгоритму больше не требуется, чтобы начало и конец диапазона имели один тип: достаточно, чтобы итератор умел перемещаться по элементам, а sentinel — сравниваться с ним для определения окончания.

Исторический контекст

Традиционные алгоритмы STL обычно принимали пару итераторов одного типа: first и last. Это удобно для контейнеров, но ограничивает работу с диапазонами, где конец нельзя или невыгодно представить обычным итератором того же типа.

В C++20 ranges разделили понятия итератора и границы диапазона. Такой подход позволяет описывать, например, последовательность до специального символа, заданное число элементов или поток, у которого нет обычного заранее сформированного конечного итератора.

Постановка проблемы

Начальный объект диапазона должен поддерживать операции, необходимые алгоритму: разыменование и продвижение. Конечная граница при этом может быть лишь маркером остановки и не обязана указывать на существующий элемент или поддерживать все операции итератора.

Если искусственно привести такие объекты к одному типу, можно получить лишние обёртки, усложнить интерфейс или потерять эффективность. Неверное сравнение итератора с sentinel приведёт к тому, что алгоритм не сможет корректно определить конец диапазона.

Подробное решение

В ranges-алгоритмах используется пара iterator, sentinel. Для неё должна выполняться концепция sentinel_for: sentinel можно сравнивать с итератором, чтобы определить, достигнута ли граница. Сам sentinel обычно не разыменовывается и не продвигается.

Итератор отвечает за доступ к текущему элементу и переход к следующему, а sentinel — только за условие завершения. Поэтому их типы могут различаться. Если дополнительно доступно вычисление расстояния между ними, выполняется более сильная концепция sized_sentinel_for, позволяющая эффективнее получать размер диапазона.

Например, std::counted_iterator считает оставшееся количество элементов, а std::default_sentinel_t служит специальной границей:

#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
    int data[] = {4, 7, 9};
    auto first = std::counted_iterator(data, 3);
    auto last = std::default_sentinel;
    auto it = std::ranges::find(first, last, 7);
    std::cout << *it;
}

Здесь first и last имеют разные типы. Алгоритм продвигает counted_iterator, пока тот не сравняется с default_sentinel, и затем ищет значение. В отличие от старых алгоритмов, ranges-алгоритмы специально проектировались для такой модели.

Диапазонный интерфейс std::ranges::find(range, value) скрывает пару границ за объектом диапазона. При этом сохраняются требования к корректности: итератор и sentinel должны быть совместимы для сравнения, а время работы всё равно зависит от категории итератора и самого алгоритма.

Ситуация из практики

В библиотеке обрабатывается буфер, в котором нужно просмотреть только первые n элементов. Вариант с созданием отдельного конечного итератора может быть неудобен для абстрактного источника данных, особенно если источник представлен адаптером или потоковой последовательностью.

Можно использовать обычные алгоритмы, предварительно завернув итератор и границу в общий тип. Плюс такого подхода — совместимость со старым кодом; минусы — дополнительная обёртка и менее выразительный интерфейс.

Более подходящее решение — std::counted_iterator вместе с std::default_sentinel и ranges-алгоритмом. Оно явно выражает ограниченную последовательность, не требует фиктивного конечного итератора и позволяет алгоритму работать с разными типами границ.

Что кандидаты часто упускают

Обязан ли sentinel быть разыменуемым?

Нет. Sentinel — это граница, а не элемент диапазона. Алгоритм сравнивает текущий итератор с sentinel, но не обращается к значению через sentinel. Разыменовываться должен только итератор, пока он не достиг границы.

Всегда ли разные типы границ означают отсутствие информации о размере?

Нет. Разные типы не исключают возможность вычислить расстояние. Если пара удовлетворяет sized_sentinel_for, между итератором и sentinel можно получить расстояние, что позволяет некоторым алгоритмам работать эффективнее.

Могут ли старые алгоритмы STL напрямую принимать разные типы конца диапазона?

Как правило, нет: классические алгоритмы используют один параметр типа для first и last. Для них можно применить адаптер, например std::common_iterator, который объединяет разные типы в один. Однако ranges-алгоритмы обычно предпочтительнее, поскольку поддерживают модель iterator-sentinel непосредственно.