C++17 STL Стандартная библиотека шаблонов - читать бесплатно онлайн полную версию книги автора Яцек Галовиц (Глава 3 Итераторы) #5

Глава 3 Итераторы

В этой главе:

□ построение собственного итерабельного диапазона данных;

□ обеспечение совместимости ваших итераторов с категориями итераторов STL;

□ использование оболочек для итераторов для заполнения обобщенных структур данных;

□ реализация алгоритмов с помощью итераторов;

□ перебор (итерирование) в обратную сторону с применением обратных адаптеров для итераторов;

□ завершение перебора диапазонов данных с использованием ограничителей;

□ автоматическая проверка кода итератора с помощью проверяемых итераторов;

□ создание собственного адаптера для итераторов-упаковщиков.

Введение

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

Многие классы-контейнеры, а также массивы в стиле С так или иначе содержат диапазон неких элементов. Для выполнения множества повседневных задач, связанных с обработкой больших объемов данных, не нужно знать, как эти данные были получены. Однако если у нас есть, например, массив целых чисел и список, содержащий целые числа, то следует воспользоваться двумя разными алгоритмами, представленными ниже.

□ Один алгоритм, который работает с массивом, проверяя его размер и суммируя все его члены, выглядит так:

int sum {0};

for (size_t i {0}; i < array_size; ++i) { sum += array[i]; }

□ Другой алгоритм, который работает со связанным списком и итерирует по нему до конца, выглядит следующим образом:

int sum {0};

