[Программирование, C++, Алгоритмы] Ленивые итераторы и диапазоны в C++
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++.
Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку.
Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator).
Данная публикация — это краткий ликбез о том, что такое ленивые итераторы и диапазоны, зачем они нужны и как ими пользоваться.
Содержание
Итератор
Начнём с простого. Что вообще такое итератор?
Понять суть концепции довольно легко. Сам по себе итератор — это обобщение указателя. При этом главное, что нужно знать — это два способа взаимодействия с итератором:
- Продвижение (например, ++i или i + n);
- Разыменование (*i).
И в эти взаимодействия мы можем внедряться и переопределять их так, как нам нужно.
Ленивость
Внедрение в операции над диапазонами может быть сколь угодно хитрым и сложным (простые примеры я привёл ниже). Ленивость же состоит в том, что нет никаких промежуточных результатов. Все вычисления происходят только тогда, когда вызываются операции разыменования или продвижения.
Определение 1. Итератор e достижим из итератора b, если существует схема f продвижения итератора b такая, что f(b) = e.
Допустим, у нас есть некая последовательность элементов, заданная двумя итераторами: на начало и конец этой последовательности (при этом конец достижим из начала). Теперь мы преобразуем оба этих итератора каким-то способом и получаем два новых итератора. Если преобразование итераторов корректно, т.е. образ конца первой последовательности достижим из образа начала первой последовательности, то мы получили новую последовательность. При этом длина и элементы новой последовательности могут отличаться от длины и элементов исходной.
В этом и состоит ленивость — мы получили новую последовательность без изменений в старой. Мы не трогали хранимые объекты, а только переопределили способ их отображения и обхода по ним.
Transform Iterator
Простой пример внедрения в операцию разыменования — это boost::transform_iterator.
Он оборачивает некий исходный итератор и при разыменовании возвращает результат преобразования над разыменованным значением исходного итератора.
Таким образом, каждому итератору i типа I мы поставили в соответствие итератор j типа J такой, что *j = f(*i).
auto v = std::vector{1, 2, 3, 4};
// 2 4 6 8
auto i = v.begin();
auto t = boost::make_transform_iterator(i, [] (auto x) {return x * 2;});
assert(*t == 2);
++t;
assert(*t == 4);
...
Filter Iterator
Пример внедрения в продвижение — это boost::filter_iterator.
Он оборачивает продвижение, причём относительно "хитрым" образом. Он выбрасывает из рассмотрения все элементы исходной последовательности, которые не удовлетворяют заданному предикату. Единственное отличие — обёрнутый итератор сразу же позиционируется на нужном элементе, если у исходной последовательности есть префикс, все элементы которого не удовлетворяют предикату.
Таким образом, мы "выбросили" из исходной последовательности итераторы i такие, что p(*i) == false, и в результирующей последовательности, для каждого итератора j типа J выполняется p(*j) == true.
auto v = std::vector{1, 2, 3, 4};
// ^ ^
auto i = v.begin();
auto f = boost::make_filter_iterator(i, [] (auto x) {return x % 2 == 0;});
assert(*i == 2);
++i;
assert(*i == 4);
Ленивые диапазоны
Итератор — это обобщение указателя. Поэтому итератор, как и указатель, сам по себе не знает, когда нужно остановиться. Имея только итератор на начало последовательности, нельзя сказать, где конец этой последовательности. Поэтому мы объединяем пару итераторов — начало и конец — в диапазон.
При этом диапазон — это уже более сложная конструкция, и у него другой интерфейс, похожий на интерфейс контейнеров:
- Взятие итераторов на начало и конец (r.begin(), r.end());
- Взятие первого элемента диапазона (r.front());
- Проверка на пустоту (r.empty()).
Разница только в том, что диапазон не владеет элементами, которые он задаёт. Хотя бы потому что канонический диапазон — это просто пара итераторов (к примеру, std::equal_range).
Важно отметить, что диапазон принято задавать полуинтервалом [b, e). Это значит, что итератор-начало b указывает на первый элемент последовательности, а итератор-конец e указывает на элемент после последнего. Таким образом, когда мы приходим в итератор-конец, мы точно знаем, что последовательность закончилась.
Transform Range
На основе преобразующих итераторов можно собрать диапазон (см. boost::iterator_range).
auto v = std::vector{...};
auto l = [] (auto x) {return x * x;};
auto tb = boost::make_transform_iterator(v.begin(), l);
auto te = boost::make_transform_iterator(v.end(), l);
auto tr = boost::make_iterator_range(tb, te);
for (auto x: tr)
{
...
}
Или проще (см. boost::transformed):
auto v = std::vector{...};
auto tr = boost::adaptors::transform(v, [] (auto x) {return x * x;});
for (auto x: tr)
{
...
}
В C++20 это std::transform_view:
auto v = std::vector{...};
auto tr = std::ranges::views::transform(v, [] (auto x) {return x * x;});
for (auto x: tr)
{
...
}
Stride
Другой пример ленивого диапазона — это boost::strided.
Он оборачивает исходный диапазон так, что в новом диапазоне остаются только кратные позиции исходного диапазона.
auto v = std::vector{1, 2, 3, 4};
// ^ ^
auto s = boost::adaptors::strided(v, 2);
assert(s.front() == 1);
s.advance_begin();
assert(s.front() == 3);
Компоновка
После того, как мы научились создавать диапазоны, нам не составит никакой сложности скомбинировать их в цепочку.
Например, если мы хотим для некоей последовательности чисел:
- возвести их в квадрат,
- взять только каждый четвёртый элемент,
- и оставить только чётные числа,
то можно это сделать так:
auto v = std::vector{...};
auto r = v | transformed([] (auto x) {return x * x;})
| strided(4)
| filtered([] (auto x) {return x % 2 == 0;});
Или, в C++20:
auto v = std::vector{...};
auto r = v | std::views::transformed([] (auto x) {return x * x;})
// | strided(4) // В C++20 такого нет.
| std::views::filtered([] (auto x) {return x % 2 == 0;});
Ещё раз хочу подчеркнуть, что этот код не производит никаких вычислений. Он только сохраняет "схемы" работы с диапазоном, а настоящие вычисления будут происходить только во время продвижения или разыменования обёрнутого итератора.
Суть итераторов и диапазонов
Помимо C++, в некоторых языках программировани также существует концепция под названием "итератор", но эта концепция зачастую имеет какой-то свой, альтернативный смысл.
К примеру, "итераторы" в языках Java и C# знают свой предел. С точки зрения языка C++ это, скорее, диапазоны.
В C++ итератор — это именно обобщение указателя. По сути указатель — это самый сильный (или наиболее конкретный) итератор, причём иерархия следующая:
- Однопроходный итератор (input iterator);
- Однонаправленный итератор (forward iterator);
- Двунаправленный итератор (bidirectional iterator);
- Итератор произвольного доступа (random access iterator);
- Непрерывный итератор (contiguous iterator);
- Указатель.
Диапазон же можно рассматривать именно как пару итераторов (даже если это на самом деле не так). Диапазон уже знает, где у него конец, может накладывать дополнительную логику на операции с итераторами и т.д. Также диапазон может быть сконвертирован обратно в итераторы (потому что диапазон — это пара итераторов, как уже было сказано выше).
Такое разделение на итераторы и диапазоны помогает создавать универсальные, гибкие и эффективные интерфейсы для операций над последовательностями.
Один из примеров создания сложной операции над диапазонами я привёл в статье Ленивые операции над множествами в C++.
Ссылки
===========
Источник:
habr.com
===========
Похожие новости:
- [PHP, Программирование] Работа с заказом через админку OpenCart, взгляд изнутри
- [JavaScript, Анализ и проектирование систем, Алгоритмы, Обработка изображений, Машинное обучение] Мы создали Web приложение для определения лиц и масок для Google Chrome (перевод)
- [Программирование, GTK+, Разработка под Linux] Пишем онлайн-радио на языке Vala
- [Программирование] Факториал 100 через рекурсию процесса в Camunda
- [Разработка веб-сайтов, Программирование, HTML, Лайфхаки для гиков] 5 HTML-трюков, о которых никто не говорит (перевод)
- [C++, C] Макросы в С и С++
- [Разработка веб-сайтов, JavaScript, Программирование, Проектирование и рефакторинг, ReactJS] Фреймворк-независимое браузерное SPA (перевод)
- [Программирование, .NET, Алгоритмы, C#, Математика] Compilation of math functions into Linq.Expression
- [Отладка, Программирование микроконтроллеров, Прототипирование] Arduino + max30102 + ЦОС = SpO2
- [Разработка веб-сайтов, PHP, Программирование, Учебный процесс в IT, Карьера в IT-индустрии] Курсы PHP-программирования в Минске. Куда пойти учиться?
Теги для поиска: #_programmirovanie (Программирование), #_c++, #_algoritmy (Алгоритмы), #_s++ (с++), #_iteratory (итераторы), #_diapazony (диапазоны), #_lenivye_vychislenija (ленивые вычисления), #_programmirovanie (
Программирование
), #_c++, #_algoritmy (
Алгоритмы
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 19:22
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++. Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку. Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator).
Содержание Итератор Начнём с простого. Что вообще такое итератор?  Понять суть концепции довольно легко. Сам по себе итератор — это обобщение указателя. При этом главное, что нужно знать — это два способа взаимодействия с итератором:
 И в эти взаимодействия мы можем внедряться и переопределять их так, как нам нужно. Ленивость Внедрение в операции над диапазонами может быть сколь угодно хитрым и сложным (простые примеры я привёл ниже). Ленивость же состоит в том, что нет никаких промежуточных результатов. Все вычисления происходят только тогда, когда вызываются операции разыменования или продвижения. Определение 1. Итератор e достижим из итератора b, если существует схема f продвижения итератора b такая, что f(b) = e. Допустим, у нас есть некая последовательность элементов, заданная двумя итераторами: на начало и конец этой последовательности (при этом конец достижим из начала). Теперь мы преобразуем оба этих итератора каким-то способом и получаем два новых итератора. Если преобразование итераторов корректно, т.е. образ конца первой последовательности достижим из образа начала первой последовательности, то мы получили новую последовательность. При этом длина и элементы новой последовательности могут отличаться от длины и элементов исходной.  В этом и состоит ленивость — мы получили новую последовательность без изменений в старой. Мы не трогали хранимые объекты, а только переопределили способ их отображения и обхода по ним. Transform Iterator Простой пример внедрения в операцию разыменования — это boost::transform_iterator. Он оборачивает некий исходный итератор и при разыменовании возвращает результат преобразования над разыменованным значением исходного итератора.  Таким образом, каждому итератору i типа I мы поставили в соответствие итератор j типа J такой, что *j = f(*i). auto v = std::vector{1, 2, 3, 4};
