Обертываем алгоритмы в итераторы

Здравствуйте, дорогие читатели. Сегодня пятница, а у нас на борту продолжается напряженный отсмотр и анализ новинок по C++, желательно с учетом C++ 17. В ходе этого увлекательного занятия мы набрели на блог Яцека Галовица (Jacek Galowicz). Из сравнительно свежих материалов нам особенно понравилась статья, размещенная под катом.

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

Числа Фибоначчи

Ряд чисел Фибоначчи широко известен. Генерация этих чисел – классический пример рекурсии, но, как минимум, в стандартных императивных языках, итеративная версия получается мощнее:

size_t fib(size_t n)
{
    size_t a {0};
    size_t b {1};

    for (size_t i {0}; i < n; ++i) {
        const size_t old_b {b};
        b += a;
        a  = old_b;
    }

    return b;
}

Таким образом очень просто сгенерировать любое число Фибоначчи. Но если для решения той или иной задачи нужно сгенерировать все числа Фибоначчи вплоть до некоторого предела, это решение уже не назовешь удобным. При подсчете числа Фибоначчи N, а затем N+1, содержимое переменных a и b можно было бы переиспользовать, поскольку каждое число Фибоначчи есть сумма двух предыдущих чисел того же ряда.

В данном случае удобно было бы иметь класс, управляющий неким состоянием Фибоначчи, чтобы с его помощью быстро получать именно следующее число.

Многие из нас просто реализовали бы класс fibonacci_number с некоторым методом next(), методом current() – и использовали его. Это, конечно, хорошо, но я предлагаю сделать еще один шаг и напоминаю: ведь именно так работают итераторы. Реализовав эту функциональность на языке итераторов, ее можно использовать в комбинации с STL, значительно повысив удобочитаемость кода.

Итераторы

Что нужно сделать, чтобы реализовать простейший возможный итератор?

Вот что имеет к нам компилятор C++, если мы хотим перебрать класс контейнера:

for (const auto &item : vector) {
    /* тело цикла */
}

Такое объявление цикла существует со времен C++11. Компилятор сделает из него вот такой эквивалентный код:

{
    auto it  (std::begin(vector));
    auto end (std::end(vector));

    for (; it != end; ++it) {
        const auto &item (*it);
        /* тело цикла */
    }
}

Смотрим на расширенный цикл – и видим, что нужно реализовать. Во-первых, нужно различать объекты двух видов: vector – это итерируемый диапазон, а it — итератор.

Итерируемый диапазон должен реализовывать функции begin() и end(). Эти функции возвращают объекты итератора.

Обратите внимание: в примере кода возвращается не vector.begin() и vector.end(), а std::begin(vector) и std::end(vector). Эти функции STL действительно вызывают vector.begin() и end(), но они более универсальны, то есть, также применимы с необработанными массивами и автоматически делают что надо, чтобы получить начальный и конечный итераторы.

Вот что должно быть реализовано в классе iterator:

• оператор *, выполняющий разыменование указателя (указатели – также полноценные итераторы!)
• оператор ++ (префиксный), делающий инкремент итератора до следующего элемента
• оператор !=, необходимый для проверки того, а не следует ли завершить цикл – то есть, не достиг ли it позиции, указанной в end.

Чтобы реализовать какой бы то ни было алгоритмически генерируемый диапазон, для начала нужно сделать итератор, который, в сущности, скрывает переменные и сам алгоритм в реализации operator++. Затем итерируемый класс просто предоставит начальный и конечный итераторы, обеспечив, таким образом, циклы for в стиле C++11.

class iterator
{
    // ... переменные состояния ...

public:
    // Конструктор

    iterator& operator++() { /* инкремент */ return *this; }

    T operator*() const { /* вернуть значение или ссылку */ }

    bool operator!= const (const iterator& o) { /* сравнить состояния */ }
}

Простейший на свете итератор – счетный; он просто оборачивает целочисленную переменную, оборачивает ее в operator++ и возвращает целое число в operator*. operator!= затем просто сравнит это число с числом из другого итератора.
А теперь перейдем к итератору Фибоначчи.

Итератор Фибоначчи

class fibit
{
    size_t i {0};
    size_t a {0};
    size_t b {1};

public:
    constexpr fibit() = default;

    constexpr fibit(size_t b_, size_t a_, size_t i_)
        : i{i_}, a{a_}, b{b_}
    {}

    size_t operator*() const { return b; }

    constexpr fibit& operator++() {
        const size_t old_b {b};
        b += a;
        a  = old_b;
        ++i;
        return *this;
    }

    bool operator!=(const fibit &o) const { return i != o.i; }
};

При помощи этого итератора уже можно перебрать числа Фибоначчи:

fibit it;

// Поскольку оператор сравнения сравнивает только переменную "i",
// определяем итератор с одними нулями, но для "i" устанавливаем значение
// 20, чтобы на нем перебор завершился 
const fibit end {0, 0, 20};

while (it != end) {
    std::cout << *it << std::endl;
    ++it;
}

// Либо делаем это красиво как в STL: (сначала включаем <iterator>)
std::copy(it, end, std::ostream_iterator<size_t>{std::cout,"\n"});

Чтобы все было красиво, как в C++11, нам нужен итерируемый класс:

class fib_range
{
    fibit  begin_it;
    size_t end_n;

public:
    constexpr fib_range(size_t end_n_, size_t begin_n = 0)
        : begin_it{fibit_at(begin_n)}, end_n{end_n_}
    {}

    fibit begin() const { return begin_it; }
    fibit end()   const { return {0, 0, end_n}; }
};

А теперь можно написать…

for (const size_t num : fib_range(10)) {
    std::cout << num << std::endl;
}

… и вывести на экран 10 первых чисел Фибоначчи

Что делает функция fibit_at? Это функция constexpr, которая по возможности продвигает итератор Фибоначчи во время компиляции, чтобы он дошел до того числа Фибоначчи, которое требуется пользователю:

constexpr fibit fibit_at(size_t n)
{
    fibit it;
    for (size_t i {0}; i < n; ++i) {
        ++it;
    }
    return it;
}

Например, эта функция позволяет перебрать числа в ряду Фибоначчи от сотого до сто пятого без необходимости высчитывать первые 100 чисел Фибоначчи во время выполнения, так как мы можем подготовить нужную стартовую позицию уже во время компиляции.

При работе с C++17 fibit_at бесполезна, так как ее можно заменить на std::next(fibit{}, n), поскольку в C++17 STLstd::next – это функция constexpr.

Чтобы гарантировать, что 100-е число в ряду Фибоначчи уже будет высчитано, когда компилятор станет записывать на диск бинарную программу, можно просто внести диапазон в переменную constexpr:

constexpr const fib_range hundred_to_hundredfive {105, 100};

for (size_t num : hundred_to_hundredfive) {
    // Делаем что-нибудь
}

Комбинируем итератор Фибоначчи с алгоритмами STL

Допустим, нам нужен вектор с первыми 1000 числами Фибоначчи. Мы уже обернули алгоритм Фибоначчи в удобный класс итератора, и теперь можем использовать его с любым STL-алгоритмом из пространства имен std:

std::vector<size_t> fib_nums;
fib_nums.resize(1000);

constexpr const fib_range first1000 {1000};
std::copy(std::begin(first1000), std::end(first1000), std::begin(fib_nums));

Очень красиво и удобно. Однако, код в том виде, как он представлен здесь, не скомпилируется, поскольку мы не задали метку итератора. Делается это просто: пусть fibit явно унаследует std::iterator<std::forward_iterator_tag, size_t>.

std::iterator, будучи базовым для нашего класса fibit, просто добавит несколько определений типов, которые помогут алгоритмам STL разобраться, что это за итератор. Для итераторов определенного типа в конкретных ситуациях существуют иные реализации алгоритмов STL, производительность которых оптимизирована (от пользователя это аккуратно скрыто!).

Метка std::forward_iterator означает, что перед нами итератор, который можно просто продвигать шаг за шагом – и он будет двигаться только вперед, но не назад.

Итоги

Многие алгоритмы, генерирующие числовые диапазоны, можно реализовать в виде итераторов, что совершенно естественно. В C++ есть вкусный синтаксический сахар для итераторов, благодаря чему из них получаются органичные интерфейсы для абстракций.

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

В статье рассказано об итераторе, а не обычном указателе данных. Реализация алгоритма интересна тем, что на этапе инкремента вычисляется нечто более сложное, нежели новая позиция внутреннего указателя на следующий элемент. Интересно, что таким образом можно инстанцировать некоторый итерируемый объект, определяющий диапазон – а для этого необходимы серьезные вычисления. Но они выполнены не будут, пока кто-нибудь специально не запросит результат (а код, запрашивающий результат, даже не «знает», какой алгоритм при этом неявно выполняется, поскольку эта информация скрыта за простым интерфейсом итератора).

Такой стиль связан с ленивыми вычислениями – это мощный и красивый принцип из чисто функциональных языков программирования.