Что такое итератор в c
Перейти к содержимому

Что такое итератор в c

  • автор:

Итераторы

Итератор — это объект, указывающий на элемент какого-то контейнера.

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

#Синтаксис

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

У всех контейнеров есть какой-то первый и последний элемент. Итератор на первый элемент можно получить через a.begin() , а через a.end() можно получить итератор на некий фиктивный элемент, следующий последним. Таким образом, если проходить от a.begin() до a.end() не включительно, ты мы пройдём по всем элементам контейнера.

::iterator»

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

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

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

  • input_iterator , поддерживающий только операции разыменования и инкремента — причём даже без гарантии, что после того, как был произведён инкремент, его предыдущие значения остались валидными. Как можно догадаться из названия, используется для потокового ввода.
  • forward_iterator , помимо предыдущего гарантирующий что итераторы на какой-то конкретный элемент можно инкрементировать сколько угодно раз не опасаясь, что они исчезнут (что позволяет их использовать в алгоритмах, проходящих по данным несколько раз).
  • bidirectional_iterator , помимо предыдущего поддерживающий возможность декремента ( it— ) — то есть перехода к предыдущему элементу.
  • random_access_iterator , помимо предыдущего поддерживающий возможность переходить к элементу, который находится на каком-то расстоянии $k$ — it + k , it — k , it += k , it -= k — и находить расстояние между позициями, на которые указывают два итератора: например, выражение a — b вернет целое число — расстояние между двумя элементами коллекции, соответствующим итераторам a и b .

#Алгоритмы из STL

Например, итераторы std::vector относятся к random_access_iterator , и если вызвать функцию lower_bound из стандартной библиотеки, то она произведет бинарный поиск по элементам (предполагая, что они отсортированы в порядке неубывания):

 Функция lower_bound возвращает итератор на первый элемент, не меньший заданного. Также есть upper_bound , возвращающий первый элемент, строго больший (в случае с int это то же самое, что найти lower_bound от x + 1 ).

Зная, что итераторы вектора поддерживают произвольный доступ, бинарный поиск будет работать за $O(n \log n)$, но для других структур это, возможно, будет не так.

Также по этой причине часто имеет смысл вместо сишных массивов использовать std::array , который является точно таким же массивом фиксированной длины, но поддерживает итераторы и вместе с ними все алгоритмы STL:

Что такое iterator в C++?

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

#include #include int main() < // Создание вектора целых чисел std::vectornumbers = ; // Использование итератора для доступа к элементам std::vector::iterator it; for (it = numbers.begin(); it != numbers.end(); ++it) < std::cout std::cout

Основные операции с итераторами:

  1. Получение начального итератора: Метод std::container::begin() возвращает итератор, указывающий на первый элемент контейнера.
  2. Получение конечного итератора: Метод std::container::end() возвращает итератор, указывающий на элемент, следующий за последним элементом контейнера.
  3. Перемещение по итераторам: Итераторы поддерживают операции инкремента ( ++ ) и декремента ( -- ), позволяя перемещаться между элементами контейнера.

Что такое итераторы и зачем они нужны

Смотрите. Пускай у вас есть контейнер. Неважно какой: map , vector , set . Он содержит набор элементов. И вы хотите сослаться не на весь контейнер, а на какое-то место в этом наборе элементов. Так чтобы от этого места можно было перейти вперёд/назад, и что-то в этом месте сделать: изменить элемент, вставить элемент, удалить элемент.

Как это сделать? Для массива вы в таких случаях пользуетесь индексом. set внутри является красно-чёрным деревом, так что вам понадобится ссылка на узел этого дерева. unordered_map использует хэш-таблицу, так что вам нужна пара из хэш-индекса и указателя на элемент внутри bucket'а.

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

Итератор — структура данных, которая «указывает» на некоторый элемент контейнера, и (для некоторых контейнеров) умеет переходить к предыдущему/следующему элементу.

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

Если вы, например, хотите реализовать RandomAccessIterator , вам придётся определить конструктор копирования, оператор присваивания, деструктор, операции == , != , * , -> , конструктор без аргументов, ++ , -- , += , + (2 шт.), -= , - (2 шт.), < , >, = . (Другие типы итераторов попроще.)

Итераторы

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

Итераторы можно использовать явным образом с помощью функций-членов и глобальных функций, таких как и end() операторы, такие как -- begin() ++ и перемещение вперед или назад. Кроме того, можно использовать итераторы неявно с диапазоном для цикла или (для некоторых типов итератора) подстрочного оператора [] .

В стандартной библиотеке С++ началом последовательности или диапазона является первый элемент. Конец последовательности или диапазона всегда определяется как элемент, следующий за последним элементом. Глобальные функции begin и возвращают итераторы end в указанный контейнер. Типичный цикл явных итераторов, включающий все элементы, выглядит следующим образом:

vector vec< 0,1,2,3,4 >; for (auto it = begin(vec); it != end(vec); it++) < // Access element using dereference operator cout

Того же можно достичь более простым способом, с помощью цикла range-for:

for (auto num : vec) < // no dereference operator cout

Существует пять категорий итераторов. Ниже описаны категории в порядке возрастания силы.

  • Выход. Выходной итератор X может выполнять итерацию по последовательности с помощью ++ оператора и может записывать элемент только один раз с помощью * оператора.
  • Ввод. Входной итератор X может выполнять итерацию по последовательности с помощью ++ оператора и читать элемент в любое количество раз с помощью * оператора. Вы можете сравнить входные итераторы с помощью == операторов и != операторов. После увеличения любой копии входного итератора ни одна из других копий не может быть безопасно сравниваема, разыменовывается или увеличивается после этого.
  • Переслать. Переадресация итератора X может выполнять итерацию по последовательности с помощью оператора ++ и может считывать любой элемент или записывать элементы, отличные от const, с помощью * оператора. Вы можете получить доступ к элементам элемента с помощью -> оператора и сравнения переадресации итераторов с помощью == операторов и != операторов. Вы можете сделать несколько копий однонаправленного итератора, каждая из которых может быть разыменована и для нее может быть выполнено независимое приращение. Итератор пересылки, который инициализирован без ссылки на любой контейнер, называется итератором пересылки null. Пустые однонаправленные итераторы всегда равны.
  • Двунаправленный. Двунаправленный итератор может занять место итератора X вперед. Однако можно также уменьшать двунаправленный итератор, как и в --X , X-- или (V = *X--) . Получить доступ к членам элементов и сравнить двунаправленные итераторы можно так же, как и однонаправленные итераторы.
  • Произвольный доступ. Итератор случайного доступа может занять место двунаправленного итератора X . С помощью итератора случайного доступа можно использовать оператор [] подстрока для доступа к элементам. Вы можете использовать + - += операторы и -= операторы для перемещения вперед или назад указанного количества элементов и вычисления расстояния между итераторами. Вы можете сравнить двунаправленные итераторы с помощью == , , , < , >и = . !=

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

Иерархия категорий итераторов может быть представлена в виде трех последовательностей. Для доступа в режиме только для записи в последовательность можно использовать любой из следующих итераторов.

итератор вывода
—> переадресация итератора
—> двунаправленный итератор
—> итератор случайного доступа

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

Для доступа в режиме только для чтения в последовательность можно использовать любой из следующих итераторов.

итератор ввода
—> переадресация итератора
—> двунаправленный итератор
—> итератор случайного доступа

Итератор ввода является самым слабым по всем категориям в этом смысле.

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

итератор пересылки
—> двунаправленный итератор
—> итератор случайного доступа

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

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

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

Вы можете избежать явного использования итераторов с помощью циклов range-for. Дополнительные сведения см. в разделе "Диапазон" для инструкции.

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

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

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