12.4.1. Итераторы вставки

Вот еще один фрагмент программы, в котором есть тонкая, но серьезная ошибка. Видите ли вы, в чем она заключается?

int ia[] = { 0, 1, 1, 2, 3, 5, 5, 8 };

vector< int > ivec( ia, ia+8 ), vres;

// ...

// поведение программы во время выполнения не определено

unique_copy( ivec.begin(), ivec.end(), vres.begin() );

Проблема вызвана тем, что алгоритм unique_copy() использует присваивание для копирования значения каждого элемента из вектора ivec, но эта операция завершится неудачно, поскольку в vres не выделено место для хранения девяти целых чисел.

Можно было бы написать две версии алгоритма unique_copy(): одна присваивает элементы, а вторая вставляет их. Эта последняя версия должна, в таком случае, поддерживать вставку в начало, в конец или в произвольное место контейнера.

Альтернативный подход, принятый в стандартной библиотеке, заключается в определении трех адаптеров, которые возвращают специальные итераторы вставки:

• back_inserter() вызывает определенную для контейнера операцию вставки push_back() вместо оператора присваивания. Аргументом back_inserter() является сам контейнер. Например, вызов unique_copy() можно исправить, написав:

// правильно: теперь unique_copy() вставляет элементы с помощью

// vres.push_back()...

unique_copy( ivec.begin(), ivec.end(),

back_inserter( vres ) );

• front_inserter() вызывает определенную для контейнера операцию вставки push_front() вместо оператора присваивания. Аргументом front_inserter() тоже является сам контейнер. Заметьте, однако, что класс vector не поддерживает push_front(), так что использовать такой адаптер для вектора нельзя:

// увы, ошибка:

// класс vector не поддерживает операцию push_front()

// следует использовать контейнеры deque или list

unique_copy( ivec.begin(), ivec.end(),

front_inserter( vres ) );

• inserter() вызывает определенную для контейнера операцию вставки insert() вместо оператора присваивания. inserter() принимает два аргумента: сам контейнер и итератор, указывающий позицию, с которой должна начаться вставка:

unique_copy( ivec.begin(), ivec.end(),

inserter( vres ), vres.begin() );

• Итератор, указывающий на позицию начала вставки, сдвигается вперед после каждой вставки, так что элементы располагаются в нужном порядке, как если бы мы написали:

vector< int >::iterator iter = vres.begin(),

iter2 = ivec.begin();

for ( ; iter2 != ivec.end() ++ iter, ++iter2 )

vres.insert( iter, *iter2 );

12.4.2. Обратные итераторы

Операции begin() и end() возвращают соответственно итераторы, указывающие на первый элемент и на элемент, расположенный за последним. Можно также вернуть обратный итератор, обходящий контейнер от последнего элемента к первому. Во всех контейнерах для поддержки такой возможности используются операции rbegin() и rend(). Есть константные и неконстантные версии обратных итераторов:

vector< int > vec0;

const vector< int > vec1;

vector< int >::reverse_iterator r_iter0 = vec0.rbegin();

vector< int >::const_reverse_iterator r_iter1 = vec1.rbegin();

Обратный итератор применяется так же, как прямой. Разница состоит в реализации операторов перехода к следующему и предыдущему элементам. Для прямого итератора оператор ++ дает доступ к следующему элементу контейнера, тогда как для обратного – к предыдущему. Например, для обхода вектора в обратном направлении следует написать:

// обратный итератор обходит вектор от конца к началу

vector< type >::reverse_iterator r_iter;

for ( r_iter = vec0.rbegin(); // r_iter указывает на последний элемент

r_iter != vec0.rend(); // пока не достигли элемента перед первым

r_iter++ ) // переходим к предыдущему элементу

{ /* ... */ }

Инвертирование семантики операторов инкремента и декремента может внести путаницу, но зато позволяет программисту передавать алгоритму пару обратных итераторов вместо прямых. Так, для сортировки вектора в порядке убывания мы передаем алгоритму sort() пару обратных итераторов:

// сортирует вектор в порядке возрастания

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

// сортирует вектор в порядке убывания

sort( vec0.rbegin(), vec0.rend() );