Итератор

Материал из Algocode wiki
Версия от 12:45, 28 ноября 2019; Gutrov Egor (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

  • InputIterator. Он поддерживает только операции разыменования и инкремента, притом после того, как был произведён инкремент, все копии его предыдущего значения могут стать невалидными.
  • ForwardIterator. Поддерживает то же, что и InputIterator, но итератор, указывающий на какой-то конкретный элемент, можно инкрементировать сколько угодно раз.
  • BidirectionalIterator. Поддерживает то же, что и ForwardIterator, но также есть возможность производить декремент (it--) — переходить к предыдущему элементу коллекции.
  • RandomAccessIterator. Поддерживает то же, что и BidirectionalIterator, но также есть возможность переходить к элементу коллекции, который находится от данного на каком-то расстоянии $k$. Так, например, для итератора it возможны следующии операции: it + k, it - k, it += k, it -= k. Также можно находить расстояние между двумя позициями, на которые указывают итератора. Так, например, выражение a - b будет означать расстояние между двумя элементами коллекции, на которые указывают итераторы a и b.

Рассмотрим использование итераторов на примере vector. Для вектора a итератор на его первый элемент можно получить так: a.begin(). Также есть функция, которая возвращает итератор на фиктивный элемент, следующий за последним элементом вектора: a.end(). Таким образом, весь a задаётся полуинтервалом [a.begin(); a.end()) (левый конец включается, правый — нет). Итераторы у vector относятся к категории RandomAccessIterator, то есть например мы можем узнать размер вектора a, просто взяв a.begin() - a.end(). При этом у vector типа vector<T> итератор будет иметь тип vector<T>::iterator. Рассмотрим пример работы с итераторами у vector.

vector<int> a = {1, -2, 3, 100};

vector<int>::iterator first_element = a.begin();
cout << *first_element << "\n"; // выведет 1
first_element++;
cout << *first_element << "\n"; // выведет -2
first_element--;
cout << *first_element << "\n"; // выведет 1
auto third_element = first_element + 2; // используем тип auto, чтобы не писать длинное имя типа
cout << *third_element << "\n"; // выведет 3
cout << (third_element - first_element) << "\n"; // выведет 2

// вывод всех элементов вектора с использованием итераторов
for (auto it = a.begin(); it != a.end(); it++) {
    cout << *it << " ";
}
cout << "\n"; // но для таких целей лучше использовать range-based for loop:
  
for (auto& it : a) {
    cout << a << " ";
}



Автор конспекта: Егор Гутров

По всем вопросам пишите в telegram @Egor_Gutrov