Скотт Мейерс - Эффективное использование STL

Если у вас имеется доступ к контейнеру, от которого был взят const_iterator , существует безопасный, переносимый способ получения соответствующего типа iterator без нарушения системы типов. Ниже приведена основная часть этого решения (возможно, перед компиляцией потребуется внести небольшие изменения):

typedef deque IntDeque;//См. ранее

typedef IntDeque::iterator Iter;

typedef IntDeque::const_iterator ConstIter;

IntDeque d;

Constlter ci;

// Присвоить ci ссылку на d

Iter i(d.begin());// Инициализировать i значением d.begin()

advance(i,distance(i,ci)); // Переместить i в позицию ci

Решение выглядит настолько простым и прямолинейным, что это невольно вызывает подозрения. Чтобы получить iterator, указывающий на тот же элемент контейнера, что и const_iterator, мы создаем новый iterator в начале контейнера и перемещаем его вперед до тех пор, пока он не удалится на то же расстояние, что и const_iterator! Задачу упрощают шаблоны функций advanceи distance, объявленные в . Distanceвозвращает расстояние между двумя итераторами в одном контейнере, a advanceперемещает итератор на заданное расстояние. Когда итераторы i и ci относятся к одному контейнеру, выражение advance( i, distance(i, ci))переводит их в одну позицию контейнера.

Все хорошо, если бы этот вариант компилировался... но этого не происходит. Чтобы понять причины, рассмотрим объявление distance:

template

typename iterator_traits::difference_type

distance(InputIterator first, InputIterator last);

Не обращайте внимания на то, что тип возвращаемого значения состоит из 56 символов и содержит упоминания зависимых типов (таких как differenceype). Вместо этого проанализируем использование параметра-типа InputIterator:

template

typename iterator_traits::difference_type

distance(InputIterator first,InputIterator last);

При вызове distance компилятор должен определить тип, представленный InputIterator, для чего он анализирует аргументы, переданные при вызове. Еще раз посмотрим на вызов distance в приведенном выше коде:

advance(i,.distance(i,ci)); // Переместить i в позицию ci

При вызове передаются два параметра, i и ci. Параметр i относится к типу iter, который представляет собой определение типа для deque:: iterator. Для компилятора это означает, что InputIterator при вызове distance( соответствует типу deque: iterator. Однако ci относится к типу ConstIter, который представляет собой определение типа для deque::const_iterator. Из этого следует, что InputIterator соответствует типу deque::const_iterator. InputIterator никак не может соответствовать двум типам одновременно, поэтому вызов distance завершается неудачей и каким-нибудь запутанным сообщением об ошибке, из которого можно (или нельзя) понять, что компилятор не смог определить тип InputIterator.

Чтобы вызов нормально компилировался, необходимо ликвидировать неоднозначность. Для этого проще всего явно задать параметр-тип, используемый distance, и избавить компилятор от необходимости определять его самостоятельно:

advanced.distance(i,ci)): // Вычислить расстояние между

// i и ci (как двумя const_iterator)

// и переместить i на это расстояние

Итак, теперь вы знаете, как при помощи advance и distance получить iterator, соответствующий заданному const_iterator, но до настоящего момента совершенно не рассматривался вопрос, представляющий большой практический интерес: насколько эффективна данная методика? Ответ прост: она эффективна настолько, насколько это позволяют итераторы. Для итераторов произвольного доступа, поддерживаемых контейнерами vector , string, deque и т. д., эта операция выполняется с постоянным временем. Для двусторонних итераторов (к этой категории относятся итераторы других стандартных контейнеров, а также некоторых реализаций хэшированных контейнеров — см. совет 25) эта операция выполняется с линейным временем.

Поскольку получение iterator, эквивалентного const_iterator, может потребовать линейного времени, и поскольку это вообще невозможно сделать при недоступности контейнера, к которому относится const_iterator, проанализируйте архитектурные решения, вследствие которых возникла необходимость получения iterator по const_iterator. Результат такого анализа станет дополнительным доводом в пользу совета 26, рекомендующего отдавать предпочтение iterator перед const- и reverse-итераторами.

При вызове функции base для итератора reverse_iterator будет получен «соответствующий» iterator , однако из сказанного совершенно не ясно, что же при этом происходит. В качестве примера рассмотрим следующий фрагмент, который заносит в вектор числа 1-5, устанавливает reverse_iterator на элемент 3 и инициализирует iterator функцией base:

vector v;

v.reserve(5);

//См. совет 14

for (int i=1;i<=5; ++i){

v.push_back(i);

// Занести в вектор числа 1-5

vector::reverse_iterator ri=

find(v.rbegin(),v.rend(),3);

vector:: iterator i ( ri.base());

// Установить ri на элемент 3

// Присвоить i результат вызова base

// для итератора ri

После выполнения этого фрагмента ситуация выглядит примерно так:

На рисунке видно характерное смещение reverse_iterator и соответствующего базового итератора, воспроизводящего смещение begin() и end() по отношению к begin() и end(), но найти на нем ответы на некоторые вопросы не удается. В частности, рисунок не объясняет, как использовать i для выполнения операций, которые должны были выполняться с ri .

Как упоминалось в совете 26, некоторые функции контейнеров принимают в качестве параметров-итераторов только iterator. Поэтому если вы, допустим, захотите вставить новый элемент в позицию, определяемую итератором п, сделать это напрямую не удастся; функция insert контейнера vector не принимает reverse_ iterator. Аналогичная проблема возникает при удалении элемента, определяемого итератором г . Функции erase не соглашаются на reverse_iterator и принимают только iterator. Чтобы выполнить удаление или вставку, необходимо преобразовать reverse_iterator в iterator при помощи base, а затем воспользоваться iterator для выполнения нужной операции.

Допустим, потребовалось вставить в v новый элемент в позиции, определяемой итератором n. Для определенности будем считать, что вставляется число 99. Учитывая, что n на предыдущем рисунке используется для перебора справа налево, а новый элемент вставляется перед позицией итератора, определяющего позицию вставки, можно ожидать, что число 99 окажется перед числом 3 в обратном порядке перебора. Таким образом, после вставки вектор v будет выглядеть так: