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

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

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

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

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

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

Бесконечные интервалы/в 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
UPD: По справедливому замечанию VoidEx исправили пассаж про zip. Спасибо!

Другие статьи цикла
Интервалы в С++, часть 1: Интервалы с ограничителями
Интервалы в С++, часть 3: представляем инкременторы (Iterable)
Интервалы в С++, часть 4: к бесконечности и далее