Ітератори

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

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

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

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

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

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

Ітераторні класи і функції описані в заголовному файлі <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.

11.2 Функціональні об'єкти

Функціональним об'єктом називається клас, в якому визначена операція виклику функції (див. розділ 5.6). Ці об'єкти використовуються як параметри стандартних алгоритмів для завдання призначених для користувача критеріїв порівняння об'єктів або способів їх обробки. У тих алгоритмах, де в якості параметру можна використовувати функціональний об'єкт, можна використовувати і вказівку на функцію. При цьому застосування функціонального об'єкту може виявитися ефективнішим, оскільки операцію () можна визначити як вбудовану.

Стандартна бібліотека надає безліч функціональних об'єктів, необхідних для її ефективного використання. Вони описані в заголовному файлі <functional>.

У стандартній бібліотеці визначені шаблони функціональних об'єктів для операцій порівняння і логічних операцій, визначених в мові C++. Вони повертають значення типу bool, тобто є предикатами.

Таблиця 11.2. Предикати стандартної бібліотеки

Нижче приведений шаблон об'єкту equal_to (решта об'єктів описана аналогічним чином):

template <class Т> struct equal_to:

binary_function<T, Т, bool>

{

bool operator()(const T& x, const T& y) const

{

return x == y;

}

};

Програміст може описати власні предикати для визначення критеріїв порівняння об'єктів. Це необхідно, коли контейнер складається з елементів призначеного для користувача типу.

За допомогою бінарних предикатів можна порівнювати два різні об'єкти. Часто потрібно порівняти об'єкт не з іншим об'єктом, а з константою. Щоб використовувати для цього той же самий предикат, потрібно зв'язати один з двох його аргументів з константою. Для цього використовуються зв’язувачі bind2ndі bindlst, що дозволяють пов'язати з конкретним значенням відповідно другий і перший аргумент бінарної функції. Зв’язувачі реалізовані в стандартній бібліотеці як шаблони функцій, що приймають першим параметром функціональний об'єкт f з двома аргументами, а другим – прив'язуване значення value. Результатом виклику функції є функціональний об'єкт, створений з вхідного об'єкту f шляхом "підстановки" value в його перший або другий аргумент.

Припустимо, потрібно обчислити кількість елементів цілочисельного масиву, які менше 40:

#include <iostream>

#include <functional>

#include <algorithm>

using namespace std;