# Глава 6.1. Что такое итератор Стандартная библиотека C++ содержит три важных элемента: - Контейнеры, реализующие различные структуры данных. - Алгоритмы для работы с контейнерами: сортировка, поиск и многое другое. - Итераторы — связующее звено между контейнерами и алгоритмами. ## STL Контейнеры, алгоритмы, итераторы и ещё некоторые компоненты стандартной библиотеки иногда обобщённо называют [STL](https://en.wikipedia.org/wiki/Standard_Template_Library) (Standard Template Library, стандартная библиотека шаблонов). На самом деле STL — это написанная в 90-х сторонняя библиотека, части из которой переехали в стандарт C++. Если в обиходе вы услышите название STL, то скорее всего имеется ввиду просто конкретное подмножество стандартной библиотеки. Начнем знакомство с итераторами. А в следующих главах взглянем на многообразие контейнеров и алгоритмов стандартной библиотеки. ## Концепция итератора **Итератор** (iterator) — это абстракция для доступа к элементам контейнера. Через объект итератора можно обходить элементы в цикле или работать с ними поштучно. Итератор — это распространённый [паттерн проектирования.](https://ru.wikipedia.org/wiki/%D0%98%D1%82%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_(%D1%88%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD_%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F)) На уровне стандартной библиотеки он реализован и в других языках, например в C# и Rust. Какую задачу решает паттерн «итератор»? Представьте, что вы автор стандартной библиотеки C++. Вы создали набор контейнеров, среди которых массивы, хеш-таблицы, списки, очереди. Но контейнеров самих по себе недостаточно. Нужно предоставить алгоритмы для работы с ними: поиск, сортировку, слияние, фильтрацию и другие функции. Как это сделать? Можно каждый из алгоритмов превратить в метод класса контейнера. Но у такого подхода есть недостатки: - Перегруженный интерфейс класса. Придется добавлять сотни публичных методов! - Дублирование одних и тех же алгоритмов для разных контейнеров. - Плохая масштабируемость. Чтобы добавить алгоритм, придётся дополнить все контейнеры новым методом. - Нет разграничения ответственности между кодом, реализующим структуру данных, и кодом алгоритма для обработки данных. Зачем классу `std::string` знать, как устроен бинарный поиск? Альтернативный подход заключается в использовании итераторов. Каждому классу контейнера соответствует свой класс итератора. Например, итератор по массиву или итератор по списку. Объект итератора имеет доступ к элементам контейнера и умеет их перебирать. Алгоритмы для работы с контейнерами оформляются в виде свободных функций, которые принимают на вход итераторы. Это даёт преимущества: - Интерфейс класса контейнера содержит только самое необходимое. Таким классом удобно пользоваться. - Отсутствует дублирование кода. - Гибкость. Алгоритмы можно применять к контейнеру целиком или к диапазону элементов. - Разделение обязанностей между кодом класса контейнера и кодом функции, реализующей алгоритм. Такое разделение позволяет развивать контейнеры и алгоритмы независимо друг от друга. Посмотрим, как выглядит использование связки контейнеров, алгоритмов и итераторов. Заведем строку `s` и динамический массив `v`. Оба контейнера имеют методы `begin()` и `end()`. Они возвращают итераторы на первый элемент и на позицию за последним элементом. Вызовем [функцию std::reverse(),](https://en.cppreference.com/w/cpp/algorithm/reverse) которая меняет порядок элементов на обратный. Она принимает итераторы на начало и конец диапазона, который нужно «перевернуть»: {#block-vector} ```cpp {.example_for_playground .example_for_playground_001} std::string s = "spam"; std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; std::reverse(s.begin(), s.end()); std::reverse(v.begin(), v.end()); std::println("Reversed.\nString: {}. Vector: {}", s, v); ``` ``` Reversed. String: maps. Vector: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] ``` Итераторы полезны и для написания собственных алгоритмов. Ведь они предоставляют гибкий и _единообразный_ доступ к элементам контейнеров разных типов. А значит, функции не надо знать, с элементами какого контейнера она работает. ## Реализация итераторов в C++ У каждого контейнера есть свой тип итератора. Тип итератора по строке — `std::string::iterator`, а итератор по массиву `std::vector<int>` — `std::vector<int>::iterator`. Здесь полное имя типа состоит из компонентов: - `std` — пространство имён. - `vector` — класс динамически изменяемого массива. - `int` — аргумент шаблонного класса `vector`. Это тип элементов контейнера. - `iterator` — класс, реализованный внутри другого класса. То есть вложенный в `vector`. Тип и реализация у всех итераторов разные, но работать с контейнерами они позволяют одинаково. Разберем это на примере цикла по строке. Вы успели познакомиться с двумя вариантами перебора строки: циклом `for` по индексам и циклом `range-for` по символам: ```cpp {.example_for_playground .example_for_playground_002} std::string s = "string"; for (std::size_t i = 0; i < s.size(); ++i) std::println("{}", s[i]); for (char c: s) std::println("{}", c); ``` Но в отличие от строки не каждый контейнер поддерживает доступ к элементам по индексам. А цикл `range-for` перебирает все элементы диапазона без возможности задания шага, начальных и конечных условий. Поэтому в ряде случаев необходим третий способ организации циклов — через итераторы. Цикл через итераторы абсолютно одинаков для строк, массивов и _любых_ контейнеров: ```cpp {.example_for_playground .example_for_playground_003} for(std::string::iterator it = s.begin(); it != s.end(); ++it) std::println("{}", *it); ``` Методы `begin()` и `end()` есть у всех контейнеров стандартной библиотеки: - `begin()` возвращает итератор, указывающий на начальный элемент. - `end()` возвращает итератор на позицию **за** последним элементом.  {.illustration} ## Основные действия над итераторами Есть несколько **операторов,** которые применимы к итераторам **всех** контейнеров: - `==`, `!=` — строгое сравнение на равенство и неравенство. - `*` — оператор разыменования. Он выглядит, как оператор умножения, но имеет другой смысл. Он нужен для обращения к элементу, на который указывает итератор: `std::println("{}", *it)`. Итератор, возвращаемый методом `end()`, разыменовывать нельзя. - `++` — перемещение к следующему элементу. Но есть и такие операторы, которые реализованы только для итераторов **некоторых** контейнеров: - `>`, `>=`, `<`, `<=` — сравнение «больше-меньше». Итератор больше другого, если он ближе к концу контейнера. - `--` — перемещение к предыдущему элементу: `--it`. - `+`, `-`, `+=`, `-=` — перемещение на заданное количество элементов: `it - 5` означает получение итератора на 5 элементов ближе к началу контейнера, а `it += 2` — сдвиг `it` на 2 элемента к концу. Почему эти операторы поддерживаются не везде? Дело в специфике контейнера. Например, каждый элемент односвязного списка ссылается лишь на следующий элемент и не обладает информацией о предыдущем. Поэтому к итератору контейнера `std::forward_list` применимы только операторы `==`, `!=`, `*` и `++`. ## Категории итераторов В зависимости от того, какие над итератором допустимы действия, итератор относится к одной из категорий: {#block-iterator-categories} - Чтение значений элементов (input). - Запись значений (output). - Прямое итерирование (forward): перебор элементов с начала к концу. - Двунаправленное итерирование (bidirectional): перебор элементов в любом направлении. - Произвольный доступ к любым элементам (random access). Чтобы показать, как эти категории соотносятся друг с другом, их можно представить вложенными друг в друга. Итераторы, изображённые внешними, обладают наибольшими возможностями.  {.illustration} Итераторы по каждому из стандартных контейнеров относятся к одной из этих категорий. Например, итераторы по строке являются итераторами произвольного доступа. Так выглядит изменение символов строки в цикле по итераторам: ```cpp {.example_for_playground .example_for_playground_004} std::string s = "iteration over string"; for(std::string::iterator it = s.begin(); it != s.end(); ++it) { if (*it == ' ') *it = '_'; } std::println("{}", s); ``` ``` iteration_over_string ``` Перебирать контейнеры можно и с помощью цикла `while`: ```cpp {.example_for_playground .example_for_playground_018} std::string card = "MasterCard N:5200 8282 8282 8210"; std::size_t hide_count = 12; std::string::iterator it = card.begin(); while (it != card.end() && hide_count > 0) { if (*it >= '0' && *it <= '9') { *it = '*'; --hide_count; } ++it; } std::println("{}", card); ``` ``` MasterCard N:**** **** **** 8210 ``` Напишите функцию `is_palindrome()`, которая принимает строку и определяет, является ли строка палиндромом. Палиндром — это строка, одинаково выглядящая в обоих направлениях. Например, `"eve"`, `"sum summus mus"`. Пустая строка палиндромом не считается. {.task_text} В своём решении используйте итераторы. {.task_text} ```cpp {.task_source #cpp_chapter_0061_task_0020} bool is_palindrome(std::string text) { } ``` Чтобы проверить, является ли строка палиндромом, нужно сравнить её нулевой символ с последним, первый — с предпоследним и так до середины строки. {.task_hint} ```cpp {.task_answer} bool is_palindrome(std::string text) { if (text.empty()) return false; std::string::iterator it = text.begin(); std::string::iterator it_tail = text.end() - 1; const std::string::iterator it_end = text.begin() + text.size() / 2; while (it != it_end) { if (*it != *it_tail) return false; ++it; --it_tail; } return true; } ``` Многие алгоритмы стандартной библиотеки используют итераторы в качестве параметров функции или возвращаемого значения. Так, [std::find_if()](https://en.cppreference.com/w/cpp/algorithm/find) принимает итераторы на границы интересующего диапазона и предикат (функцию, возвращающую `true` либо `false`). Начальный элемент диапазона участвует в поиске, а последний — нет. Функция возвращает итератор на первый элемент внутри диапазона, для которого предикат вернул `true`. Если такого элемента нет, функция возвращает итератор на последний элемент диапазона. {#block-find-if} А [std::distance()](https://en.cppreference.com/w/cpp/iterator/distance) принимает итераторы на границы диапазона. И возвращает, сколько элементов расположено между этими границами, включая начальный элемент диапазона и не включая последний. {#block-distance} ```cpp {.example_for_playground} import std; // Параметром шаблона может быть литерал простого типа, // в данном случае любой ASCII символ template<char Sym> bool expected(char c) { return c == Sym; } // Параметр шаблона - функция-предикат template <typename Pred> void print_distance(std::string str, Pred pred) { const std::string::iterator it = std::find_if(str.begin(), str.end(), pred); if (it == str.end()) { std::println("a character cannot be found by predicate"); } else { const auto d = std::distance(str.begin(), it); std::println("distance to '{}' is {}", *it, d); } } int main() { std::string menu_item = "FAQ"; print_distance(menu_item, expected<'F'>); print_distance(menu_item, expected<'A'>); print_distance(menu_item, expected<'Q'>); print_distance(menu_item, expected<'X'>); } ``` ``` distance to 'F' is 0 distance to 'A' is 1 distance to 'Q' is 2 a character cannot be found by predicate ``` Важно знать, что `std::distance()` может вернуть _отрицательное_ значение. Это допустимо, если переданы итераторы произвольного доступа (random access), а итератор на начало диапазона достижим из итератора на конец: ```cpp std::string menu_item = "FAQ"; std::println("{}", std::distance(menu_item.end(), menu_item.begin())); ``` ``` -3 ``` Напишите шаблонную функцию `index_of()`. Функция принимает строку и предикат. Тип предиката является параметром шаблона. Функция возвращает индекс первого символа, для которого предикат вернул `true`. Если такого символа нет, функция должна бросить исключение `std::runtime_error`. {.task_text} В своём решении используйте алгоритмы `std::find_if()` и `std::distance()`. {.task_text} ```cpp {.task_source #cpp_chapter_0061_task_0010} ``` У шаблона единственный параметр — тип предиката. Назовем его `Fn`. Тогда функция будет выглядеть так: `template<class Fn> std::size_t index_of(std::string s, Fn pred)`. Внутри функции нужно вызвать `std::find_if()` от итераторов на начало и конец строки и предиката `pred`. Если итератор, который вернёт `std::find_if()`, равен `s.end()`, нужно бросить исключение. Иначе вернуть расстояние от начала строки до этого итератора. Для этого вызовите функцию `std::distance()`. {.task_hint} ```cpp {.task_answer} template<class Fn> std::size_t index_of(std::string s, Fn pred) { std::string::iterator it = std::find_if( s.begin(), s.end(), pred); if (it == s.end()) throw std::runtime_error("not found"); return std::distance(s.begin(), it); } ``` ---------- ## Резюме - Итераторы — это абстракция для доступа к элементам контейнера. - Они позволяют единообразно работать с элементами контейнеров разных типов. - Контейнеры, алгоритмы и итераторы — это важные компоненты стандартной библиотеки. - Паттерн проектирования «итератор» есть и в стандартных библиотеках других языков, например в C# и Rust. - Итераторы, контейнеры, алгоритмы и ещё некоторые компоненты стандартной библиотеки C++ иногда называют STL (Standard Template Library). - От категории итератора зависит, какие над ним допустимы действия: - input — чтение значений перебираемых элементов, - output — запись значений, - forward — перебор элементов с начала к концу, - bidirectional — перебор элементов в любом направлении, - random access — произвольный доступ к любым элементам.