Уже скоро появится стандарт C++20, в который, скорее всего, добавят концепцию интервалов (ranges), однако мало кто знает, что они из себя представляют и с чем их едят. Доступных широкой аудитории русскоязычных источников про этого зверя мне найти не удалось, вследствие чего в данной статье я бы хотел подробнее про него рассказать, базируясь на лекции Arno Schödl «From Iterators to Ranges: The Upcoming Evolution Of the STL» с конференции Meeting C++ 2015-го года. Я постараюсь сделать эту статью максимально понятной для тех, кто впервые сталкивается с этим понятием, и одновременно расскажу про всевозможные фишки вроде интервальных адаптеров для тех, кто с этим понятием уже знаком и хочет узнать больше.
На момент написания данной статьи можно выделить три основные библиотеки, реализующие интервалы:
Первая библиотека, по сути, прародитель данной концепции (что неудивительно, ведь чего только нет в собрании библиотек Boost :) ). Вторая — библиотека Эрика Ниблера (Eric Niebler), про неё будет рассказано позднее. И наконец, последняя библиотека, как нетрудно догадаться, написана компанией think-cell, которая, можно сказать, развила и усовершенствовала Boost.Range.
Для тех, кто ещё не знаком с понятием интервала, определим это нетривиальное понятие как то, что имеет начало и конец (пара итераторов).
Давайте теперь рассмотрим следующую задачу: имеется вектор, необходимо удалить из него все повторяющиеся элементы. В рамках текущего стандарта мы решали бы её так:
При этом мы указываем имя вектора аж 6 раз! Однако, используя концепцию интервалов (объединив итераторы на начало и конец вектора в один объект), можно написать в разы проще, указав искомый вектор лишь единожды:
В стандарте С++11 добавили range-based цикл for и универсальный доступ к началу/концу контейнеров, и в последнем стандарте С++17 ничего нового, связанного с интервалами, добавлено не было.
Остановимся теперь на упомянутой ранее библиотеке Range V3. Эрик Ниблер, её создатель, в качестве своего домашнего проекта создал техническую спецификацию интервалов (Range's Technical Specification), модифицировав библиотеку algorithm для поддержки интервалов. Это выглядит примерно так:
На его сайте есть некое превью того, что он хочет стандартизировать, это и есть Range V3.
В первую очередь, контейнеры (vector, string, list etc.), ведь у них есть начало и конец. Ясно, что контейнеры владеют своими элементами, то есть, когда мы обращаемся к контейнерам, то мы обращаемся и ко всем их элементам. Аналогично при копировании и объявлении постоянной (глубокое копирование и константность). Во вторую очередь, views могут так же считаться интервалами. Views — это просто пара итераторов, указывающих соответственно на начало и конец. Вот их простейшая реализация:
Views, в свою очередь, лишь ссылаются на элементы, поэтому копирование и константность ленивые (это не влияет на элементы).
На этом изобретатели интервалов останавливаться не стали, ведь иначе эта концепция была бы довольно бесполезной. Поэ��ому ввели такое понятие, как интервальные адаптеры (range adaptors).
Рассмотрим следующую задачу: пусть дан вектор int'ов, в котором нужно найти первый элемент, равный 4:
Теперь же представим, что тип вектора не int, а какая-то сложная самописная структура, но в которой есть int, и задача всё та же:
Ясно, что эти два кода схожи по семантике, однако значительно различаются по синтаксису, ведь в последнем случае пришлось вручную писать функцию, пробегающую по полю int. Но если использовать трансформирующий адаптер (transform adaptor), то всё выглядит гораздо более лаконично:
По сути, трансформирующий адаптор «трансформирует» нашу структуру, создавая вокруг поля int класс-обёртку. Ясно, что указатель указывает на поле id, но если бы мы хотели, чтобы он указывал на всю структуру, то необходимо дописать в конце .base(). Эта команда инкапсулирует поле, из-за чего указатель может пробегать по всей структуре:
Вот примерная реализация трансформирующего адаптера (он состоит из итераторов, каждый из которых имеет собственный функтор):
А если бы в прошлой задаче нам нужно было найти не первый такой элемент, а «профильтровать» всё поле int'ов на наличие таких элементов? В таком случае мы использовали бы фильтрующий адаптер (filter adaptor):
Заметим, что фильтр при этом выполняется лениво, во время итераций.
А вот его наивная реализация (примерно такая реализована в Boost.Range):
Как мы можем заметить, здесь требуется уже два итератора вместо одного, как это было в трансформирующем адаптере. Второй итератор необходим для того, чтобы случайно не выйти за границы контейнера при итерациях.
Хорошо, а как выглядит итератор от tc::filter(tc::filter(tc::filter(...)))?
В рамках реализации выше это выглядит так:
Очевидно, это ужасно неэффективно.
Давайте подумаем, как можно оптимизировать этот адаптер. Идея Эрика Ниблера состояла в том, что мы должны положить общую информацию (функтор и указатель на конец) в объект-адаптер, и тогда мы можем хранить ссылку на этот объект-адаптер и искомый итератор
Тогда в рамках такой реализации тройной фильтр будет выглядеть примерно так:
Это всё ещё не идеально, хотя и в разы быстрее предыдущей реализации.
Теперь рассмотрим решение компании think-cell. Они ввели так называемую концепцию индексов (index concept) для решения этой проблемы. Индекс — это такой итератор, который выполняет все те же операции, что и обычный итератор, но делает это, обращаясь к интервалам.
Покажем, как можно совместить индекс с обычным итератором.
Ясно, что обычный итератор можно тоже считать индексом. В обратную же сторону совместимость можно реализовать например так:
Тогда тройной фильтр будет реализован супер-эффективно:
В рамках такой реализации алгоритм будет работать быстро вне зависимости от глубины фильтра.
Теперь посмотрим, как работают интервалы с lvalue и rvalue контейнерами:
Range V3 и think-cell ведут себя одинаково с lvalue. Предположим, что у нас есть такой код:
Тут у нас есть заранее объявленный вектор, который лежит в памяти (lvalue), и нам нужно создать интервал и потом как-то с ним работать. Мы создаём view с помощью view::filter или tc::filter и становимся счастливыми, никаких ошибок нет, и этот view мы потом можем использовать например, в any_of.
Однако, если бы наш вектор ещё не был в памяти (например, если мы его только создавали), и перед нами стояла бы та же задача, то мы попробовали бы написать так и столкнулись с ошибкой:
Почему же она возникла? View будет висячей ссылкой на rvalue из-за того, что мы создаём вектор и напрямую кладём в filter, то есть в фильтре будет rvalue ссылка, которая потом будет указывать на что-то неизвестное, когда компилятор перейдёт на следующую строку, и возникнет ошибка. Для того, чтобы решить эту проблему, в Range V3 придумали action:
Action делает всё сразу, то есть просто берёт вектор, фильтрует по предикату и кладёт в интервал. Однако минус в том, что это больше не является ленивым, и think-cell постарались исправить этот минус.
В think-cell сделали так, что там вместо view создаётся контейнер:
В результате мы не сталкиваемся с подобной ошибкой, потому что в их реализации фильтр собирает rvalue контейнер вместо ссылки, поэтому это происходит лениво. В Range V3 так делать не захотели, потому что боялись, что будут ошибки из-за того, что фильтр ведёт себя то как view, то как контейнер, однако think-cell убеждены в том, что программисты понимают, как ведёт себя фильтр, а большая часть ошибок возникает именно из-за этой «ленивости».
Обобщим понятие интервалов. На самом деле, существуют и интервалы без итераторов. Они называются generator ranges (генераторные интервалы). Предположим, что у нас есть GUI виджет (элемент интерфейса), и мы вызываем виджет перемещения. У нас есть окно, которое просит переместить её виджет, также у нас есть кнопка в list box, и другое окно тоже должно листнуть свои виджеты, то есть мы вызываем traverse_widgets, который соединяет элементы в функтор (можно сказать, есть функция перечисления, где вы подключаете функтор, и функция перечисляет в этот функтор все элементы, которые у него есть).
Это чем-то напоминает интервал виджетов, но здесь нет никаких итераторов. Писать их непосредственно было бы неэффективно и, прежде всего, очень сложно. В таком случае, можно сказать, что такие конструкции тоже считаются интервалами. Тогда для таких случаев имеет место быть использование полезных интервальных методов, таких как any_of:
think-cell стараются реализовывать методы так, чтобы они имели одинаковый интерфейс для всех видов интервалов:
Используя tc::enumerate, разница между интервалами скрывается, так как такая реализация придерживается концепции внутреннего итерирования (о том, в чём заключаются концепции external и internal iteration, рассказано подробнее на лекции), однако в такой реализации есть и свои минусы, а именно, std::any_of останавливается, как только встречается true. Такую проблему пытаются решать, например, добавляя исключения (так называемые прерываемые генераторные интервалы).
Я ненавижу range-based цикл for, потому что он мотивирует людей писать его везде где нужно и где не нужно, из-за чего зачастую ухудшается лаконичность кода, например, люди пишут это:
вместо этого:
Библиотеки с ranges
На момент написания данной статьи можно выделить три основные библиотеки, реализующие интервалы:
Первая библиотека, по сути, прародитель данной концепции (что неудивительно, ведь чего только нет в собрании библиотек 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
В рамках реализации выше это выглядит так:
Слабонервным не смотреть!
m_func3
m_it3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
m_itEnd3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
Очевидно, это ужасно неэффективно.
Range V3
Давайте подумаем, как можно оптимизировать этот адаптер. Идея Эрика Ниблера состояла в том, что мы должны положить общую информацию (функтор и указатель на конец) в объект-адаптер, и тогда мы можем хранить ссылку на этот объект-адаптер и искомый итератор
*m_rng
m_it
Тогда в рамках такой реализации тройной фильтр будет выглядеть примерно так:
Тык
m_rng3
m_it3
m_rng2
m_it2
m_rng1
m_it1
Это всё ещё не идеально, хотя и в разы быстрее предыдущей реализации.
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 );
