В предыдущем посте мы пытались впихнуть интервалы с ограничителями в 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<char> 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
ссылка на оригинал статьи http://habrahabr.ru/post/264473/
Добавить комментарий