Уже скоро появится стандарт 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 );