До появления ranges для сортировки вектора нужно было делать примерно такое:

// C++17 and earlier
std::sort(v.begin(), v.end());
// C++20
std::ranges::sort(v)

То есть функция сортировки принимала два итератора и сортировала то, что между ними. При этом перегрузки, куда можно просто передать вектор, не существовало.

Почему так было сделано? Идея такая: форма, которая принимает два итератора более общая, и если нужно сортировать некоторый подотрезок, она нам подходит. А функция, которая принимает вектор целиком — более частный случай.

При этом короткой формы, которая принимала просто какой-то контейнер, не было. Основной причиной являлось то, что добавление новых перегрузок к стандартным алгоритмам, приводило к тому, что нужно было добавлять много дополнительных SFINAE проверок. В примерах к концептам мы видели, что при создании большого количества перегрузок, они начинают конфликтовать. Поэтому нужно следить, чтобы в каждом случае выбиралась ровно одна перегрузка (см. пример с assign).

Опыт использования стандартных алгоритмов показал, что от них ещё хочется какие-то вещи (например, добавление новых перегрузок), и многие из них откладывались из-за того, что нужно было сломать совместимость, или нужны были мощные SFINAE ограничения и тому подобное. Это всё откладывалось и, когда в языке появились концепты — алгоритмы стандартной библиотеки переделали.

Ренджи — набор удобных утилит. Помимо того, что писать приходится меньше, мы также можем комбинировать алгоритмы друг с другом, получая таким образом легко читаемый (пример про парсинг m3u файла) и эффективный код.

P.S.: На лекции был пример реализации подсчёта и сортировки слов по частоте вхождения в виде 6строчника на баше и 10страничной реализации Кнута на Паскале.

В стандарте используется подмножество библиотеки range-v3. Eric Niebler (автор пропозала) предлагает три способа обращения с ренжами:

D-like ranges

Ренжи в D хранят набор ещё не обработанных элементов, т.е. они постоянно сужаются. С такими ренжами сложно работать когда алгоритму нужно похранить позицию, например find. В D эта проблема решается кучей функций. Ещё такие ренжи плохи в алгоритмах типа partial_sort (там нужны три итератора).

Position-based ranges

position это что-то типа итератора, который ссылается не на сам элемент, а на позицию в каком-то контейнере, который нужно явно передать. С такими ренжами легко сделать проверку на границу диапазона. Ещё такие ренжи решают проблему времени жизни - алгоритму нельзя передать протухший итератор. Минус такого подхода в том что нам придется ввести кучу дополнительной машинерии для interop-а обычных итераторов и positions.

Iterator-based ranges

Ренж просто держит два итератора под капотом. Так были построены почти все библиотеки для ренжей. Так сделали и в стандарте.

Range и Views

Помимо алгоритмов с ренджами, в стандарт вошли views. Например, мы можем получить "reverse view" вектора, т.е. обертку, которая ссылается на вектор и при доступе к i-му элементу выдаёт n-i-1-й и т.п. Ещё можно создавать ленивые последовательности и делать над ними преобразования:

total = accumulate(iota(1)
                  | transform([](int x) { return x * x; })
                  | take(10), 0)

Рассмотрим пример:

void foo(std::vector<int32_t> const& v) {
    auto r = v | std::views::reverse;
}

Возникают вопросы: является ли r копируемым? Если да, то за какое время? Может ли r жить дольше, чем v? Можно ли делать *r.begin() = 42? Изменится ли при этом исходный v? Изменятся ли ответы, если вместо v передать rvalue? Для ответа на эти вопросы, дадим соответствующие определения.

В первом приближении можно думать, что view — это легковесный объект, который на что-то ссылается и имеет специальные свойства, т.е. он не копирует внутрь себя ничего (обычно).

Что такое std::ranges::range? Всё что угодно, если для него определены операции begin(r), end(r).

std::ranges::view -- Это range, но с дополнением, что он movable за O(1). Чтобы тип считался view, его нужно "пометить", специализировав переменную enable_view.

Примеры view: ref_view, owning_view, filter_view, ...

Примеры range, которые не являются view: vector, array.

Рассмотрим pipe-line:

void foo(std::vector<int32_t>& v) {
    return v 
        | std::views::filter(is_divisible_by_3) 
        | std::views::transform(square)
        | std::ranges::to<std::vector<int32_t>>();
}

Он работает следующим образом: filter, transform принимают view и возвращают view. Если в начале передали не view, то его превращают в нужный тип специальным образом: sts::views::all(v).

Превращает он по следующим правилам (упрощённо):

Если r уже view, то его же и возвращает.
Если r — lvalue, то возвращается ref_view<R> (view, который просто ссылается на контейнер).
(*) Если r — rvalue, то возвращается owning_view<R> (view, который хранит сам объект). Со звёздочкой, потому что появилось только в C++20 DR (Defect Report) P2415. До появления owning_view<R> требовалось, чтобы non-view range был lvalue.

Sentinel

В C++03 существовали такие "ренжи" (пара итераторов), размера, которого мы не знаем наперёд (потенциально, он может быть бесконечным), например, std::istream, std::regex_iterator. У них на месте end() стояла заглушка.

Для них совершенно не принципиально, чтобы begin() и end() имели один и тот же тип. Наоборот, это может усложнять код разными проверками вида is_end(). Однако практически все стандартные алгоритмы требуют, чтобы итераторы по типу совпадали. Хотелось бы ослабить это ограничение: многие алгоритмы могли бы спокойно работать, даже если begin и end имеют различные типы.

В C++ ranges разрешили иметь разные типы начала и конца: в качестве begin передаётся всё так же итератор, а вот объект, который показывает, где конец, стали называть sentinel. Проверка на конец спрятана в операторе сравнения между итератором и sentinel (range-based for мог работать с sentinel уже в C++17). И это позволяет нам иметь, например, бесконечные ренжи:

auto naturals = std::views::iota(1);
auto begin_ = naturals.begin();
auto end_ = naturals.end(); // std::unreachable_sentinel_t

Про данный тип окончания можно прочитать здесь: unreachable_sentinel_t.

Изменения в категориях итераторах

В С++ 98 были следующие категории итераторов:

InputIterator
OutputIterator
ForwardIterator
BidirectionalIterator
RandomAccessIterator

Для Forward,Bidirectional и RandomAccess итераторов есть требования, чтобы они могли возвращать ссылку на элемент и это все хорошо работает пока мы не получим следующий пример с view:

transform(v, [](int x){return x * x;})

Тут мы возвращаем новое значение, мы уже не можем возвращать ссылку. В Boost такое предложили разделять 2 свойства итераторов: Traversal -- то как мы проходим по диапазону, Access -- то как мы обращаемся к элементу.

В С++20 не стали выделять 2 этих свойства, для Forward,Bidirectional и RandomAccess решили ослабить требования к итераторам, для них убрали требования уметь возвращать ссылку, оставили только Traversal требования. При этом добавили ещё одну категорию: ContigousIterator -- он означает что элементы лежат в памяти непрерывным блоком, позволяет делать всякие операции.

Итого куча разных итераторов могут предоставить более сильные категории.

См. C++20 iterator concepts

Алгоритмы на ренжах

На каждый алгоритм в STL сделали дополнительные перегрузки: одна для двух итераторов с sentinel-ами, а вторая для ренжа. Для "трёхногих" алгоритмов сделали по четыре доп. перегрузки. Если захочется поиспользовать, то в std::ranges лежат улучшенные перегрузки старых алгоритмов для ренжей, алгоритмы для view лежат std::ranges::views.

C++ course notes

Ranges

Мотивация