while (list_node != nullptr) {

  sum += list_node->value; list_node = list_node->next;

Оба алгоритма суммируют целые числа, но какая часть введенных нами символов непосредственно связана с решением задачи? Работает ли какой-нибудь из этих алгоритмов с другими видами структур данных, например с

std::map

, или нужно реализовывать еще одну версию алгоритма суммирования? Отсутствие итераторов приведет к нелепым решениям.

Только с помощью итераторов можно реализовать этот алгоритм в обобщенном виде:

int sum {0};

for (int i : array_or_vector_or_map_or_list) { sum += i; }

Это красивое и короткое выражение, названное «основанный на диапазоне цикл

for

», существует еще со времен С++11. Оно представляет собой лишь синтаксический сахар, который развертывается в нечто похожее на следующий код:

  auto &&  range = array_or_vector_or_map_or_list;

  auto  begin = std::begin( range);

  auto  end = std::end( range);

  for ( ;  begin !=  end; ++ begin) {

   int i = * begin;

   sum += i;

Такие циклы хорошо знакомы всем, кто уже работал с итераторами, но кажутся черной магией для тех, кто еще этого не делал. Представьте, что наш вектор, содержащий целые числа, выглядит следующим образом (рис. 3.1).

Команда

std::begin(vector)

аналогична команде

vector.begin()

, она возвращает итератор, который указывает на первый элемент (

). Команда

std::end(vector)

аналогична команде

vector.end()

, она возвращает итератор, указывающий на элемент, стоящий за последним элементом (

На каждой итерации цикл проверяет, равен ли начальный итератор конечному. Если это не так, то мы разыменовываем начальный итератор и получаем доступ к числовому значению, на которое он указывает. Далее выполняем операцию инкремента для итератора, повторяем сравнение с конечным итератором и т.д. В этот момент полезно прочесть код цикла снова, представляя, что итераторы — обычные указатели, взятые из языка С. Фактически такие указатели тоже являются итераторами.

Категории итераторов

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

Рассмотрим их в правильном порядке (рис. 3.2).

Итераторы ввода

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

std::istream_iterator

Однонаправленные итераторы

Аналогичны итераторам ввода, но отличаются тем, что по диапазонам данных, которые они представляют, вы можете проитерировать несколько раз. В качестве примера такого итератора приведем

std::forward_list

. По такому списку можно проитерировать только вперед, но не назад, однако это можно сделать требуемое количество раз.

Двунаправленные итераторы

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

std::list

std::set

std::map

Итераторы с произвольным доступом

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

std::vector

std::deque

Непрерывные итераторы

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

std::vector

Итераторы вывода

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

Изменяемые итераторы

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

Создаем собственный итерабельный диапазон данных

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

++

, оператор разыменования

и оператор сравнения объектов

==

, и получится примитивный итератор, подходящий для работы с циклом

for

, основанным на диапазоне, который появился в C++11.

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

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

В этом примере мы реализуем собственный класс итератора, а затем проитерируем по нему.

1. Сначала включим заголовочный файл, который позволит выводить данные на консоль:

#include

2. Наш класс итератора будет называться

num_iterator

class num_iterator {

3. Его единственным членом выступит целое число, которое послужит для счета. Оно будет инициализироваться в конструкторе. Создание явных конструкторов — хороший стиль программирования, поскольку это позволяет избежать случайных неявных преобразований. Обратите внимание: мы предоставляем значение по умолчанию для переменной

position

, что делает возможным создание экземпляров класса

num_iterator

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

  int i;

public:

  explicit num_iterator(int position = 0) : i{position} {}

4. При разыменовании наш итератор (

*it

) генерирует целое число:

  int operator*() const { return i; }

5. Инкрементирование итератора (

++it

) просто увеличит значение его внутреннего счетчика

  num_iterator& operator++() {

   ++i;

   return *this;

6. Цикл

for

будет сравнивать итератор с конечным итератором. Если они не равны, то продолжим перебор:

  bool operator!=(const num_iterator &other) const {

   return i != other.i;

};

7. Это был класс итератора. Нам все еще нужен промежуточный объект для записи

for (int i:intermediate(a, b)) {...}

, который содержит начальный и конечный итераторы и будет перепрограммирован так, чтобы итерировал от

до

. Мы назовем его

num_range

class num_range {

8. Он содержит два члена, представляющие собой целые числа. Они обозначают число, с которого начнется перебор, а также число, стоящее непосредственно за последним числом. Это значит, что если мы хотим проитерировать по числам от

до

, то a будет иметь значение

, а

—

  int a;

  int b;

public:

  num_range(int from, int to)

    : a{from}, b{to}

{}

9. Нужно реализовать всего две функции-члена:

begin

end

. Обе эти функции возвращают итераторы, которые указывают на начало и конец численного диапазона:

  num_iterator begin() const { return num_iterator{a}; }

 num_iterator end() const { return num_iterator{b}; }

};

10. На этом все. Можно использовать полученный объект. Напишем функцию

main

, в которой просто проитерируем по диапазону значений от

до

и выведем эти значения:

int main()

  for (int i : num_range{100, 110}) {

   std::cout << i << ", ";

  std::cout << '\n';

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

100, 101, 102, 103, 104, 105, 106, 107, 108, 109,

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

Представьте, что мы написали следующий код:

for (auto x:range) { code_block; }

Компилятор развернет его в такую конструкцию:

  auto _begin = std::begin(range);

  auto _end = std::end(range);

  for (; _begin !=  end; ++_begin) {

   auto x = *_begin;

   code_block

При взгляде на этот код становится очевидно, что для создания итератора необходимо реализовать всего три оператора:

□

operator!=

— определение равенства;

□

operator++

— префиксный инкремент;

□

operator*

— разыменование.

Требования к диапазону данных заключаются в том, что он должен иметь методы

begin

end

, которые будут возвращать два итератора для обозначения начала и конца диапазона.

В данной книге мы будем использовать преимущественно

std::begin(x)

вместо

x.begin()

. Это хороший вариант, поскольку функция

std::begin(x)

автоматически вызывает метод

x.begin()

, при условии, что он доступен. Если

представляет собой массив, не имеющий метода

begin()

, то функция

std::begin(x)

автоматически определит, как с этим справиться. То же верно и для

std::end(x)

. Пользовательские типы, не имеющие методов

begin()/end()

, не смогут работать с методами

std::begin/std::end

В рамках этого примера мы разместили простой алгоритм счета в интерфейсе однонаправленного итератора. Реализация итератора и диапазона данных зачастую включает в себя написание минимального объема стереотипного кода, что, с одной стороны, может слегка раздражать. С другой стороны, взглянув на цикл, который использует

num_range

, мы понимаем, что это здорово, поскольку цикл выглядит очень просто!

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

Обеспечиваем совместимость собственных итераторов с категориями итераторов STL

Какую бы структуру данных вы ни создали, для эффективного объединения ее с библиотекой STL нужно добавить интерфейсы для итераторов. В последнем разделе мы научились делать это, но затем быстро поняли, что некоторые алгоритмы STL плохо компилируются с нашими итераторами. Почему так происходит?

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

memcpy

. Если мы копируем данные из списка или в него, то такой вызов сделать нельзя и элементы нужно копировать по одному. Авторы алгоритмов STL хорошо продумали подобную автоматическую оптимизацию. Чтобы помочь им, мы укажем некоторую информацию о наших итераторах. В этом разделе показано, как достичь той же цели.

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

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

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

#include

#include

2. Далее реализуем примитивный итератор для подсчета чисел, как было показано в предыдущем разделе. При переборе он генерирует обычные увеличивающиеся целые числа. Диапазон данных

num_range

выступает в роли удобного донора начального и конечного итераторов:

class num_iterator

  int i;

public:

  explicit num_iterator(int position = 0) : i{position} {}

 int operator*() const { return i; }

  num_iterator& operator++() {

   ++i;

   return *this;

  bool operator!=(const num_iterator &other) const {

   return i != other.i;

  bool operator==(const num_iterator &other) const {

   return !(*this != other);

};

class num_range {

 int a;

  int b;

public:

  num_range(int from, int to)

    : a{from}, b{to}

{}

  num_iterator begin() const { return num_iterator{a}; }

  num_iterator end() const { return num_iterator{b}; }

};

3. Чтобы избавиться от префикса пространства имен

std::

и поддерживать код читабельным, объявим об использовании пространства имен

std

using namespace std;

4. Теперь просто создадим диапазон данных, содержащий числа от

до

. Обратите внимание: конечный итератор стоит в позиции

. Это значит, что

— первое число, которое находится за пределами диапазона (именно поэтому он начинается со значения

и заканчивается значением

int main()

  num_range r {100, 110};

5. Теперь воспользуемся им для

std::minmax_element

. Алгоритм возвращает объект типа

std::pair

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

, поскольку именно с их помощью мы создавали диапазон данных:

  auto [min_it, max_it] (minmax_element(begin(r), end(r)));

  cout << *min_it << " - " << *max_it << '\n';

6. Компиляция этого кода приведет к следующему сообщению об ошибке (рис. 3.3). Вы увидите ошибку, связанную с

std::iterator_traits

. Подробнее об этом вы узнаете позже. Может случиться так, что вы увидите другую ошибку, если применяете другие компиляторы и/или реализацию библиотеки STL; а возможно даже, что ошибок не будет. Сообщение об ошибке, показанное на рис. 3.3, появляется при использовании компилятора clang version 5.0.0 (trunk 299766).

7. Для исправления ситуации активизируем возможности типажей итераторов для нашего класса итератора. Сразу после определения

num_iterator

укажем следующую спецификацию шаблона структуры для типа

std::iterator_traits

. Она сообщает STL, что наш итератор num_iterator является однонаправленным и итерирует по целочисленным значениям:

namespace std {

 template <>

  struct iterator_traits {

   using iterator_category = std::forward_iterator_tag;

   using value_type = int;

};

8. Скомпилируем код снова; мы видим, что он работает! Результат работы функций min/max выглядит следующим образом:

100 — 109

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

Одним алгоритмам STL нужно знать характеристики типа итератора, применяемого вместе с ними, другим — тип элементов, среди которых выполняется перебор. От этого зависят варианты реализации алгоритмов.

Однако все алгоритмы STL будут получать эту информацию о типе с помощью

std::iterator_traits

, предполагая, что итератор имеет тип

my_iterator

. Этот класс типажа содержит до пяти разных определений членов.

□

difference_type

— значение какого типа мы получим в результате выполнения конструкции

it1 — it2

□

value_type

— какой тип имеет элемент, к которому мы получаем доступ с помощью

*it

(обратите внимание: для чистых итераторов вывода этот тип будет

void

□

pointer

— к какому типу должен относиться указатель, чтобы иметь возможность указывать на элемент?

□

reference

— какой тип должна иметь ссылка, чтобы она могла работать как полагается?

□

iterator_category:

к какой категории принадлежит итератор?

Определения типов

pointer

reference

difference_type

не нужны для нашего итератора

num_iterator

, поскольку он не итерирует по реальным значениям памяти (мы просто возвращаем значения

int

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

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

До появления C++17 поощрялось наследование итераторами типа

std::iterator<...>

, что автоматически заполняет наш класс всеми описаниями типов. Этот механизм все еще работает, но, начиная с С++17, больше не рекомендуется.

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

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

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

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

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

1. Сначала включим необходимые заголовочные файлы.

#include

#include

#include

#include

#include

2. Объявим об использовании пространства имен

std

, чтобы сэкономить время.

using namespace std;

3. Начнем с итератора

std::istream_iterator

. Мы специализируем его для типа

int

. Таким образом, он станет преобразовывать данные из стандартного потока ввода в целые числа. Например, при итерировании по нему он будет выглядеть так, будто имеет тип

std::vector

. Конечный итератор имеет тот же тип, но не принимает аргументы конструктора.

int main()

  istream_iterator it_cin {cin};

 istream_iterator end_cin;

4. Далее создадим экземпляр типа

std::deque

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

std::back_insert_iterator

с помощью вспомогательной функции

std::back_inserter

. Эта особая оболочка для итератора позволит выполнить метод

v.push_back(item)

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

  deque v;

  copy(it_cin, end_cin, back_inserter(v));

5. Воспользуемся

std::istringstream

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

stream

  istringstream sstr {"123 456 789"};

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

std::next

. Второй аргумент данной функции говорит о том, что вернет итератор, смещенный на позицию

v.size()/2

шагов, т.е. на половину очереди. (Мы преобразуем

v.size()

к типу

int

, поскольку второй параметр функции

std::next

представляет собой

difference_type

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

  auto deque_middle (next(begin(v),

              static_cast(v.size())/2));

7. Теперь можно скопировать проанализированные целые числа шаг за шагом из потока ввода строк в очередь. Опять же конечный итератор оболочки итератора потока представляет собой пустой объект типа

std::istream_iterator

без аргументов конструктора (поэтому вы можете видеть пустые скобки

{}

в строке кода). Очередь оборачивается в итератор вставки, который представляет собой

std::insert_iterator

, указывающий на середину очереди с помощью итератора

deque_middle

  copy(istream_iterator{sstr}, {}, inserter(v, deque_middle));

8. Воспользуемся итератором

std::front_insert_iterator

, чтобы вставить элементы в начало очереди:

  initializer_list il2 {-1, -2, -3};

  copy(begin(il2), end(il2), front_inserter(v));

9. На последнем шаге выведем содержимое очереди на консоль. Здесь итератор

std::ostream_iterator

работает как итератор вывода, что в нашем случае просто перенаправляет все скопированные целые числа в

std::cout

, прикрепляя символ "

" после каждого элемента:

  copy(begin(v), end(v), ostream_iterator{cout, ", "});

  cout << '\n';

10. Компиляция и запуск программы дадут следующий результат. Можете ли вы определить, какие строки кода добавили каждое число?

$ echo "1 2 3 4 5" | ./main

-3, -2, -1, 1, 2, 123, 456, 789, 3, 4, 5,

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

Мы использовали множество разных адаптеров. Они имеют только одну схожую черту — оборачивают объект, не являющийся итератором сам по себе, в итератор.

std::back_insert_iterator

В адаптер

back_insert_iterator

можно обернуть типы

std::vector

std::deque

std::list

и т.д. Он будет вызывать метод контейнера

push_back

, который вставит новый элемент после всех существующих элементов. Если объект контейнера недостаточно велик, то его размер увеличится автоматически.

std::front_insert_iterator

Адаптер

front_insert_iterator

делает то же самое, что и адаптер

back_insert_iterator

, но вызывает метод контейнера

push_front

, который вставляет новый элемент перед существующими. Обратите внимание: для контейнеров наподобие

std::vector

это значит, что все существующие элементы нужно сдвинуть на одну позицию вправо для освобождения места под новый элемент.

std::insert_iterator

Этот адаптер итератора аналогичен другим итераторам вставки, но может вставлять новые элементы между существующими. Вспомогательная функция

std::inserter

, которая создает подобную оболочку, принимает два аргумента. Первый — контейнер, а второй — итератор, указывающий на позицию, в которую будут вставлены новые элементы.

std::istream_iterator

Адаптер

istream_iterator

тоже довольно удобен. Он подходит для любого объекта

std::istream

(который может представлять собой стандартный поток ввода или файлы) и будет пытаться преобразовывать полученные данные в соответствии с параметром шаблона. В этом примере мы использовали конструкцию

std::istream_iterator(std::cin)

, получающую из потока ввода целые числа.

Как правило, мы не знаем длину потока. Это оставляет открытым вопрос: куда указывает конечный итератор, если нам неизвестно, где заканчивается поток? Суть в том, что итератор знает, когда достигает конца потока. При сравнении с конечным итератором он фактически не будет сравнивать себя с конечным итератором, но даст знать, остались ли токены в потоке. Именно поэтому конструктор конечного итератора не принимает никаких аргументов.

std::ostream_iterator

Адаптер

ostream_iterator

аналогичен адаптеру

istream_iterator

, но работает по обратному принципу: не принимает токены из потока ввода, а отправляет их в поток вывода. Еще одно отличие заключается в том, что его конструктор принимает второй аргумент, являющийся строкой, которая будет помещена в поток вывода после каждого элемента. Это полезно, поскольку таким способом можно вывести на экран разделяющую запятую "

" или символ перехода на новую строку.

Реализуем алгоритмы с помощью итераторов

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

++it

) и возвращать это значение при разыменовании (

*it

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

F(n) = F(n-1)+F(n-2)

. Она начинается со стартовых значений

F(0) = 0

F(1) = 1

. Это приводит к появлению такой последовательности чисел:

□

F(0) = 0;

□

F(1) = 1;

□

F(2) = F(1)+F(0) = 1;

□

F(3) = F(2)+F(1) = 2;

□

F(4) = F(3)+F(2) = 3;

□

F(5) = F(4)+F(3) = 5;

□

F(6) = F(5)+F(4) = 8;

□ ... и т.д.

Если мы реализуем это в форме вызываемой функции, которая возвращает значение Фибоначчи для любого числа 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;

  // сделаем что-нибудь с b, текущим числом Фибоначчи

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

++

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

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

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

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

#include

2. Определим итератор Фибоначчи,

fibit

. Он будет содержать член

, в котором будет сохраняться индекс позиции в последовательности Фибоначчи, а также члены

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

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. При использовании в цикле инкрементированный итератор сравнивается с конечным итератором, для чего следует реализовать оператор

!=

. Мы выполняем сравнение только на том шаге, на котором в данный момент находятся итераторы Фибоначчи, что позволяет проще определить конечный итератор, скажем, для шага

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

  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, на котором показана стандартная последовательность чисел, хранящаяся в итерабельном диапазоне данных. Если она содержит числа от

до

, то начальный итератор должен указывать на элемент

, а конечный итератор — на элемент, стоящий сразу после

При определении обратных итераторов итератор

rbegin

должен указывать на элемент

, а итератор

rend

— на элемент, стоящий сразу перед

. Переверните книгу вверх ногами — и убедитесь в том, что это имеет смысл.

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

std::make_reverse_iterator

, и она сделает всю работу за нас.

Завершение перебора диапазонов данных с использованием ограничителей

Как алгоритмы STL, так и основанные на диапазонах циклы

for

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

Самый простой пример такой ситуации — это перебор в стиле С простых строк, длина которых во время выполнения неизвестна. Код, итерирующий по таким строкам, обычно выглядит следующим образом:

for (const char *c_ponter = some_c_string;

 *c_pointer != '\0'; ++c_pointer)

  const char c = *c_pointer;

  // сделаем что-нибудь с переменной c

Единственный способ поработать с этими строками в основанном на диапазоне цикле

for

заключается в том, чтобы обернуть их в объект

std::string

, который поддерживает функции

begin()

end()

for (char c : std::string(some_c_string)) { /* сделаем что-нибудь с c */ }

Однако конструктор класса

std::string

будет итерировать по всей строке до того, как этим сможет заняться созданный нами цикл. В С++17 появился класс

std::string_view

, но его конструктор также один раз проитерирует по всей строке. Короткие строки не стоят таких хлопот, но это только пример одного из проблемных классов, для которого подобная возня может быть оправдана в других ситуациях. Итератор

std::istream_iterator

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

std::cin

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

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

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

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

1. Сначала, как и всегда, включим заголовочные файлы:

#include

2. Ограничитель итератора — самый важный элемент этого раздела. Удивительно, но определение его класса остается полностью пустым:

class cstring_iterator_sentinel {};

3. Теперь реализуем итератор. Он будет содержать указатель на строку, которая и станет тем контейнером, по которому мы будем итерировать:

class cstring_iterator {

 const char *s {nullptr};

4. В конструкторе просто инициализируется внутренний указатель на строку, предоставляемую пользователем. Сделаем конструктор явным, чтобы предотвратить неявные преобразования строк к строковым итераторам:

public:

  explicit cstring_iterator(const char *str)

   : s{str}

{}

5. При разыменовании итератор в какой-то момент просто вернет символьное значение в этой позиции:

  char operator*() const { return *s; }

6. Операция инкремента для итератора просто инкрементирует позицию в строке:

  cstring_iterator& operator++() {

   ++s;

   return *this;

7. Здесь начинается самое интересное. Мы реализуем оператор сравнения

!=

, который используется алгоритмами STL и основанным на диапазоне циклом

for

. Однако в этот раз мы будем реализовывать его для сравнения итераторов не с другими итераторами, а с ограничителями. При сравнении итераторов можно проверить только тот факт, что их внутренние указатели на строку указывают на один и тот же адрес; это несколько ограничивает наши возможности. Сравнивая итератор с пустым объектом-ограничителем, можно применить совершенно другую семантику: проверить, указывает ли наш итератор на завершающий символ

'\0'

, поскольку он представляет собой конец строки!

  bool operator!=(const cstring_iterator_sentinel) const {

   return s != nullptr && *s != '\0';

};

8. Чтобы использовать эту возможность в основанном на диапазоне цикле

for

, нужен класс диапазона, который предоставит конечный и начальный итераторы:

class cstring_range {

  const char *s {nullptr};

9. Единственное, что пользователь должен предоставить при создании экземпляра этого класса, — строка, по которой мы будем итерировать:

public:

  cstring_range(const char *str)

   : s{str}

{}

10. Вернем обычный итератор

cstring_iterator

из функции

begin()

, который указывает на начало строки. Из функции

end()

мы вернем тип ограничителя. Обратите внимание: без типа ограничителя мы также будем возвращать итератор, но как же узнать о достижении конца строки, если мы не нашли его заранее?

  cstring_iterator begin() const {

   return cstring_iterator{s};

  cstring_iterator_sentinel end() const {

   return {};

};

11. На этом все. Мы можем мгновенно применить итератор. Строки, которые поступают от пользователя, представляют собой лишь один пример входных данных, чью длину мы не знаем заранее. Чтобы заставить пользователя предоставить какие-нибудь входные данные, мы станем завершать работу программы, если тот не указал хотя бы один параметр при ее запуске в оболочке:

int main(int argc, char *argv[])

  if (argc < 2) {

   std::cout << "Please provide one parameter.\n";

   return 1;

12. Если программа все еще работает, то мы знаем, что в

argv[1]

содержится какая-то пользовательская строка:

  for (char c : cstring_range(argv[1])) {

   std::cout << c;

  std::cout << '\n';

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

$ ./main "abcdef"

abcdef

Цикл выводит на экран введенные нами данные, и это неудивительно, поскольку мы рассмотрели небольшой пример реализации диапазона итераторов на базе ограничителей. Такой способ завершения перебора позволит вам реализовать собственные итераторы, если вы столкнетесь с ситуацией, когда сравнение с конечной позицией не помогает.

Автоматическая проверка кода итераторов с помощью проверяемых итераторов

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

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

К счастью, спасение есть! Реализация GNU STL имеет режим отладки, а компиляторы GNU C++ и LLVM clang C++ поддерживают дополнительные библиотеки, пригодные для создания сверхчувствительных и избыточных бинарных файлов, которые будут мгновенно сообщать о большинстве ошибок. Их легко использовать, и они очень полезны, что мы и продемонстрируем в этом разделе. Стандартная библиотека Microsoft Visual C++ также предоставляет возможность проведения дополнительных проверок.

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

В этом примере мы напишем программу, которая намеренно получает доступ к некорректному итератору.

1. Сначала включим заголовочные файлы:

#include

#include

2. Теперь создадим вектор, содержащий целые числа, и получим итератор, указывающий на первый элемент, — значение

. Мы применим функцию

shrink_to_fit()

для вектора с целью убедиться, что его емкость действительно равна

, поскольку данная реализация может выделять фрагмент памяти больше необходимого, чтобы благодаря этому небольшому резерву будущие операции вставки проходили быстрее:

int main()

  std::vector v {1, 2, 3};

  v.shrink_to_fit();

  const auto it (std::begin(v));

3. Далее выведем на экран разыменованный итератор, что совершенно корректно:

  std::cout << *it << '\n';

4. Добавим в вектор новое число. Поскольку он недостаточно велик, чтобы свободно принять новое число, он автоматически увеличится в размере. Это достигается за счет выделения более крупного фрагмента памяти, перемещения всех существующих элементов в новый фрагмент и удаления старого.

  v.push_back(123);

5. Теперь снова выведем на экран значение

из вектора с помощью данного итератора. Это кончится плохо. Почему? Когда вектор переместил все свои значения в новый фрагмент памяти и удалил старый, он не сообщил итератору о текущем изменении. Т.е. итератор все еще указывает на старую позицию, и мы точно не знаем, что с тех пор произошло.

  std::cout << *it << '\n'; // плохо плохо плохо!

6. Компиляция и запуск программы приводят к идеальному выполнению. Приложение не дает сбой, но данные, которые оно выводит на экран при разыменовании некорректного указателя, выглядят совершенно случайными. В таком виде программу оставлять нельзя, но к этому моменту никто не сообщит нам о данной ошибке, если мы не заметим ее сами (рис. 3.5).

7. Ситуацию спасут флаги отладки! Реализация GNU STL поддерживает макрос препроцессора _GLIBCXX_DEBUG, который активизирует много функций для проверки достоверности STL. Это замедляет выполнение программы, но зато помогает находить ошибки. Можно активизировать макрос, добавив флаг -D_GLIBCXX_DEBUG в командную строку компилятора или определив его в начале файла кода, поместив его до директив

include

. Как видите, он завершает работу приложения, после чего запускаются разные средства очистки. Скомпилируем код с флагом для активизации проверяемых итераторов (в компиляторе Microsoft Visual C++ выглядит как /D_ITERATOR_DEBUG_LEVEL=1) (рис. 3.6).

8. Реализация STL для LLVM/clang тоже имеет флаги отладки, но они нужны для отладки самой STL, а не пользовательского кода. Для последнего можно активизировать различные средства очистки. Скомпилируем код для

clang

с помощью флагов

-fsanitize=address

-fsanitize=undefined

и посмотрим, что произойдет (рис. 3.7).

Ого! Перед нами очень точное описание того, что именно пошло не так. Если бы мы не обрезали этот скриншот, то он занял бы несколько страниц книги. Обратите внимание: это характерно не только для

clang

, но и для GCC.

Если вы видите ошибки во время выполнения программы из-за того, что отсутствует какая-то библиотека, то значит, ваш компилятор не поставляется с библиотеками

libasan

libubsan

. Попробуйте установить их с помощью вашего менеджера пакетов или чего-то аналогичного.

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

Как видите, нам ничего не нужно менять в программе, чтобы включить эту функциональность для кода, генерирующего ошибки. Мы, по сути, получили ее бесплатно, просто добавив некоторые флаги компилятора в командную строку при компиляции программы.

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

malloc

free

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

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

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

□ Использование после освобождения: ошибка происходит, если мы обращаемся к памяти кучи после того, как она была освобождена (что мы и сделали в данном разделе).

□ Переполнение переменной типа

int

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

□ Выравнивание указателя: в некоторых архитектурах невозможно обратиться к памяти, если блоки памяти выровнены неаккуратно.

Средства очистки могут обнаруживать и многие другие ошибки.

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

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

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

□ https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html;

□ http://clang.llvm.org/docs/index.html (найдите в содержании раздел Sanitizers (Средства очистки)).

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

Заняв должность разработчика в новой для вас компании, сразу убедитесь, что в вашей команде используются все доступные средства очистки. Если это не так, то у вас есть уникальный шанс исправить важные и незаметные ошибки в свой первый рабочий день!

Создаем собственный адаптер для итераторов-упаковщиков

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

Существует особый стиль программирования — чистое функциональное программирование. Он значительно отличается от императивного, к которому привыкли программисты, работающие на С и С++. Несмотря на то, что этот стиль значительно отличается от других, во многих ситуациях он позволяет писать очень элегантный код.

Один из примеров проявления данной элегантности — реализация формул, например скалярного произведения. Если даны два математических вектора, то нахождение их скалярного произведения означает попарное умножение чисел на одинаковых позициях вектора, а затем суммирование этих умноженных значений. Скалярное произведение векторов

(a,b,c)*(d,e,f)

равно

(a*e+b*e+c*f)

[6]. Конечно, это можно сделать и с помощью языков C и C++. Код выглядел бы следующим образом:

std::vector a {1.0, 2.0, 3.0};

std::vector b {4.0, 5.0, 6.0};

double sum {0};

for (size_t i {0}; i < a.size(); ++i) {

 sum += a[i] * b[i];

// sum = 32.0

Как же выглядит аналогичный код в языках, которые считаются более элегантными?

Haskell — чистый функциональный язык, на этом языке вычислить скалярное произведение двух векторов можно с помощью следующей волшебной строки (рис. 3.8).

Python не является чистым функциональным языком, но в некоторой степени использует аналогичные шаблоны, что видно в следующем примере (рис. 3.9).

В библиотеке STL вы можете найти специальный алгоритм:

std::inner_product

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

Не погружаясь в объяснения синтаксиса других языков, выделим важную деталь, которая является общей в обоих примерах, — магическую функцию

zip

. Что она делает? Принимает два вектора

и преобразует их в смешанный вектор. Например, при вызове этой функции векторы

[a1, a2, a3]

[b1, b2, b3]

будут выглядеть как

[(a1,b1), (a2,b2), (a3,b3)]

. Посмотрите на него внимательно; он работает почти так же, как и ускорители упаковки!

Важное значение имеет тот факт, что теперь вы можете проитерировать по одному объединенному промежутку, выполнив попарное умножение и сложив результаты в переменную-аккумулятор. Именно это и происходит в примерах кода на языках Haskell и Python, где не используются ни циклы, ни ненужные индексные переменные.

Код на языке C++ нельзя сделать таким же элегантным, как код на языке Haskell или Python, но в этом разделе мы поговорим о способах реализации подобных возможностей с помощью итераторов путем добавления итератора-упаковщика. Определить скалярное произведение двух векторов можно более элегантно, задействуя конкретные библиотеки, но данный вопрос не относится к теме нашей книги. Однако я пытаюсь показать, насколько библиотеки, основанные на итераторах, могут помочь при написании выразительного кода, предоставляя очень обобщенные модули.

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

В этом примере мы воссоздадим функцию

zip

, известную из языков Haskell и Python. Она будет работать только для векторов, содержащих значения типа

double

, чтобы не отвлекаться от механики итераторов.

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

#include

#include

#include

2. Далее определим класс

zip_iterator

. При переборе диапазонов данных

zip_iterator

мы будем получать на каждом этапе пару значений из двух контейнеров. Это значит, что мы итерируем по двум контейнерам одновременно:

class zip_iterator {

3. Итератор-упаковщик должен сохранять два итератора, по одному для каждого контейнера:

  using it_type = std::vector::iterator;

  it_type it1;

  it_type it2;

4. Конструктор просто сохраняет итераторы обоих контейнеров, по которым нужно проитерировать:

public:

  zip_iterator(it_type iterator1, it_type iterator2)

   : it1{iterator1}, it2{iterator2}

{}

5. Инкрементирование итератора-упаковщика означает инкрементирование обоих итераторов-членов:

  zip_iterator& operator++() {

   ++it1;

   ++it2;

   return *this;

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

ИЛИ (||)

вместо логического

И (&&)

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

  bool operator!=(const zip_iterator& o) const {

   return it1 != o.it1 && it2 != o.it2;

7. Оператор сравнения равенства реализуется с помощью другого оператора, изменяя результат его работы на противоположный:

  bool operator==(const zip_iterator& o) const {

   return !operator!=(o);

8. Разыменование итератора-упаковщика открывает доступ к обоим контейнерам в одной и той же позиции:

  std::pair operator*() const {

   return {*it1, *it2};

};

9. Мы рассмотрели код итератора. Нужно сделать итератор совместимым с алгоритмами STL, поэтому следует определить стереотипный код для типажа. По сути, он говорит, что данный итератор является обычным однонаправленным и при разыменовании возвращает пары значений типа

double

. Несмотря на то, что мы не использовали в текущем примере

difference_type

, для некоторых реализаций STL это может понадобиться для успешной компиляции кода:

namespace std {

 template <>

  struct iterator_traits {

   using iterator_category = std::forward_iterator_tag;

   using value_type = std::pair;

   using difference_type = long int;

};

10. Следующий шаг — определение класса диапазона данных, функции

begin

end

которого возвращают итераторы-упаковщики:

class zipper {

  using vec_type = std::vector;

 vec_type &vec1;

  vec_type &vec2;

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

public:

  zipper(vec_type &va, vec_type &vb)

   : vec1{va}, vec2{vb}

{}

12. Функции

begin

end

просто передают пары начальных и конечных указателей, чтобы создать с их помощью экземпляры итераторов-упаковщиков:

  zip_iterator begin() const {

   return {std::begin(vec1), std::begin(vec2)};

  zip_iterator end() const {

   return {std::end(vec1), std::end(vec2)};

};

13. Как и в примерах кода на языках Haskell и Python, определяем два вектора, содержащих значения типа

double

. Кроме того, указываем, что используем пространство имен

std

внутри функции

main

по умолчанию:

int main()

  using namespace std;

  vector a {1.0, 2.0, 3.0};

  vector b {4.0, 5.0, 6.0};

14. Объект класса

zipper

объединяет их в один диапазон данных, напоминающий вектор, где можно увидеть пары значений векторов

  zipper zipped {a, b};

15. Используем метод

std::accumulate

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

std::pair

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

std::accumulate

хорошо работает с лямбда-выражениями со следующей сигнатурой:

  const auto add_product ([](double sum, const auto &p) {

   return sum + p.first * p.second;

);

16. Теперь передадим его функции

std::accumulate

, а также пару итераторов для упаковываемых диапазонов и стартовое значение

0.0

для переменной-аккумулятора, которая, в конечном счете, будет содержать сумму произведений:

  const auto dot_product (accumulate(

   begin(zipped), end(zipped), 0.0, add_product));

17. Выведем на экран полученный результат:

  cout << dot_product << '\n';

18. Компиляция и запуск программы дадут правильный результат:

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

Да, нам пришлось написать много строк, чтобы добавить в код немного синтаксического сахара, и он все еще не так элегантен, как версия кода на Haskell. Большим недостатком является тот факт, что наш итератор-упаковщик жестко закодирован — он работает только для векторов, содержащих переменные типа

double

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

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

zip_iterator

). Ее легко использовать для самых разных классов.

Кстати, если хотите узнать о наиболее элегантном способе определения скалярного произведения в C++ и вам не особо нужна концепция итераторов-упаковщиков, то обратите внимание на

std::valarray

. Взгляните сами:

#include

#include

int main()

  std::valarray a {1.0, 2.0, 3.0};

  std::valarray b {4.0, 5.0, 6.0};

  std::cout << (a * b).sum() << '\n';

Библиотека ranges. Это очень интересная библиотека для языка C++, которая поддерживает упаковщики и все прочие виды волшебных адаптеров итераторов, фильтров и т.д. Ее создатели вдохновлялись библиотекой

Boost ranges

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

1. Определение суммы квадратов всех чисел от

до

const int sum = accumulate(view::ints(1)

            | view::transform([](int i){return i*i;})

            | view::take(10), 0);

2. Фильтрация всех четных чисел из вектора чисел и преобразование остальных чисел в строки:

std::vector v {1,2,3,4,5,6,7,8,9,10};

auto rng = v | view::remove_if([](int i){return i % 2 == 1;})

       | view::transform([](int i){return std::to_string(i);});

// rng == {"2"s,"4"s,"6"s,"8"s,"10"s};

Если вы заинтересовались и не можете дождаться выхода следующего стандарта С++, то обратитесь к документации для ranges, которая находится по адресу https://ericniebler.github.io/range-v3/.