Розділ 11. Алгоритми

11.1 Ітератори

Ітератор – це узагальнення поняття вказівки для роботи з різними структурами даних стандартним способом. Для того, щоб можна було реалізувати алгоритми, які коректно і ефективно працюють з даними різної структури, стандарт визначає не тільки інтерфейс, але й вимоги до часу доступу за допомогою ітераторів. Оскільки ітератор є узагальненням поняття "вказівка", семантика у них однакова, і всі функції, що приймають в якості параметрів ітератори, можуть також працювати із звичайними вказівками. У стандартній бібліотеці ітератори використовуються для роботи з контейнерними класами, потоками і буферами потоків.

У ітераторах використовуються поняття "Поточний вказуваний елемент" і "вказати на наступний елемент". Доступ до поточного елементу послідовності виконується аналогічно вказівкам за допомогою операцій "*" та "->". Перехід до наступного елементу – за допомогою операції інкремента ++. Для всіх ітераторів визначені також привласнення, перевірка на рівність і нерівність.

Дані можуть бути організовані різним чином – наприклад, у вигляді масиву, списку, вектора або дерева. Для кожного виду послідовності потрібний свій тип ітератора, що підтримує різні набори операцій. Відповідно до набору забезпечуваних операцій ітератори діляться на п'ять категорій, описаних в таблиці 11.1.

Нехай i та j – ітератори одного виду, х – змінна того ж типу, що і елемент послідовності, n – ціла величина. Тоді допустимі вирази:

i++ ; ++i; i = j; i!=j

Таблиця 11.1 Категорії ітераторів

Категорія ітератора	Операції	Контейнери
вхідний (input)	x = *i	всі
вихідний (output)	*i = x	всі
прямий (forward)	x = * i , * i = x	всі
двонаправлений (bidirectional)	x = *i , *i = x, -- i , i--	всі
довільного доступу (random access)	x = *i , *i = x, -- i , i--, i + n, i - n, i += n, i -= n, i < j , i > j , i <= j , i >= j	всі, окрім list

Ітераторні класи і функції описані в заголовному файлі <iterator>. При використанні стандартних контейнерів цей файл підключається автоматично. Ітератори можуть бути константними. Константні ітератори використовуються тоді, коли змінювати значення відповідних елементів контейнера немає необхідності.

Перераховані ітератори мають свої різновиди, так звані адаптери ітераторів. Розглянемо наступні адаптери: зворотні ітератори, ітератори вставки та потокові ітератори.

Зворотний ітератор reverse_iterator, що є різновидом двонаправлених ітераторів та ітераторів довільного доступу, дозволяє продивлятися послідовність у зворотному напрямі.

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

vector <int> v;

for (vector <int> reverse_iterator i = v.rbegin();

i != v.rend; ++i)

cout << *i << " ";

Якщо контейнер оголошений як const (наприклад, в списку передаваних функції параметрів), то потрібно використовувати ітератор з префіксом const _const_reverse_iterator.

Ітератори вставки призначені для додавання нових елементів в початок, кінець або довільне місце контейнера. У стандартній бібліотеці визначено три шаблони класів ітераторів вставки, побудованих на основі вихідних ітераторів: back_insert_iterator, front_insert iterator і insert iterator. У цих ітераторах, а вони як і всі ітератори, є класами, визначено три функції: back_inserter() – вставляє елементи в кінець контейнера, front_inserter() – в початок, а inserter() – перед елементом, на який посилається її аргумент-ітератор. Приклад їх використання приведений нижче при описі алгоритмів.

Потокові ітератори введені для того, щоб стандартні алгоритми, які розглядаються при описі алгоритмів могли безпосередньо використовувати потоки введення/виведення. Потоки представляються у вигляді послідовностей. Визначено два шаблони класів потокових ітераторів: ітератор вхідного потоку istreamiterator і ітератор вихідного потоку ostreamiterator.