Введение в итераторы в С++

  Дмитрий Бушуев  | 

  Обновл. 8 Фев 2020  | 

 764

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

Итерация по элементам структур данных

Итерация/Перемещение по элементам массива (или какой-нибудь другой структуры) является довольно распространённым действием в программировании. Мы уже рассматривали множество различных способов выполнения данной задачи, а именно: с использованием циклов и индексов (циклы for и while), с помощью указателей и арифметики указателей, а также с помощью циклов for с явным указанием диапазона:

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

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

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

Примечание для продвинутых читателей: Указатели (без арифметики указателей) могут использоваться для перебора/итерации некоторых структур данных с непоследовательным расположением элементов. Например, в связном списке каждый элемент соединён указателем с предыдущим элементом, поэтому мы можем перебирать список, следуя по цепочке указателей.

Циклы for с явным указанием диапазона чуть более интересны, поскольку у них скрыт механизм перебора нашего контейнера, но при всём при этом, они всё равно могут быть применены к различным структурам данных (массивы, списки, деревья, карты и т.д.). «Как же они работают?» — спросите вы. Они используют итераторы.

Итераторы в С++


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

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

После того, как итератор соответствующего типа создан, программист может использовать интерфейс, предоставляемый данным итератором, для перемещения по элементам контейнера или доступа к его элементам, не беспокоясь при этом о том, какой тип перебора элементов задействован или каким образом в контейнере хранятся данные. И, поскольку итераторы в С++ обычно используют один и тот же интерфейс как для перемещения по элементам контейнера (operator++ для перехода к следующему элементу), так и для доступа (operator* для доступа к текущему элементу), то итерации можно выполнять по разнообразным типам контейнеров, используя последовательный метод.

Указатели в качестве итераторов

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

Результат выполнения программы выше:

0 1 2 3 4 5 6

В примере выше мы определили две переменные: begin (которая указывает на начало нашего контейнера) и end (которая указывает на конец нашего контейнера). Для массивов конечным маркером обычно является место в памяти, где находился бы последний элемент, если бы контейнер содержал бы ещё один элемент.

Затем указатель перемещается между begin и end, при этом доступ к текущему элементу можно получить с помощью оператора разыменовывания.

Предупреждение: У вас может появиться соблазн вычислить конечную точку, используя оператор адреса(&) следующим образом:

Но это приведёт к неопределённому поведению, потому что array[std::size(array)] обращается к элементу, который находится за пределами массива.

Вместо этого следует использовать:

Итераторы Стандартной Библиотеки С++


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

Результат выполнения программы выше:

1 2 3

В заголовочном файле <iterator> также содержатся две обобщенные функции (std::begin() и std::end()):

Результат выполнения аналогичен предыдущему:

1 2 3

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

   начальная точка;

   конечная точка;

   operator++ для перемещения итератора к следующему элементу (или к концу);

   operator* для получения значения текущего элемента.

Итераторы и циклы for с явным указанием диапазона

Все типы данных, которые имеют методы begin() и end() или используются с std::begin() и std::end(), могут быть задействованы в циклах for с явным указанием диапазона:

На самом деле, циклы for с явным указанием диапазона для осуществления итерации незаметно обращаются к вызовам функций begin() и end(). Тип данных std::array также имеет в своём арсенале методы begin() и end(), а значит и его мы можем использовать в циклах for с явным указанием диапазона. Массивы C-style с фиксированным размером также можно использовать с функциями std::begin() и std::end(). Однако с динамическими массивами данный способ не работает, так как для них не существует функции std::end() (из-за того, что отсутствует информация о длине массива).

Позже вы узнаете, как добавлять функционал к вашим типам данным так, чтобы их можно было использовать и с циклами for с явным указанием диапазона.

Циклы for с явным указанием диапазона используются не только при работе с итераторами. Они также могут быть задействованы вместе с std::sort и другими алгоритмами. Теперь, когда вы знаете, что это такое, вы можете заметить, что они довольно часто используются в стандартной библиотеке.

«Висячие» итераторы


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

Некоторые операции, которые изменяют контейнеры (например, добавление элемента в std::vector), могут иметь побочный эффект, приводя к изменению адресов элементов контейнера. Когда такое происходит, текущие итераторы для этих элементов считаются недействительными. Хорошая справочная документация по C++ обязательно должна иметь информацию о том, какие операции с контейнерами могут привести или приведут к инвалидации итераторов (в качестве примера вот справочная информация по «инвалидации итераторов» в std::vector).

Вот пример подобной ситуации:

В следующем уроке мы рассмотрим алгоритмы стандартной библиотеки C++.

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (4 оценок, среднее: 5,00 из 5)
Загрузка...

Добавить комментарий

Ваш E-mail не будет опубликован. Обязательные поля помечены *