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

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

templateInputIterator>

typename iterator_traits< InputIterator>::difference_type

distance( InputIteratorfirst, InputIteratorlast);

При вызове 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< 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-итераторами.

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

vector v;

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

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

v.push_back(i);

}

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

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

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

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

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

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