Интервалы: грядущая эволюция C++

Уже скоро появится стандарт C++20, в который, скорее всего, добавят концепцию интервалов (ranges), однако мало кто знает, что они из себя представляют и с чем их едят. Доступных широкой аудитории русскоязычных источников про этого зверя мне найти не удалось, вследствие чего в данной статье я бы хотел подробнее про него рассказать, базируясь на лекции Arno Schödl «From Iterators to Ranges: The Upcoming Evolution Of the STL» с конференции Meeting C++ 2015-го года. Я постараюсь сделать эту статью максимально понятной для тех, кто впервые сталкивается с этим понятием, и одновременно расскажу про всевозможные фишки вроде интервальных адаптеров для тех, кто с этим понятием уже знаком и хочет узнать больше.

Библиотеки с ranges

На момент написания данной статьи можно выделить три основные библиотеки, реализующие интервалы:

• Boost.Range
• Range V3
• think-cell public library

Первая библиотека, по сути, прародитель данной концепции (что неудивительно, ведь чего только нет в собрании библиотек Boost :) ). Вторая — библиотека Эрика Ниблера (Eric Niebler), про неё будет рассказано позднее. И наконец, последняя библиотека, как нетрудно догадаться, написана компанией think-cell, которая, можно сказать, развила и усовершенствовала Boost.Range.

Почему интервалы это наше будущее?

Для тех, кто ещё не знаком с понятием интервала, определим это нетривиальное понятие как то, что имеет начало и конец (пара итераторов).

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

std::vector<T> vec=...;
std::sort( vec.begin(), vec.end() );
vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() );

При этом мы указываем имя вектора аж 6 раз! Однако, используя концепцию интервалов (объединив итераторы на начало и конец вектора в один объект), можно написать в разы проще, указав искомый вектор лишь единожды:

tc::unique_inplace( tc::sort(vec) );

Что из интервалов есть на данный момент в рамках текущего стандарта?

В стандарте С++11 добавили range-based цикл for и универсальный доступ к началу/концу контейнеров, и в последнем стандарте С++17 ничего нового, связанного с интервалами, добавлено не было.

for ( int& i : <range_expression> ) {
 ...
}

std::begin/end(<range_expression>)

Будущее интервалов

Остановимся теперь на упомянутой ранее библиотеке Range V3. Эрик Ниблер, её создатель, в качестве своего домашнего проекта создал техническую спецификацию интервалов (Range's Technical Specification), модифицировав библиотеку algorithm для поддержки интервалов. Это выглядит примерно так:

namespace ranges {
    template< typename Rng, typename What > 
    decltype(auto) find( Rng && rng, What const& what ) {
        return std::find( 
            ranges::begin(rng),
            ranges::end(rng),
            what 
        );
    }
}

На его сайте есть некое превью того, что он хочет стандартизировать, это и есть Range V3.

Что же всё-таки может считаться range?

В первую очередь, контейнеры (vector, string, list etc.), ведь у них есть начало и конец. Ясно, что контейнеры владеют своими элементами, то есть, когда мы обращаемся к контейнерам, то мы обращаемся и ко всем их элементам. Аналогично при копировании и объявлении постоянной (глубокое копирование и константность). Во вторую очередь, views могут так же считаться интервалами. Views — это просто пара итераторов, указывающих соответственно на начало и конец. Вот их простейшая реализация:

template<typename It> 
struct iterator_range {
    It m_itBegin;
    It m_itEnd;
    It begin() const {
        return m_itBegin; 
    }
    It end() const { 
        return m_itEnd;
    } 
};

Views, в свою очередь, лишь ссылаются на элементы, поэтому копирование и константность ленивые (это не влияет на элементы).

Интервальные адаптеры

На этом изобретатели интервалов останавливаться не стали, ведь иначе эта концепция была бы довольно бесполезной. Поэтому ввели такое понятие, как интервальные адаптеры (range adaptors).

Трансформирующий адаптер

Рассмотрим следующую задачу: пусть дан вектор int'ов, в котором нужно найти первый элемент, равный 4:

std::vector<int> v;
auto it = ranges::find(v, 4);

Теперь же представим, что тип вектора не int, а какая-то сложная самописная структура, но в которой есть int, и задача всё та же:

struct A {
    int id;
    double data; 
};
std::vector<A> v={...};
auto it = ranges::find_if(
    v,
    [](A const& a) { return a.id == 4; }
);

Ясно, что эти два кода схожи по семантике, однако значительно различаются по синтаксису, ведь в последнем случае пришлось вручную писать функцию, пробегающую по полю int. Но если использовать трансформирующий адаптер (transform adaptor), то всё выглядит гораздо более лаконично:

struct A { 
    int id;
    double data; 
};
std::vector<A> v={...}; 
auto it = ranges::find(
    tc::transform(v, std::mem_fn(&A::id)), 
    4);

По сути, трансформирующий адаптор «трансформирует» нашу структуру, создавая вокруг поля int класс-обёртку. Ясно, что указатель указывает на поле id, но если бы мы хотели, чтобы он указывал на всю структуру, то необходимо дописать в конце .base(). Эта команда инкапсулирует поле, из-за чего указатель может пробегать по всей структуре:

auto it = ranges::find(
    tc::transform(v, std::mem_fn(&A::id)), 
    4).base();

Вот примерная реализация трансформирующего адаптера (он состоит из итераторов, каждый из которых имеет собственный функтор):

template<typename Base, typename Func> 
struct transform_range {
    struct iterator { 
    private:
        Func m_func; // в каждом итераторе
        decltype( tc::begin(std::declval<Base&>()) ) m_it; 
    public:
        decltype(auto) operator*() const { 
            return m_func(*m_it);
        }
        decltype(auto) base() const {
            return (m_it); 
        }
        ... 
    };
};

Фильтрующий адаптер

А если бы в прошлой задаче нам нужно было найти не первый такой элемент, а «профильтровать» всё поле int'ов на наличие таких элементов? В таком случае мы использовали бы фильтрующий адаптер (filter adaptor):

tc::filter( v,
    [](A const& a) { return 4 == a.id; } 
);

Заметим, что фильтр при этом выполняется лениво, во время итераций.

А вот его наивная реализация (примерно такая реализована в Boost.Range):

template<typename Base, typename Func> 
struct filter_range {
    struct iterator { 
    private:
        Func m_func; // функтор и ДВА итератора
        decltype( ranges::begin(std::declval<Base&>()) ) m_it;
        decltype( ranges::begin(std::declval<Base&>()) ) m_itEnd;
    public:
        iterator& operator++() {
            ++m_it;
            while( m_it != m_itEnd && !static_cast<bool>(m_func(*m_it)) )
                ++m_it; 
            return *this;
        }
        ... 
    };
};

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

Немного оптимизаций

Хорошо, а как выглядит итератор от tc::filter(tc::filter(tc::filter(...)))?

Boost.Range

В рамках реализации выше это выглядит так:


Очевидно, это ужасно неэффективно.

Range V3

Давайте подумаем, как можно оптимизировать этот адаптер. Идея Эрика Ниблера состояла в том, что мы должны положить общую информацию (функтор и указатель на конец) в объект-адаптер, и тогда мы можем хранить ссылку на этот объект-адаптер и искомый итератор
*m_rng
m_it

Тогда в рамках такой реализации тройной фильтр будет выглядеть примерно так:


Это всё ещё не идеально, хотя и в разы быстрее предыдущей реализации.

think-cell, концепция индексов

Теперь рассмотрим решение компании think-cell. Они ввели так называемую концепцию индексов (index concept) для решения этой проблемы. Индекс — это такой итератор, который выполняет все те же операции, что и обычный итератор, но делает это, обращаясь к интервалам.

template<typename Base, typename Func>
struct index_range {
    ...
    using Index = ...;
    Index begin_index() const;
    Index end_index() const;
    void increment_index( Index& idx ) const; 
    void decrement_index( Index& idx ) const; 
    reference dereference( Index& idx ) const;
    ...
};

Покажем, как можно совместить индекс с обычным итератором.

Ясно, что обычный итератор можно тоже считать индексом. В обратную же сторону совместимость можно реализовать например так:

template<typename IndexRng>
struct iterator_for_index {
    IndexRng* m_rng;
    typename IndexRng::Index m_idx;

    iterator& operator++() {
        m_rng.increment_index(m_idx); 
        return *this;
    }
    ... 
};

Тогда тройной фильтр будет реализован супер-эффективно:

template<typename Base, typename Func> 
struct filter_range {
    Func m_func; 
    Base& m_base;

    using Index = typename Base::Index;
    void increment_index( Index& idx ) const {
        do {
            m_base.increment_index(idx);
        } while ( idx != m_base.end_index() 
            && !m_func(m_base.dereference_index(idx)) );
    }
};

template<typename IndexRng>
struct iterator_for_index {
    IndexRng* m_rng;
    typename IndexRng::Index m_idx; 
    ...
};

В рамках такой реализации алгоритм будет работать быстро вне зависимости от глубины фильтра.

Интервалы с lvalue и rvalue контейнерами

Теперь посмотрим, как работают интервалы с lvalue и rvalue контейнерами:

lvalue

Range V3 и think-cell ведут себя одинаково с lvalue. Предположим, что у нас есть такой код:

auto rng = view::filter(vec, pred1);
bool b = ranges::any_of(rng, pred2);

Тут у нас есть заранее объявленный вектор, который лежит в памяти (lvalue), и нам нужно создать интервал и потом как-то с ним работать. Мы создаём view с помощью view::filter или tc::filter и становимся счастливыми, никаких ошибок нет, и этот view мы потом можем использовать например, в any_of.

Range V3 и rvalue

Однако, если бы наш вектор ещё не был в памяти (например, если мы его только создавали), и перед нами стояла бы та же задача, то мы попробовали бы написать так и столкнулись с ошибкой:

auto rng = view::filter(create_vector(), pred1); // не скомпилируется
bool b = ranges::any_of(rng, pred2);

Почему же она возникла? View будет висячей ссылкой на rvalue из-за того, что мы создаём вектор и напрямую кладём в filter, то есть в фильтре будет rvalue ссылка, которая потом будет указывать на что-то неизвестное, когда компилятор перейдёт на следующую строку, и возникнет ошибка. Для того, чтобы решить эту проблему, в Range V3 придумали action:

auto rng = action::filter(create_vector(), pred1); // теперь скомпилируется
bool b = ranges::any_of(rng, pred2);

Action делает всё сразу, то есть просто берёт вектор, фильтрует по предикату и кладёт в интервал. Однако минус в том, что это больше не является ленивым, и think-cell постарались исправить этот минус.

think-cell и rvalue

В think-cell сделали так, что там вместо view создаётся контейнер:

auto rng = tc::filter(creates_vector(), pred1); 
bool b = ranges::any_of(rng, pred2);

В результате мы не сталкиваемся с подобной ошибкой, потому что в их реализации фильтр собирает rvalue контейнер вместо ссылки, поэтому это происходит лениво. В Range V3 так делать не захотели, потому что боялись, что будут ошибки из-за того, что фильтр ведёт себя то как view, то как контейнер, однако think-cell убеждены в том, что программисты понимают, как ведёт себя фильтр, а большая часть ошибок возникает именно из-за этой «ленивости».

Генераторные интервалы

Обобщим понятие интервалов. На самом деле, существуют и интервалы без итераторов. Они называются generator ranges (генераторные интервалы). Предположим, что у нас есть GUI виджет (элемент интерфейса), и мы вызываем виджет перемещения. У нас есть окно, которое просит переместить её виджет, также у нас есть кнопка в list box, и другое окно тоже должно листнуть свои виджеты, то есть мы вызываем traverse_widgets, который соединяет элементы в функтор (можно сказать, есть функция перечисления, где вы подключаете функтор, и функция перечисляет в этот функтор все элементы, которые у него есть).

template<typename Func>
void traverse_widgets( Func func ) {
    if (window1) {
        window1->traverse_widgets(std::ref(func));
    }
    func(button1);
    func(listbox1);
    if (window2) {
        window2->traverse_widgets(std::ref(func));
    }
}

Это чем-то напоминает интервал виджетов, но здесь нет никаких итераторов. Писать их непосредственно было бы неэффективно и, прежде всего, очень сложно. В таком случае, можно сказать, что такие конструкции тоже считаются интервалами. Тогда для таких случаев имеет место быть использование полезных интервальных методов, таких как any_of:

mouse_hit_any_widget=tc::any_of(
    [] (auto func) { traverse_widgets(func); },
    [] (auto const& widget) {
        return widget.mouse_hit();
    }
);

think-cell стараются реализовывать методы так, чтобы они имели одинаковый интерфейс для всех видов интервалов:

namespace tc {
    template< typename Rng >
    bool any_of( Rng const& rng ) {
        bool bResult = false;
        tc::enumerate( rng, [&](bool_context b) {
            bResult = bResult || b;
        } );
        return bResult;
    }
}

Используя tc::enumerate, разница между интервалами скрывается, так как такая реализация придерживается концепции внутреннего итерирования (о том, в чём заключаются концепции external и internal iteration, рассказано подробнее на лекции), однако в такой реализации есть и свои минусы, а именно, std::any_of останавливается, как только встречается true. Такую проблему пытаются решать, например, добавляя исключения (так называемые прерываемые генераторные интервалы).

Заключение

Я ненавижу range-based цикл for, потому что он мотивирует людей писать его везде где нужно и где не нужно, из-за чего зачастую ухудшается лаконичность кода, например, люди пишут это:

bool b = false; 
for (int n : rng) {
    if ( is_prime(n) ) {
        b = true;
        break;
    }
}

вместо этого:

bool b = tc::any_of( rng, is_prime );