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

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

  |

  Обновл. 15 Сен 2021  | 

 43584

 ǀ   9 

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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 вещи:

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

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

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

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

Итераторы и циклы 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 (139 оценок, среднее: 4,87 из 5)
Загрузка...

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

  1. mojoRising:

    есть такой вопрос ещё, auto begin{ &data[0] } — я так понимаю компилятор сам понимает что создаётся указатель? просто до этого момента для создания указателя необходимо было использовать *, а информации об автоматическом определении не было

    1. Виталий:

      auto begin{ &data[0] } это тоже что и int *begin = &data[0];

      1. Fray:

        Если попытаться вывести тип с помощью typeid, то выведется:

        Что явно не похоже на указатель int*.
        И вывести begin в консоль, как будто мы пытаемся вывести указатель, не получится, если конечно не использовать амперсанд и оператор разыменования.

    2. Павел:

      Ключевое слово auto может использоваться при инициализации переменной для выполнения вывода типа. Так как &data[0] является адресом, то принять его может указатель соответствующего типа.

      https://ravesli.com/urok-62-klyuchevoe-slovo-auto-vyvod-tipov/#toc-2

  2. Максим:

    В первом примере циклы for прописаны так:

    и далее во всех примерах с указателями для определения завершения цикла используется оператор "!=" (но не оператор "<").

    Подскажите, корректно ли в циклах for с указателями на массив использовать операторы "<", ">" ?
    Или как-то неправильно сравнивать указатели друг с другом на предмет: кто больше, кто меньше?

    На практике все работает.
    Прикладываю код со сравнением указателей друг с другом в циклах:

    1. Артурка:

      Так как в array используется random access iterator, то у него перегружены операторы типа:

      но в том же std::forward_list таких перегрузок нету, но есть перегрузки типа:

      По этому подход с последними операторами более универсальный.
      ПОдробнее:
      http://www.cplusplus.com/reference/iterator/RandomAccessIterator/
      http://www.cplusplus.com/reference/iterator/ForwardIterator/

  3. Александр:

    Что такое 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() – функция, которая возвращает размер контейнера или стандартного статического массива (так как его размер известен компилятору).

      1. Fray:

        Большое спасибо за разъяснения!

Добавить комментарий для Виталий Отменить ответ

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