4.4. Двунаправленные итераторы

В последнем разделе мы видели, что однонаправленные итераторы позволяют нам читать значения из структуры данных и записывать их в нее при проходе по структуре данных в одном направлении. Двунаправленный итератор аналогичен однонаправленному итератору, за исключением того, что он допускает обход в обоих направлениях. То есть, двунаправленные итераторы должны поддерживать все операции однонаправленных итераторов, а кроме них — операцию --, делая возможным обход последовательности в обратном направлении.

Требуется наличие и префиксной, и постфиксной версий operator--; префиксная версия выполняет декремент итератора и возвращает новое его значение, а постфиксная — выполняет декремент итератора и возвращает его старое значение. И префиксный, и постфиксный operator- - должны выполняться за константное время.

Возможность обхода структуры данных в обратном порядке важна потому, что в противном случае некоторые алгоритмы не в состоянии эффективно работать. Например, алгоритм STL reverse может использоваться для обращения порядка элементов в последовательности при наличии двунаправленных итераторов. Например, встроенные типы указателей, использующиеся с массивами, удовлетворяют всем требованиям к двунаправленным итераторам, так что мы можем написать

int a [100];

// ... Код для сохранения значений в а[0], . . . , а[99]

// Обращение порядка значений в массиве:

reverse(&а[0] , &а [100]);

Контейнер STL list также предоставляет двунаправленные итераторы, так что его тоже можно использовать с алгоритмом reverse:

list<int> list1;

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

// Обращение порядка значений в списке:

reverse(list1.begin(), list1.end());

Как можно ожидать, требование поддержки двунаправленных итераторов к классу list приводит к тому, что представление списка должно быть двусвязным. В случае односвязного списка эффективно реализовать operator-- (с константным временем работы) невозможно.

Таким образом, требования к двунаправленным итераторам позволяют гарантировать эффективность работы таких алгоритмов, как reverse, которым требуется обход последовательности в любом направлении.

4.5. Итераторы с произвольным доступом

В предыдущих разделах мы рассмотрели четыре категории итераторов, которые позволяют нам выразить различные ограничения, которые разные алгоритмы накладывают на структуры данных, чтобы эффективно с ними работать. Мы видели примеры алгоритмов, требующие, чтобы структуры данных, с которыми они работают, могли как минимум быть:

• прочитаны и обойдены в одном направлении (иначе говоря, алгоритм принимает входные итераторы);

• записаны и обойдены в одном направлении (иначе говоря, алгоритм принимает выходные итераторы);

• прочитаны, записаны и обойдены в одном направлении с дополнительной

возможностью сохранения итератора и повторного сканирования с сохраненной позиции (иначе говоря, алгоритм принимает однонаправленные итераторы);

• прочитаны, записаны и пройдены в любом направлении (иначе говоря, алгоритм принимает двунаправленные итераторы).

Оказывается, этих четырех категорий структур данных недостаточно для всех алгоритмов. Имеются некоторые алгоритмы, которые предъявляют к итераторам еще более высокие требования. Для эффективной работы эти алгоритмы требуют, чтобы любой элемент последовательности был достижим из любого другого за константное время.

Рассмотрим, например, обобщенный алгоритм STL binary_search. Будучи вызван как

binary_search(first, last, value)

где first и last ограничивают последовательность, хранящуюся в порядке возрастания, алгоритм возвращает true, если в последовательности имеется позиция, в которой хранится значение value, и false в противном случае. Это описание похоже на описание алгоритма find, но binary_search использует факт упорядоченности последовательности для сокращения времени работы с O(N) до O(logN), где N— длина последовательности. Этого можно достичь, сравнивая значение в средине последовательности с value и продолжая поиск в левой половине, если значение в средине больше value, или в правой половине, если оно меньше. То есть, при каждом сравнении пространство поиска сокращается вдвое, поэтому требуется выполнить не более log₂N сравнений. Но чтобы общее время вычислений было O(logN), требуется, чтобы элемент в средине последовательности был достижим за константное время.

Ясно, что списки таким свойством не обладают. Имея указатели на начало и конец списка, единственный способ добраться до элемента посредине — это обойти элементы один за другим. Это займет время, пропорциональное длине списка.

С другой стороны, векторы и массивы позволяют обратиться к любому элементу контейнера за константное время. Таким образом, алгоритм binary_search эффективно работает с векторами и массивами:

vector<int> vector1;

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

// Сканирование vector1 в поисках значения 5; если оно

// найдено, возвращает true; в противном случае — false:

bool found = binary_search(vector1.begin(), vector1.end(), 5);

Из этого примера видна необходимость еще одной категории итераторов — итераторов с произвольным доступом.

Итераторы с произвольным доступом должны поддерживать все операции двунаправленных итераторов, плюс следующие (здесь г и s — итераторы с произвольным доступом, a n — целочисленное выражение):

• прибавление и вычитание целых чисел, выражаемые r + n, n + r и r-n;

• доступ к n-му элементу при помощи выражения г [n], которое означает

* (г + п);

• двунаправленные "большие переходы", выражаемые как г += n и r -= n;

• вычитание итераторов, выражаемое как г - s и дающее целочисленное значение;

• сравнения, выражаемые как г < s,r > s,r <= s и г >= s и дающие значения

типа bool.

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