Итераторы

Последнее обновление: 03.11.2017

Итераторы обеспечивают доступ к элементам контейнера. С помощью итераторов очень удобно перебирать элементы. Итератор описывается типом iterator. Но для каждого контейнера конкретный тип итератора будет отличаться. Так, итератор для контейнера представляет тип list<int>::iterator, а итератор контейнера представляет тип vector<int>::iterator и так далее.

Для получения итераторов контейнеры в C++ обладают такими функциями, как begin() и end(). Функция begin() возвращает итератор, который указывает на первый элемент контейнера (при наличии в контейнере элементов). Функция end() возвращает итератор, который указывает на следующую позицию после последнего элемента, то есть по сути на конец контейнера.

Итераторы библиотеки STL

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

Обе этих функции возвращают итератор для конкретного типа контейнера:

std::vector<int> v = { 1,2,3,4 }; std::vector<int>::iterator iter = v.begin(); // получаем итератор

В данном случае создается вектор — контейнер типа vector, который содержит значения типа int. И этот контейнер инициализируется набором {1, 2, 3, 4}. И через метод можно получить итератор для этого контейнера. Причем этот итератор будет указывать на первый элемент контейнера.

Операции с итераторами

С итераторами можно проводить следующие операции:

• *iter: получение элемента, на который указывает итератор

• ++iter: перемещение итератора вперед для обращения к следующему элементу

• —iter: перемещение итератора назад для обращения к предыдущему элементу. Итераторы контейнера forward_list не поддерживают операцию декремента.

• iter1 == iter2: два итератора равны, если они указывают на один и тот же элемент

• iter1 != iter2: два итератора не равны, если они указывают на разные элементы

Например, используем итераторы для перебора элементов вектора:

#include <iostream> #include <vector> int main() { std::vector<int> v = {1, 2, 3, 4, 5}; auto iter = v.begin(); // получаем итератор while(iter!=v.end()) // пока не дойдем до конца { std::cout << *iter << std::endl;// получаем элементы через итератор ++iter; // перемещаемся вперед на один элемент } return 0; }

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

Итераторы позволяют не только получать элементы, но и изменять их:

#include <iostream> #include <vector> int main() { std::vector<int> v = {1, 2, 3, 4, 5}; auto iter = v.begin(); while(iter!=v.end()) // пока не дойдем до конца { *iter = (*iter) * (*iter); // возводим число в квадрат ++iter; } for(iter = v.begin(); iter!=v.end(); ++iter) { std::cout << *iter << std::endl; } return 0; }

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

Константные итераторы

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

