[Перевод] Интервалы в С++, часть 2: Бесконечные интервалы
В предыдущем посте мы пытались впихнуть интервалы с ограничителями в STL, и убедились, что результат оставляет желать лучшего. Сейчас мы попробуем сделать это с бесконечными интервалами, чтобы прийти к аналогичному заключению. Но это упражнение направит нас к концепции супер-интервалов, которые будут включать в себя и интервалы с ограничителями, и бесконечные, и пары итераторов, напоминающие STL’ные.
Бесконечные интервалы
Необходимость бесконечных интервалов обосновать чуть сложнее. Программисты на С++ редко сталкиваются с бесконечностями. В других языках это случается сплошь и рядом. В Haskell можно создать бесконечный список целых чисел, просто набрав [1…]. Это просто «ленивый список», элементы в котором создаются по требованию. Все бесконечные интервалы ленивые.
Для чего это может понадобиться? Допустим, в алгоритме, строящем новый список из N первых элементов другого. Или вы захотите заархивировать в zip бесконечный список при помощи конечного. Тогда вы получите конечный список пар элементов. Это совершенно нормальная практика.
Было бы круто иметь поддержку бесконечных списков в библиотеке общего назначения.
Бесконечные интервалы/в STL
Можно представить себе бесконечные интервалы как интервалы с ограничителями, где условие ограничения всегда возвращает ложь. Памятуя об этом, реализуем бесконечный список целых чисел, начинающийся с заданного числа, и заканчивающийся «никогда».
struct iota_range
{
private:
int i_;
public:
using const_iterator = struct iterator
: boost::iterator_facade<
iterator, int const,
std::forward_iterator_tag
>
{
private:
bool sentinel_;
int i_;
friend class boost::iterator_core_access;
friend struct iota_range;
iterator(int i) : sentinel_(false), i_(i) {}
bool equal(iterator that) const
{
return sentinel_ == that.sentinel_
&& i_ == that.i_;
}
void increment()
{
++i_;
}
int const & dereference() const
{
return i_;
}
public:
iterator() : sentinel_(true), i_(0) {}
};
constexpr explicit iota_range(int i = 0)
: i_(i)
{}
iterator begin() const
{
return iterator{i_};
}
iterator end() const
{
return iterator{};
}
constexpr explicit operator bool() const
{
return true;
}
};
С таким списком можно сделать следующее:
// Spew all the ints. WARNING: THIS NEVER ENDS!
for( int i : iota_range() )
std::cout << i << 'n';
iota_range — прямой интервал; то есть, его итераторы построены по модели ForwardIterator. В них хранится целое число и булевское значение, которое говорит о том, является ли итератор сигнальным. Итератор begin не сигнальный, а end — сигнальный. Поэтому они никогда не будут равны, и мы будем считать целые числа целую вечность.
Что случилось по пути в бесконечность
Правда, при работе с таким интервалом вы выясните, что что-то работает, как ожидалось, а что-то улетает в гиперпространство и не возвращается. Простой пример: std: distance. Вам должно хватить ума, чтобы не делать следующее:
iota_range iota;
// Oops!
auto dist = std::distance(iota.begin(), iota.end());
Менее очевидно, что вам нельзя, вообще, никогда, ни за что, передавать такой интервал в любой алгоритм бинарного поиска — binary_search, lower_bound, upper_bound и equal_range. Несмотря на то, что iota_range — это отсортированный прямой интервал. Бинарные алгоритмы делят интервалы, а деление бесконечного интервала на выходе должно дать бесконечный интервал. Ждать этого придётся долго.
Быстродействие
Читателей прошлого поста, возможно, покоробила реализация iota_range: iterator: equal. Поскольку iota_range никогда не должен остановиться в своих итерациях, условие прекращения должно быть константой. Вместо этого мы делаем следующее:
bool equal(iterator that) const
{
return sentinel_ == that.sentinel_
&& i_ == that.i_;
}
Две проверки там, где их должно быть ноль! В прошлый раз я показал, что это приводит к нежелательным эффектам в сгенерированном коде.
Возможные бесконечные интервалы
Кроме проблемы с бесконечными циклами есть ещё одна, которая, к сожалению, существует в STL. Возьмём моего любимого мальчика для битья std: istream_iterator. Это итератор ввода, поэтому с ним необходимо связать difference_type. В книге «Elements of Programming» Александр Степанов (отец STL и Generic Programming) говорит про это так:
DistanceType возвращает целый тип, достаточно большой, чтобы измерить любую последовательность приложений допустимого саксессора.
Для istream_iterator difference_type будет std: ptrdiff_t. Рассмотрим такой код:
std::istream& sin = ...;
std::istream_iterator it{sin}, end;
std::ptrdiff_t dis = std::distance(it, end);
Код допустимый и логичный. Он выцепляет символы из istream, подсчитывает их, и избавляется от них. Представьте, что sin получает символы из сети, и этот код работает несколько дней, получая миллиарды символов. Что случится, если ptrdiff_t окажется недостаточно большим для результата? Ответ: неопределённое поведение. На практике — мусор, но в принципе — всё, что угодно.
Меня это маленько сбивает с толку. У итератора difference_type должен быть достаточно большим, чтобы содержать промежуток между двумя любыми итераторами. Поскольку потоки ввода в принципе границ не имеют, то не существует знакового целого, достаточно большого для них. Приходится признать, что допустимость операции увеличения istream_iterator ограничена размером difference_type, или что difference_type задан неверно.
Предварительное заключение
Бесконечные интервалы — вещь полезная, но у них есть проблема с тем, как они сейчас определены в STL. Можно было бы запретить бесконечные интервалы, но проблема даже больше этого. И некоторые из проблем существуют и сегодня. Тяжело исправить проблему с переполнением difference_type в STL (кроме как просить людей соблюдать осторожность), но можно подумать, не поможет ли нам новый интерфейс для интервалов.
Вот пока все проблемы, которые я встретил с интервалах с парой итераторов по принципу STL:
- интервалы с ограничителями и бесконечные интервалы генерят плохой код,
- им приходится моделировать более слабые концепции, чем они могли бы,
- их трудно использовать,
- очень просто передать бесконечный интервал в алгоритм, который его не переварит,
- интервалы, которые могут быть бесконечными или очень большими, могут вызвать переполнение в difference_type.
В следующем посте я опишу основы концепции моей новой библиотеки интервалов, которая бьёт в корень всех этих проблем. Не переключайтесь.
Вновь небольшой презент для добравшихся до конца. Ещё пять билетов со скидкой 30% по промокоду Infinite Ranges
