Эффективное использование STL

Мейерс Скотт

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

При вызове передаются два параметра,

i

и

ci

. Параметр

i

относится к типу

iter

, который представляет собой определение типа для

deque<int>::iterator

. Для компилятора это означает, что

InputIterator

при вызове

distance

соответствует типу

deque<int>::iterator

. Однако

ci

относится к типу

ConstIter

, который представляет

собой определение типа для

deque<int>::const_iterator

. Из этого следует, что

InputIterator

соответствует типу

deque<int>::const_iterator

.

InputIterator

никак не может соответствовать двум типам одновременно, поэтому вызов

distance

завершается неудачей и каким-нибудь запутанным сообщением об ошибке, из которого можно (или нельзя) понять, что компилятор не смог определить тип

InputIterator

.

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

distance

, и избавить компилятор от необходимости определять его самостоятельно:

advanced.distance<ConstIter>(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

– итераторами.

Совет 28. Научитесь использовать функцию base

При вызове функции

base

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

reverse_iterator

будет получен «соответствующий»

iterator

, однако из сказанного совершенно не ясно, что же при этом происходит. В качестве примера рассмотрим следующий фрагмент, который заносит в вектор числа 1–5, устанавливает

reverse_iterator

на элемент 3 и инициализирует

iterator

функцией

base

:

vector<int> v;

v.reserve(5); //См. совет 14

for (int i=1; i<=5; ++i){ // Занести в вектор числа 1-5

 v.push_back(i);

}

vector<int>::reverse_iterator ri = // Установить ri на элемент 3

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

vector<int>::iterator i(ri.base); // Присвоить i результат вызова base

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

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

На рисунке видно характерное смещение

reverse_iterator

и соответствующего базового итератора, воспроизводящего смещение

begin

и

end

по отношению к

begin

и

end

, но найти на нем ответы на некоторые вопросы не удается. В частности, рисунок не объясняет, как использовать

i

для выполнения операций, которые должны были выполняться с

ri

.

Как упоминалось в совете 26, некоторые функции контейнеров принимают в качестве параметров-итераторов только

iterator

. Поэтому если вы, допустим, захотите вставить новый элемент в позицию, определяемую итератором

ri

, сделать это напрямую не удастся; функция

insert

контейнера

vector

не принимает

reverse_iterator

. Аналогичная проблема возникает при удалении элемента, определяемого итератором

ri

. Функции erase не соглашаются на

reverse_iterator

и принимают только

iterator

. Чтобы выполнить удаление или вставку, необходимо преобразовать

reverse_iterator

в

iterator

при помощи

base

, а затем воспользоваться iterator для выполнения нужной операции.

Допустим, потребовалось вставить в

v

новый элемент в позиции, определяемой итератором

ri

. Для определенности будем считать, что вставляется число 99. Учитывая, что 

ri

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

v

будет выглядеть так:

Конечно, мы не можем использовать 

ri

для обозначения позиции вставки, поскольку это не

iterator

. Вместо этого необходимо использовать

i

. Как упоминалось выше, когда

ri

указывает на элемент 3,

i

(то есть

r. base

) указывает на элемент 4. Именно на эту позицию должен указывать итератор

i

, чтобы вставленный элемент оказался в той позиции, в которой он бы находился, если бы для вставки можно было использовать итератор

ri

. Заключение: