C++17 STL Стандартная библиотека шаблонов — страница 28 из 119

1. Чтобы иметь возможность вывести на экран числа Фибоначчи, включим соответствующий заголовочный файл:

#include 

2. Определим итератор Фибоначчи, fibit. Он будет содержать член i, в котором будет сохраняться индекс позиции в последовательности Фибоначчи, а также члены a и b, в которых будут храниться два последних значения Фибоначчи. При вызове конструктора по умолчанию итератор Фибоначчи инициализируется значениями F(0).

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

3. Далее определим стандартный конструктор и конструктор, который позволит инициализировать итератор любым этапом вычисления чисел Фибоначчи:

public:
  fibit() = default;
  explicit fibit(size_t i_)
    : i{i_}
  {}

4. Разыменование итератора (*it) вернет текущее число Фибоначчи на данном шаге:

  size_t operator*() const { return b; }

5. При инкрементировании итератор (++it) переместится на следующее число Фибоначчи. Эта функция содержит тот же код, что и реализация функции Фибоначчи, основанная на цикле:

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

6. При использовании в цикле инкрементированный итератор сравнивается с конечным итератором, для чего следует реализовать оператор !=. Мы выполняем сравнение только на том шаге, на котором в данный момент находятся итераторы Фибоначчи, что позволяет проще определить конечный итератор, скажем, для шага 1000000, поскольку не нужно выполнять трудоемкие вычисления этого довольно большого числа Фибоначчи заранее.

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

7. Чтобы иметь возможность использовать итератор Фибоначчи в основанном на диапазоне цикле for, реализуем класс диапазона заранее. Назовем его fib_range. Его конструктор будет принимать один параметр, который скажет, насколько далеко нужно проитерировать по диапазону данных:

class fib_range
{
  size_t end_n;
public:
  fib_range(size_t end_n_)
    : end_n{end_n_}
  {}

8. Функции begin и end возвращают итераторы, которые указывают на позиции F(0) и F(end_n):

  fibit begin() const { return fibit{}; }
  fibit end() const { return fibit{end_n}; }
};

9. О’кей, теперь забудем о реализации стереотипного кода, связанного с итераторами. Теперь у нас есть вспомогательный класс, который аккуратно скрывает детали реализации! Выведем на экран первые десять чисел Фибоначчи.

int main()
{
  for (size_t i : fib_range(10)) {
    std::cout << i << ", ";
  }
  std::cout << '\n';
}

10. Компиляция и запуск программы дадут следующий результат:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

Дополнительная информация

Использование этого итератора совместно с библиотекой STL предполагает, что он должен поддерживать класс std::iterator_traits. Для того чтобы увидеть, как это делается, взглянем на другой пример, который решает именно эту задачу: обеспечивает совместимость ваших итераторов с категориями итераторов STL.

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

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

□  Сделать конструктор fibit(size_t i_) закрытым и объявить, что класс fib_range является дружественным для класса fibit. Таким образом, пользователи могут применять его только корректным способом.

□  Задействовать особые символы, чтобы помешать пользователям разыменовать конечный итератор. Взгляните на пример, в котором мы делаем именно это: завершаем перебор диапазонов данных с помощью особых символов. 

Перебор в обратную сторону с применением обратных адаптеров для итераторов

Иногда может быть полезно итерировать по диапазону данных не вперед, а назад. Основанный на диапазонах цикл for, а также все алгоритмы STL обычно итерируют по диапазонам данных, инкрементируя итераторы, однако перебор (итерирование) в обратную сторону требует выполнения операции декремента. Конечно, можно обернуть итераторы в слой, преобразующий операцию инкремента в операцию декремента. Но складывается впечатление, что у нас получится множество стереотипного кода на каждый тип, для которого мы собираемся поддерживать эту возможность.

Библиотека STL предоставляет полезный обратный адаптер для итератора, позволяющего задействовать итераторы подобным образом.

Как это делается

В этом примере мы будем разными способами применять обратные итераторы, чтобы показать варианты их использования.

1. Как обычно, включим некоторые заголовочные файлы:

#include 
#include 
#include 

2. Далее объявляем об использовании пространства имен std с целью сэкономить немного времени:

using namespace std;

3. Чтобы у нас появился объект, по которому мы сможем итерировать, создадим список, содержащий целые числа:

int main()
{
  list l {1, 2, 3, 4, 5};

4. Теперь выведем эти числа на экран в обратном порядке. Для этого проитерируем по списку благодаря функциям rbegin и rend класса std::list и выведем данные значения с помощью стандартного потока вывода, используя удобный адаптер ostream_iterator:

  copy(l.rbegin(), l.rend(), ostream_iterator{cout, ", "});
  cout << '\n';

5. Если контейнер не предоставляет функций rbegin и rend, но хотя бы выдает двунаправленные итераторы, то поможет функция std::make_reverse_iterator. Она принимает обычные итераторы и преобразует их в обратные:

  copy(make_reverse_iterator(end(l)),
       make_reverse_iterator(begin(l)),
       ostream_iterator{cout, ", "});
  cout << '\n';
}

6. Компиляция и запуск программы дадут следующий результат:

5, 4, 3, 2, 1,
5, 4, 3, 2, 1,

Как это работает

Преобразование обычного итератора в обратный возможно при поддержке двунаправленного перебора. Это требование выполняется любым итератором, который находится в категории двунаправленных или выше.

Обратный итератор содержит обычный итератор и подражает его интерфейсу, но изменяет операцию инкремента на операцию декремента.

Еще одна деталь связана с позициями начала и конца. Взглянем на рис. 3.4, на котором показана стандартная последовательность чисел, хранящаяся в итерабельном диапазоне данных. Если она содержит числа от