const vector<int> v = {1, 2, 3, 4, 5}; for(auto iter = v.begin(); iter != v.end(); ++iter) { std::cout << *iter << std::endl; // так нельзя сделать //*iter = (*iter) * (*iter); }

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

#include <iostream> #include <vector> int main() { std::vector<int> v = { 1, 2, 3, 4, 5 }; for (std::vector<int>::const_iterator iter = v.cbegin(); iter != v.cend(); ++iter) { std::cout << *iter << std::endl; // так нельзя сделать, так как итератор константный //*iter = (*iter) * (*iter); } return 0; }

Реверсивные итераторы

Реверсивные итераторы позволяют перебирать элементы контейнера в обратном направлении. Для получения реверсивного итератора применяются функции rbegin() и rend(), а сам итератор представляет тип :

#include <iostream> #include <vector> int main() { std::vector<int> v = { 1, 2, 3, 4, 5 }; for (std::vector<int>::reverse_iterator iter = v.rbegin(); iter != v.rend(); ++iter) { std::cout << *iter << std::endl; } std::cout << «\n»; return 0; }

Консольный вывод программы:

Если надо обеспечить защиту от изменения значений контейнера, то можно использовать константный реверсивный итератор, который представлен типом const_reverse_iterator и который можно получить с помощью функций crbegin() и crend():

#include <iostream> #include <vector> int main() { std::vector<int> v = { 1, 2, 3, 4, 5 }; for (std::vector<int>::const_reverse_iterator iter = v.crbegin(); iter != v.crend(); ++iter) { std::cout << *iter << std::endl; // так нельзя сделать, так как итератор константный //*iter = (*iter) * (*iter); } return 0; }

Также итераторы для всех типов, кроме list и forward_list, поддерживают ряд дополнительных операций:

• iter + n: возвращает итератор, который перещен от итератора iter на n позиций вперед

• iter — n: возвращает итератор, который перещен от итератора iter на n позиций назад

• iter += n: перемещает итератор на n позиций вперед

• iter -= n: перемещает итератор на n позиций назад

• iter1 — iter2: возвращает количество позиций между итераторами iter1 и iter2

• >, >=, <, <=: операции сравнения. Один итератор больше другого, если указывает на элемент, который ближе к концу

Применение некоторых операций:

std::vector<int> v = {1, 2, 3, 4, 5}; auto iter1 = v.begin(); auto iter2 = iter1 + 2; std::cout << *iter2 << std::endl; // 3 bool res = iter2 > iter1; // true std::cout << res << std::endl;

Итераторы

Последнее обновление: 25.04.2018

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

Интерфейс Iterator имеет следующее определение:

public interface Iterator <E>{ E next(); boolean hasNext(); void remove(); }

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

Контейнеры, итераторы, функторы, алгоритмы

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

Используем итератор для перебора коллекции ArrayList:

import java.util.*; public class Program { public static void main(String[] args) { ArrayList<String> states = new ArrayList<String>(); states.add(«Germany»); states.add(«France»); states.add(«Italy»); states.add(«Spain»); Iterator<String> iter = states.iterator(); while(iter.hasNext()){ System.out.println(iter.next()); } } }

Интерфейс Iterator предоставляет ограниченный функционал. Гораздо больший набор методов предоставляет другой итератор — интерфейс ListIterator. Данный итератор используется классами, реализующими интерфейс , то есть классами LinkedList, ArrayList и др.

Интерфейс ListIterator расширяет интерфейс Iterator и определяет ряд дополнительных методов:

• void add(E obj): вставляет объект obj перед элементом, который должен быть возвращен следующим вызовом

• boolean hasNext(): возвращает , если в коллекции имеется следующий элемент, иначе возвращает false

• boolean hasPrevious(): возвращает , если в коллекции имеется предыдущий элемент, иначе возвращает false

• E next(): возвращает текущий элемент и переходит к следующему, если такого нет, то генерируется исключение

• E previous(): возвращает текущий элемент и переходит к предыдущему, если такого нет, то генерируется исключение

• int nextIndex(): возвращает индекс следующего элемента. Если такого нет, то возвращается размер списка

• int previousIndex(): возвращает индекс предыдущего элемента. Если такого нет, то возвращается число -1

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

• void set(E obj): присваивает текущему элементу, выбранному вызовом методов или , ссылку на объект obj

Используем ListIterator:

import java.util.*; public class Program { public static void main(String[] args) { ArrayList<String> states = new ArrayList<String>(); states.add(«Germany»); states.add(«France»); states.add(«Italy»); states.add(«Spain»); ListIterator<String> listIter = states.listIterator(); while(listIter.hasNext()){ System.out.println(listIter.next()); } // сейчас текущий элемент — Испания // изменим значение этого элемента listIter.set(«Португалия»); // пройдемся по элементам в обратном порядке while(listIter.hasPrevious()){ System.out.println(listIter.previous()); } } }

Использование Iterable

Тип iterable может использоваться как тип параметра, чтобы указать, что функция принимает набор значений, но ей не важна форма этого набора, пока поскольку он будет использоваться с foreach. Если значение не является массивом или объектом, реализующий Traversable, будет выброшено исключение TypeError.

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

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

Функции, объявляющие iterable как возвращаемый тип, также могут быть генераторы.

Приведение типа iterable

Наследующие/реализующие классы могут расширять методы, использующие array или Traversable в качестве типов параметров до iterable или ограничить возвращаемые типы с iterable до array или Traversable.