Відповідність алгоритмів контейнерам

Кабель – це не випадкова метафора для ітераторів, оскільки саме ітератори здійснюють зв’язок між алгоритмами і контейнерами. Зосередимо увагу на двох кінцях уявного кабеля: контейнерах і алгоритмах.

 

Монтаж кабеля в контейнерний кінець

Якщо обмежитися розглядом лише основних контейнерів STL, доведеться констатувати той факт, що можна обійтися тільки двома категоріями ітераторів. Як показано в таблиці 9.7, векторам і чергам з двостороннім доступом взагалі все одно, який ітератор використовується, а списки, множини, мультимножини, відображення і мультивідображення сприймають все, крім ітераторів довілнього доступу.

Таблиця 9.7

Типи ітераторів, що підтримуються контейнерами

Тип ітератора	Вектор	Список	Черга з двосто­роннім доступом	Множина	Мульти­множина	Відобра­ження	Мульти­відобра­ження
Довільного доступу	*		*
Двонапрям­лений	*	*	*	*	*	*	*
Прямий	*	*	*	*	*	*	*
Вхідний	*	*	*	*	*	*	*
Вихідний	*	*	*	*	*	*	*

Тепер розберемося. як же STL підключає правильний ітератор до контейнера? При визначенні ітератора потрібно вказати, для якого типу контейнера його слід використовувати. Наприклад, якщо ми визначили список значень типу int

list <int> ilist;//список int

тоді для того, щоб визначити ітератор для нього, потрібно написати:

list<int>::iteratot iter; //ітератор для цілочисельного списку

Після цього STL автоматично робить ітератор двонапрямленим, оскільки саме такий ітератор потрібний контейнеру типу «список». Ітератор для вектора чи черги з двостороннім доступом автоматично робиться ітератором довільного доступу.

Така автоматизація процесу досягається за рахунок того, що клас ітератора конкретного класу є спадкоємцем класу більш загального ітератора. Ітератори для векторів і черг з двостороннім доступом є спадкоємцями класу random_access_iterator, а ітератори для списків – спадкоємцями класу bidirectional_iterator.

Зараз ми розглянемо, як до контейнерів приєднуються «кінці» наших «кабелів»-ітераторів. Кабель насправді не вставляється в контейнер. Фігурально висловлюючись, він намертво на нього прикручений Вектори і черги з двостороннім доступом прикручені до ітераторів довільного доступу, а списки та інші асоціативні контейнери завжди прикручені до двонапрямлених ітераторів.

 

Монтаж «кабеля» в алгоритм

Кожному алгоритму, залежно від того, чим він займається, потрібний свій тип ітератора. Якщо потрібно звертатися до довільних елементів ітератора, потрібний ітератор довільного доступу. Якщо ж потрібно просто пересуватися від елемента до елемента, то підійде менш потужний прямий ітератор. В таблиці 10.8 показані приклади алгоритмів та потрібних їм ітераторів.

Таблиця 10.8

Типи ітераторів, потрібні певним алгоритмам

Алгоритм	Вхідний	Вихідний	Прямий	Двонапрям­лений	Довільного доступу
for_each	*
find	*
count	*
copy	*	*
replace			*
unique			*
reverse				*
sort					*
nth_element					*
merge	*
accumulate	*

Попри те, що кожному алгоритму потрібний певний рівень можливостей, потужніші ітератори теж працюватимуть нормально. Алгоритму replace() потрібний прямий ітератор, але він працюватиме і з двонапрямленим ітератором, і з ітератором довільного доступу.

Завдяки двом попереднім таблицям, можна встановити, з якими алгоритмами працює той чи інший ітератор. Наприклад, алгоритму sort() потрібний ітератор довільного доступу. Ітератор довільного доступу працює з векторами і чергами з двостороннім доступом. Отже, алгоритм sort() працюватиме лише з ними.

Будь-який алгоритм, якому не потрібний ітератор довільного доступу, працюватиме з довільним типом контейнера STL, оскільки всі контейнери використовують двонапрямлені ітератори, які тільки на один рівень менш потужні, ніж ітератори довільного доступу. Якщо б у STL існували однозв’язні списки, то з ними можна було б користуватися прямими ітераторами, але не можна б було використовувати ітератор reverse().

Як бачимо, відносно мале число алгоритмів реально потребує алгоритмів довільного доступу. Тому більшість алгоритмів працюватиме з більшістю контейнерів.