Интервалы в С++, часть 2: Бесконечные интервалы

В предыдущем посте мы пытались впихнуть интервалы с ограничителями в STL, и убедились, что результат оставляет желать лучшего. Сейчас мы попробуем сделать это с бесконечными интервалами, чтобы прийти к аналогичному заключению. Но это упражнение направит нас к концепции супер-интервалов, которые будут включать в себя и интервалы с ограничителями, и бесконечные, и пары итераторов, напоминающие STL'ные.

Бесконечные интервалы

Необходимость бесконечных интервалов обосновать чуть сложнее. Программисты на С++ редко сталкиваются с бесконечностями. В других языках это случается сплошь и рядом. В Haskell можно создать бесконечный список целых чисел, просто набрав [1..]. Это просто «ленивый список», элементы в котором создаются по требованию. Все бесконечные интервалы ленивые.

Для чего это может понадобиться? Допустим, в алгоритме, строящем новый список из N первых элементов другого. Или вы захотите «склеить» бесконечный список с конечным. Тогда вы получите конечный список пар элементов. Это совершенно нормальная практика.

Было бы круто иметь поддержку бесконечных списков в библиотеке общего назначения.

Бесконечные интервалы/в STL

Можно представить себе бесконечные интервалы как интервалы с ограничителями, где условие ограничения всегда возвращает ложь. Памятуя об этом, реализуем бесконечный список целых чисел, начинающийся с заданного числа, и заканчивающийся «никогда».

С таким списком можно сделать следующее:

iota_range – прямой интервал; то есть, его итераторы построены по модели ForwardIterator. В них хранится целое число и булевское значение, которое говорит о том, является ли итератор сигнальным. Итератор begin не сигнальный, а end – сигнальный. Поэтому они никогда не будут равны, и мы будем считать целые числа целую вечность.

Что случилось по пути в бесконечность

Правда, при работе с таким интервалом вы выясните, что что-то работает, как ожидалось, а что-то улетает в гиперпространство и не возвращается. Простой пример: std::distance. Вам должно хватить ума, чтобы не делать следующее:

Менее очевидно, что вам нельзя, вообще, никогда, ни за что, передавать такой интервал в любой алгоритм бинарного поиска – binary_search, lower_bound, upper_bound и equal_range. Несмотря на то, что iota_range – это отсортированный прямой интервал. Бинарные алгоритмы делят интервалы, а деление бесконечного интервала на выходе должно дать бесконечный интервал. Ждать этого придётся долго.

Быстродействие

Читателей прошлого поста, возможно, покоробила реализация iota_range::iterator::equal. Поскольку iota_range никогда не должен остановиться в своих итерациях, условие прекращения должно быть константой. Вместо этого мы делаем следующее:

Две проверки там, где их должно быть ноль! В прошлый раз я показал, что это приводит к нежелательным эффектам в сгенерированном коде.

Возможные бесконечные интервалы

Кроме проблемы с бесконечными циклами есть ещё одна, которая, к сожалению, существует в STL. Возьмём моего любимого мальчика для битья std::istream_iterator. Это итератор ввода, поэтому с ним необходимо связать difference_type. В книге «Elements of Programming» Александр Степанов (отец STL и Generic Programming) говорит про это так:

DistanceType возвращает целый тип, достаточно большой, чтобы измерить любую последовательность приложений допустимого саксессора.

Для istream_iterator difference_type будет std::ptrdiff_t. Рассмотрим такой код:

Код допустимый и логичный. Он выцепляет символы из istream, подсчитывает их, и избавляется от них. Представьте, что sin получает символы из сети, и этот код работает несколько дней, получая миллиарды символов. Что случится, если ptrdiff_t окажется недостаточно большим для результата? Ответ: неопределённое поведение. На практике – мусор, но в принципе – всё, что угодно.

Меня это маленько сбивает с толку. У итератора difference_type должен быть достаточно большим, чтобы содержать промежуток между двумя любыми итераторами. Поскольку потоки ввода в принципе границ не имеют, то не существует знакового целого, достаточно большого для них. Приходится признать, что допустимость операции увеличения istream_iterator ограничена размером difference_type, или что difference_type задан неверно.

Предварительное заключение

Бесконечные интервалы – вещь полезная, но у них есть проблема с тем, как они сейчас определены в STL. Можно было бы запретить бесконечные интервалы, но проблема даже больше этого. И некоторые из проблем существуют и сегодня. Тяжело исправить проблему с переполнением difference_type в STL (кроме как просить людей соблюдать осторожность), но можно подумать, не поможет ли нам новый интерфейс для интервалов.

Вот пока все проблемы, которые я встретил с интервалах с парой итераторов по принципу STL:

• интервалы с ограничителями и бесконечные интервалы генерят плохой код,
• им приходится моделировать более слабые концепции, чем они могли бы,
• их трудно использовать,
• очень просто передать бесконечный интервал в алгоритм, который его не переварит,
• интервалы, которые могут быть бесконечными или очень большими, могут вызвать переполнение в difference_type.

В следующем посте я опишу основы концепции моей новой библиотеки интервалов, которая бьёт в корень всех этих проблем. Не переключайтесь.

Вновь небольшой презент для добравшихся до конца. Ещё пять билетов со скидкой 30% по промокоду Infinite Ranges UPD: По справедливому замечанию VoidEx исправили пассаж про zip. Спасибо!