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

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

  Обновл. 27 Июл 2020  | 

 6053

 ǀ   2 

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

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

Итерация/перемещение по элементам массива (или какой-нибудь другой структуры) является довольно распространенным действием в программировании. Мы уже рассматривали множество различных способов выполнения данной задачи, а именно: с использованием циклов и индексов (циклы 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 (46 оценок, среднее: 4,91 из 5)
Загрузка...

Комментариев: 2

  1. Аватар Александр:

    Что такое std::size_t и что такое std::size, где о них можно почитать? У вас в уроках нет никаких даже минимальных пояснений.

    1. Аватар Steindvart:

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

      То есть, простыми словами говоря, это тип для безнаковых целых чисел, которые связаны с адресацией памяти. Так как адрес не может быть:
      1. Отрицательным
      2. Дробным

      Универсальный он потому, что его размер подстраивается под конкретную платформу. То есть размер адреса может быть разным на разных машинах: например, 32-битные и 64-битные системы. Где "битность" означает кол-во битов отведённые под представление адреса в памяти. Используя size_t, размер типа будет соответствовать размерам адреса платформы.

      Как правило, он определяется в том или ином заголовочном файле в виде:
      typedef unsigned long size_t или typedef unsigned int size_t, в зависимости от платформы.

      std::size() – функция, которая возвращает размер контейнера или стандартного статического массива (так как его размер известен компилятору).

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

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