В предыдущем посте мы попробовали вписать в STL интервалы с разделителями и убедились, что результат оставляет желать лучшего.
Теперь мы попробуем это сделать через бесконечные промежутки времени, чтобы прийти к аналогичному выводу.
Но это упражнение приведет нас к концепции суперинтервалов, которая будет включать в себя ограниченные интервалы, бесконечные интервалы и пары итераторов в стиле STL.
Бесконечные интервалы
Потребность в бесконечных интервалах обосновать немного сложнее.Программисты C++ редко сталкиваются с бесконечностью.
В других языках это происходит постоянно.
В Haskell вы можете создать бесконечный список целых чисел, просто набрав [1.].
Это просто ленивый список, элементы которого создаются по требованию.
Все бесконечные интервалы ленивы.
Зачем это может понадобиться? Скажем, в алгоритме, который строит новый список из первых N элементов другого.
Или вы можете захотеть «склеить» бесконечный список с конечным.
Тогда вы получите конечный список пар элементов.
Это совершенно нормальная практика.
Было бы здорово иметь поддержку бесконечных списков в библиотеке общего назначения.
Бесконечные интервалы/в STL
Вы можете думать о бесконечных интервалах как об ограниченных интервалах, где условие ограничения всегда возвращает false. Имея это в виду, давайте реализуем бесконечный список целых чисел, начиная с заданного числа и заканчивая словом «никогда».
С помощью этого списка вы можете сделать следующее: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. Они хранят целое число и логическое значение, указывающее, является ли итератор итератором сигнала.
Начальный итератор не является итератором сигнала, а конец — это итератор сигнала.
Поэтому они никогда не будут равны, и мы будем считать целые числа целую вечность.
Что произошло на пути к бесконечности
Правда, работая с таким интервалом, вы обнаружите, что что-то работает как положено, а что-то улетает в гиперпространство и не возвращается.
Простой пример: std::distance. Вы должны быть достаточно умны, чтобы не делать следующее: iota_range iota;
// Oops!
auto dist = std::distance(iota.begin(), iota.end());
Менее очевидно, что вы никогда, никогда и никогда не должны передавать такой диапазон в какой-либо алгоритм двоичного поиска -binary_search, low_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. Это входной итератор, поэтому с ним необходимо связать Different_type. В книге «Элементы программирования» Александр Степанов (отец STL и Generic Programming) говорит следующее: DistanceType возвращает целочисленный тип, достаточно большой для измерения любой последовательности допустимых приложений доступа.
Для istream_iterator тип разницы_типа будет 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 недостаточно велик для результата? Ответ: неопределенное поведение.
На практике это фигня, но в принципе ничего.
Это меня немного смущает. Разностный_тип итератора должен быть достаточно большим, чтобы вместить пространство между любыми двумя итераторами.
Поскольку входные потоки в принципе не имеют границ, для них не существует достаточно большого целого числа со знаком.
Мы должны признать, что допустимость операции приращения istream_iterator ограничена размером Different_type или что Difference_type установлен неправильно.
Предварительное заключение
Бесконечные интервалы — полезная вещь, но у них есть проблема с тем, как они сейчас определены в STL. Можно было бы запретить бесконечные интервалы, но проблема еще серьезнее.И некоторые проблемы существуют до сих пор.
Трудно исправить проблему переполнения Different_type в STL (кроме как призывать людей быть осторожными), но мы можем задаться вопросом, может ли помочь новый интерфейс для интервалов.
Вот пока все проблемы, с которыми я столкнулся при работе с интервалами с парой итераторов по принципу STL:
- разделенные интервалы и бесконечные интервалы создают плохой код,
- им приходится моделировать более слабые концепции, чем они могли бы,
- их сложно использовать
- очень легко передать бесконечный интервал алгоритму, который его не переварит,
- интервалы, которые могут быть бесконечными или очень большими, могут вызвать переполнение в Different_type.
Не переключайтесь.
И снова небольшой подарок для тех, кто дошёл до конца.
Еще пять билетов со скидкой 30% по промокоду Infinite Ranges УПД: Справедливо сказать БезднаЭкс Исправлен пассаж про zip. Спасибо! Другие статьи из серии Интервалы в C++, часть 1: Интервалы с разделителями Интервалы в C++, часть 3: введение инкрементаторов (Iterable) Интервалы в C++, часть 4: до бесконечности и дальше Теги: #C++ #c++11 #диапазоны #C++
-
Преимущества Обзоров Веб-Хостинга
19 Oct, 24 -
Гибридный Логический Нейрон
19 Oct, 24 -
Mozilla Намного Медленнее Ie6
19 Oct, 24 -
Техлид - Уходи
19 Oct, 24 -
Почему Битрикс - Битрикс
19 Oct, 24 -
Зачем Нам Кузнец?
19 Oct, 24 -
Tdatetime В Qdatetime
19 Oct, 24
