В публикации Ленивые операции над множествами в C++ я показал, как можно проектировать ленивые операции над несколькими диапазонами. Теперь я хочу подробнее рассказать о важном решении, делающем такие операции удобными в использовании.
Один из основных моментов в интерфейсе ленивых операций над диапазонами — это возможность следующей записи
burst::merge(std::tie(range1, range2, ...));То есть возможность работать с произвольным набором исходных диапазонов.
В коде это будет выглядеть как-то так:
const auto odd = std::vector{1, 3, 5, 7};
const auto even = std::list{0, 2, 4, 6, 8};
const auto merged_range = burst::merge(std::tie(odd, even));
const auto expected = {0, 1, 2, 3, 4, 5, 6, 7, 8};
assert(merged_range == expected);Почему же это так важно, и что стоит за этой записью?
Ответ на вопрос "почему это важно" понятен. Во-первых, это красиво. Кроме того, удобно.
А вот что за этим стоит — и есть суть данной публикации.
Содержание
- Проблематика
- Стирание типа диапазона
- Сделай. Пожалуйста
- Массив диапазонов
- Диапазон из контейнера
- Собираем всё вместе
- std::tie
- Заключение
- Ссылки
Проблематика
Ключевой момент дизайна ленивых итераторов над диапазонами (см. Дизайн->Быстрое копирование) — это их легковесность. Если коротко — в итераторе не лежит ничего лишнего, кроме пары других итераторов.
Это даёт гибкость, но и накладывает определённые ограничения.
Допустим, мы хотим слить несколько разнотипных диапазонов. Но под капотом у итератора слияния сидит алгоритм, который хранит сливаемые диапазоны в одном контейнере и может переупорядочивать их (см. Алгоритм слияния).
Хранить в одном контейнере разнотипные объекты можно (например, использовать std::variant или динамический кортеж), но в нашем случае довольно накладно. Поэтому нужно привести их к одному типу.
— Но как, Холмс?
— Элементарно, мой дорогой Ватсон. Использовать стирание типов.
Стирание типа диапазона
Канонический пример стирания типов — std::any.
Наш "стёртый" диапазон — это any-диапазон. Собственно, в Бусте он так и называется — boost::any_range.
Для приведения разных диапазонов к единому типу нужно:
- Найти минимальную категорию из категорий исходных диапазонов;
- Выделить тип итерируемых элементов;
- Создать
any-диапазон, который знает только свою категорию и тип итерируемых элементов.
Если совсем по-простому, стирание типов — это механизм, который позволяет "потерять" тип объекта на этапе компиляции, но "запомнить" этот тип в обработчике, который будет вызван когда-нибудь потом.
#include <iostream>
#include <string>
template <typename T>
void handle (const void * erased_object)
{
std::cout << *static_cast<const T *>(erased_object) << std::endl;
}
struct erased_t
{
// Обработчик принимает указатель на void.
using handler_type = void (*) (const void *);
const void * object;
handler_type handler;
};
template <typename T>
erased_t erase (const T & object)
{
// Запомнили указатель на объект и нужный ему обработчик.
return {&object, &handle<T>};
}
int main ()
{
auto s = std::string("123");
// Стёрли тип.
auto erased = erase(s);
// ...
// Много кода.
// ...
// Вызвали запомненный обработчик.
erased.handler(erased.object);
}
Сделай. Пожалуйста
Итак, у нас есть возможность стирать типы диапазонов. Напишем функцию uniform_range_tuple_please, которая из кортежа ссылок на различные диапазоны должна сделать кортеж ссылок на одинаковые диапазоны.
Тут я использую идиому, которую называю "please" (если у неё есть какое-то общераспространённое название, напишите в комментариях, пожалуйста). Заключается она в том, что некая функция делает что-то только в том случае, если это требуется. А если не требуется, то возвращает то же, что получила на входе.
template <typename... Ranges>
auto uniform_range_tuple_please (std::tuple<Ranges &...> ranges)
{
return uniform_range_tuple_please_impl(ranges, are_same<Ranges...>{});
}Если изначальные кортежи неодинаковые, то мы их приводим к единому типу.
template <typename... Ranges>
auto uniform_range_tuple_please_impl (std::tuple<Ranges &...> ranges, std::false_type)
{
static_assert(not are_same_v<Ranges...>, "");
using iterator_category = minimum_category_t<range_category_t<Ranges>...>;
using boost_traversal =
typename boost::iterator_category_to_traversal<iterator_category>::type;
return by_all(to_any_range<boost_traversal>, ranges);
}Если же они изначально одинаковые, то ничего делать не нужно. Возвращаем исходный объект.
template <typename... Ranges>
auto uniform_range_tuple_please_impl (std::tuple<Ranges &...> ranges, std::true_type)
{
static_assert(are_same_v<Ranges...>, "");
return ranges;
}Массив диапазонов
После того, как исходные диапазоны были приведены к единому типу, нужно их сложить в контейнер. Здесь просто складываем их в std::vector. Для этого я использую самописную утилиту burst::make_range_vector. Всё.
Диапазон из контейнера
Дальше требуется ещё одна хитрость.
Как уже было сказано, в итераторе слияния должна храниться только пара итераторов на контейнер, в котором лежат сливаемые диапазоны. А после предыдущего шага у нас на руках как раз-таки контейнер. И его нужно, с одной стороны, где-то сохранить (он должен жить, пока жив итератор слияния), а с другой — в итераторе слияния должны быть только итераторы на начало и конец нашего контейнера.
Для этого есть владеющий итератор. Он хранит итерируемый контейнер (в умном указателе) и итератор этого контейнера. Время жизни итерируемого контейнера ограничено созданием первого и уничтожением последнего экземпляров владеющего итератора. Кроме того, владеющий итератор сохраняет все характеристики итератора хранимого контейнера. Все действия с ним — продвижение, разыменование, сравнение — производятся так, как будто бы с итератором хранимого контейнера.
Собираем всё вместе
А теперь осталось только взять всё, что у нас имеется, и написать нужную обвязку:
template <typename ... Ranges>
auto make_merge_iterator (std::tuple<Ranges &...> ranges)
{
auto common_ranges = detail::uniform_range_tuple_please(ranges);
return make_merge_iterator(own_as_range(burst::apply(make_range_vector, common_ranges)));
}std::tie
Ленивый итератор над диапазонами оперирует только ссылками и итераторами на исходные диапазоны. Поэтому нужно, чтобы был внешний (по отношению к нашему ленивому итератору) владелец этих диапазонов.
Я долго думал над тем, какой именно интерфейс нужно предоставить для того, чтобы передавать произвольный набор исходных диапазонов: то ли создать специальную структуру, то ли использовать вариадик и enable_if-магию. Но потом понял, что в стандартной библиотеке уже есть то, что мне нужно: std::tie.
Во-первых, std::tie создаёт кортеж. Во-вторых, запись получается достаточно лаконичной. Ну и в-третьих, std::tie принимает только lvalue, то есть временные объекты он принимать откажется. Значит, тем, что мы передаём в std::tie, уже кто-то владеет, и объект не умрёт в процессе слияния. Никаких висячих ссылок.
Заключение
Мы получили удобный интерфейс для ленивого слияния (или любой другой операции над множествами) и достаточно эффективную реализацию этого механизма.
При этом, если для нас недопустимы накладные расходы на, например, std::shared_ptr в недрах burst::owning_iterator, то мы по-прежнему можем создать диапазон для слияния руками.