4.11. Почему некоторые алгоритмы требуют более мощные итераторы

Некоторые алгоритмы в библиотеке требуют от итераторов большего, чем минимальные возможности входных, выходных или однонаправленных итераторов. Такие алгоритмы требуют от передаваемых им итераторов принадлежности к категории двунаправленных итераторов или итераторов с произвольным доступом; в противном случае они просто не компилируются. Например, алгоритм sort имеет следующий интерфейс:

template <typename RandomAccessIterator>

void sort(RandomAccessIterator first,

RandomAccessIterator last);

означающий, что sort требует передачи двух итераторов, принадлежащих категории итераторов с произвольным доступом. Именно их он и получает, когда мы пишем

vector<int> vector1;

// ... Код для вставки значений в vector1

sort(vector1.begin(), vector1.end());

Как и в случае "не совсем обобщенной" реализации find1, мы получим проблемы, пытаясь применить алгоритм sort к контейнеру list:

list<int> list1;

// ... Код для вставки значений в list1

sort(list1.begin(), list1.end()); // Неверно

Поскольку listl .begin() и listl.end() всего лишь двунаправленные итераторы,

они не предоставляют всю необходимую функциональность, используемую реализацией sort, такую как оператор +=, так что такой код компилироваться не будет.

Почему бы не расширить итераторы list и подобные до другой категории, добавив им операции +=, < и прочие, которыми обладают итераторы с произвольным доступом? Похоже, это бы упростило задачу написания обобщенных алгоритмов, так как нам бы не пришлось столько беспокоиться о том, какие операции могут быть применены к итераторам. И вновь причина в эффективности. В случае списков нет никакой возможности вычислить выражение

наподобие listl.begin () + n за константное время; есть только очевидный способ

прохода по узлам списка один за другим, требующий время, пропорциональное п (т.е. имеющий линейное время работы). Поэтому даже если мы запрограммируем метод и назовем его +, то все равно не достигнем истинного произвольного доступа. Такие алгоритмы, как sort, будут работать существенно медленнее, чем алгоритмы, использующие возможности списков (такой, как алгоритм, использующийся классом list в функции-члене sort).

4.12. Выбор правильного алгоритма

Одно из последних замечаний о совместимости алгоритм/контейнер: хотя схема классификации итераторов STL способствует созданию эффективных комбинаций и препятствует неэффективным, она не в состоянии полностью исключить комбинации, неэффективные в некоторых случаях. То есть можно применить тот или иной алгоритм к контейнеру, но делать это — неразумно.

Пожалуй, наиболее простым примером является алгоритм find в комбинации с контейнерами с произвольным доступом, такими как массивы, векторы и деки. Как мы уже видели, find просто проходит по объектам последовательности один за другим, так что это алгоритм с линейным временем работы (т.е. время, необходимое алгоритму find для поиска значения в контейнере размера N пропорционально N). Если объекты последовательности не упорядочены каким-либо образом, такой поиск может быть лучшим. Однако если объекты в контейнере с произвольным доступом находятся в отсортированном виде, то другой алгоритм STL, binary_search, выполнит ту же работу гораздо эффективнее (за логарифмическое время, т.е. время работы алгоритма пропорционально логарифму размера контейнера).

Немного более "хитрый" случай представляет собой поиск в ассоциативном контейнере. Здесь также может быть применен обобщенный алгоритм find, поскольку ассоциативные контейнеры предоставляют двунаправленные итераторы, но внутренняя организация ассоциативных контейнеров STL обеспечивает возможность поиска за логарифмическое время. Поэтому все они предоставляют функцию-член (с тем же именем find, но принимающую один аргумент — искомое значение), которая выполняет такой эффективный поиск. Так что для больших ассоциативных контейнеров неэффективно использовать обобщенный алгоритм find для всего диапазона позиций контейнера:

set<int> set1;

// ... Код для вставки значений в set1

set<int>::iterator where;

where = find(set1.begin(), set1.end(), 7);

Этот способ работает, но время его работы — линейное. Гораздо эффективнее написать следующее выражение, выполняющееся за логарифмическое время:

where = set1.find(7);