Рис. 7.2. Категории итераторов

Проблема увеличения и уменьшения итераторов в векторах

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

std::vector<1nt> coll:

Сортировка, начиная со второго элемента - НЕПЕРЕНОСИМАЯ версия 1f (coll.SizeO > 1) {

sort(++coll .beg1n(). coll.endO);

Обычно компиляция строки с вызовом sort() завершается неудачей, но если заменить вектор деком, компиляция пройдет нормально. Иногда программа компилируется даже для векторов - это зависит от реализации класса vector.

Дело в том, что векторные итераторы обычно реализуются в виде обычных указателей. Для всех базовых птов данных, в том числе и для указателей, модификация временных значений запрещена. С другой стороны, для структур и классов она разрегнена. Следовательно, если тттератор реализован в виде обычного указателя, программа не компилируется; если итератор реализован в виде класса, компиляция проходит успешно. Для деков, списков, множеств и отображений такой проблемы не существует, поскольку в них итераторы в нршщипе пе реализуются в виде обычных указателей, но для векторов все зависит от реализации. В большинстве реализаций задействованы обычные указатели. Но, например, в «безопасной» версии STL итераторы реализованы в виде классов. Чтобы приведенный выше фрагмент был переносимым, достаточно определить промежуточный объект:

std::vector<1nt> coll;

Сортировка, начиная со второго элемента - ПЕРЕНОСИМАЯ версия If (coll .SizeO > 1) {

std: :vector<lnt>:: iterator beg = coll.beginO: sort C++C0II .beg, coll.endO):

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

Вспомогательные функции итераторов

Стандартная библиотека С++ содержит три вспомогательные функции для работы с итераторами: advance(), distance() и iter swap(). Первые две функции предоставляют для любого итератора возможности, которыми обычно обладают только итераторы произвольного доступа: перемещение итератора сразу на несколько элементов вперед (или назад) и вычисление разности между итераторами. Третья вспомогательная функция меняет местами элементы, на которые ссылаются два итератора.

Перебор итераторов функцией advance

Функция advanceO перемещает итератор, передаваемый ей в качестве аргумента. При этом смещение может производиться в прямом (илн обратном) направлении сразу на несколько элементов:

#include <iterator>

void advance (InputIterator& pos. Dist n)

О Перемещает итератор ввода p05 на п элементов вперед (или назад).

О Для двунаправленных итераторов и итераторов произвольного доступа значение п может быть отррщательным (перемещение в обратном направлении).

О Dist - тип шаблона. Обычно является целым типом, поскольку для него вызываются такие операции, как <, ++, - и сравнение с 0.

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

Благодаря разным трактовкам итераторов (см. с. 288) функция всегда использует оптимальную реализацию в зависимости от категории итератора. Для итераторов произвольного доступа она просто вызывает pos+=n. Следовательно, для таких итераторов функция advance() имеет постоянную сложность. Для остальных итераторов используется и-кратный вызов pos (или -pes, если значение п отрицательно). Таким образом, для всех остальных категорий итераторов функция advanceO выполняется с лштейной сложностью.

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

iter/advancel.cpp #include <lostream> #lnclude <l1st> #lnclude <algorithfii> using namespace std;

int mainO {

I1st<int> coll;

Вставка элементов от 1 до 9 for Cmt i=l; i<-9: ++i) { coll.push backCi);

list<int>:; iterator pos = coll.beginO:

Вывод текущего элемента cout « *pos « endl:

Перемещение вперед на три элемента advance Cpos. 3);

Вывод текущего элемента cout « *pos « endl:

Перемещение назад на один элемент advance Cpos. -1);

Вывод текущего элемента cout « *pos « endl:

Вызовы advance() переводят итератор на три элемента вперед и на один элемент назад. Результат:

1 4 3

Существуют и другие применения функции advance(). Например, вы можете проигнорировать часть ввода от итераторов, читающих данные из входного потока, пример приведен на с. 286.