// 2 4 6 8 auto i = v.begin(); auto t = boost::make_transform_iterator(i, [] (auto x) {return x * 2;}); assert(*t == 2); ++t; assert(*t == 4); ... Filter Iterator Пример внедрения в продвижение — это boost::filter_iterator. Он оборачивает продвижение, причём относительно "хитрым" образом. Он выбрасывает из рассмотрения все элементы исходной последовательности, которые не удовлетворяют заданному предикату. Единственное отличие — обёрнутый итератор сразу же позиционируется на нужном элементе, если у исходной последовательности есть префикс, все элементы которого не удовлетворяют предикату.  Таким образом, мы "выбросили" из исходной последовательности итераторы i такие, что p(*i) == false, и в результирующей последовательности, для каждого итератора j типа J выполняется p(*j) == true. auto v = std::vector{1, 2, 3, 4};
// ^ ^ auto i = v.begin(); auto f = boost::make_filter_iterator(i, [] (auto x) {return x % 2 == 0;}); assert(*i == 2); ++i; assert(*i == 4); Ленивые диапазоны Итератор — это обобщение указателя. Поэтому итератор, как и указатель, сам по себе не знает, когда нужно остановиться. Имея только итератор на начало последовательности, нельзя сказать, где конец этой последовательности. Поэтому мы объединяем пару итераторов — начало и конец — в диапазон. При этом диапазон — это уже более сложная конструкция, и у него другой интерфейс, похожий на интерфейс контейнеров:
Разница только в том, что диапазон не владеет элементами, которые он задаёт. Хотя бы потому что канонический диапазон — это просто пара итераторов (к примеру, std::equal_range). Важно отметить, что диапазон принято задавать полуинтервалом [b, e). Это значит, что итератор-начало b указывает на первый элемент последовательности, а итератор-конец e указывает на элемент после последнего. Таким образом, когда мы приходим в итератор-конец, мы точно знаем, что последовательность закончилась.  Transform Range На основе преобразующих итераторов можно собрать диапазон (см. boost::iterator_range). auto v = std::vector{...};
auto l = [] (auto x) {return x * x;}; auto tb = boost::make_transform_iterator(v.begin(), l); auto te = boost::make_transform_iterator(v.end(), l); auto tr = boost::make_iterator_range(tb, te); for (auto x: tr) { ... } Или проще (см. boost::transformed): auto v = std::vector{...};
auto tr = boost::adaptors::transform(v, [] (auto x) {return x * x;}); for (auto x: tr) { ... } В C++20 это std::transform_view: auto v = std::vector{...};
auto tr = std::ranges::views::transform(v, [] (auto x) {return x * x;}); for (auto x: tr) { ... } Stride Другой пример ленивого диапазона — это boost::strided. Он оборачивает исходный диапазон так, что в новом диапазоне остаются только кратные позиции исходного диапазона.  auto v = std::vector{1, 2, 3, 4};
// ^ ^ auto s = boost::adaptors::strided(v, 2); assert(s.front() == 1); s.advance_begin(); assert(s.front() == 3); Компоновка После того, как мы научились создавать диапазоны, нам не составит никакой сложности скомбинировать их в цепочку. Например, если мы хотим для некоей последовательности чисел:
то можно это сделать так: auto v = std::vector{...};
auto r = v | transformed([] (auto x) {return x * x;}) | strided(4) | filtered([] (auto x) {return x % 2 == 0;}); Или, в C++20: auto v = std::vector{...};
auto r = v | std::views::transformed([] (auto x) {return x * x;}) // | strided(4) // В C++20 такого нет. | std::views::filtered([] (auto x) {return x % 2 == 0;}); Ещё раз хочу подчеркнуть, что этот код не производит никаких вычислений. Он только сохраняет "схемы" работы с диапазоном, а настоящие вычисления будут происходить только во время продвижения или разыменования обёрнутого итератора.
Суть итераторов и диапазонов Помимо C++, в некоторых языках программировани также существует концепция под названием "итератор", но эта концепция зачастую имеет какой-то свой, альтернативный смысл. К примеру, "итераторы" в языках Java и C# знают свой предел. С точки зрения языка C++ это, скорее, диапазоны. В C++ итератор — это именно обобщение указателя. По сути указатель — это самый сильный (или наиболее конкретный) итератор, причём иерархия следующая:
Диапазон же можно рассматривать именно как пару итераторов (даже если это на самом деле не так). Диапазон уже знает, где у него конец, может накладывать дополнительную логику на операции с итераторами и т.д. Также диапазон может быть сконвертирован обратно в итераторы (потому что диапазон — это пара итераторов, как уже было сказано выше). Такое разделение на итераторы и диапазоны помогает создавать универсальные, гибкие и эффективные интерфейсы для операций над последовательностями. Один из примеров создания сложной операции над диапазонами я привёл в статье Ленивые операции над множествами в C++. Ссылки =========== Источник: habr.com =========== Похожие новости:
Программирование ), #_c++, #_algoritmy ( Алгоритмы ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 19:22
Часовой пояс: UTC + 5