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

Чтобы вызов нормально компилировался, необходимо ликвидировать неоднозначность. Для этого проще всего явно задать параметр-тип, используемый 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. Заключение:

• чтобы эмулировать вставку в позицию, заданную итератором ri типа reverse_iterator, выполните вставку в позицию r.base. По отношению к операции вставки ri и r.base эквивалентны, но r.base в действительности представляет собой iterator, соответствующий ri.

Рассмотрим операцию удаления элемента. Вернемся к взаимосвязи между ri и исходным вектором (по состоянию на момент, предшествующий вставке значения 99):

Для удаления элемента, на который указывает итератор ri, нельзя просто использовать i, поскольку этот итератор ссылается на другой элемент. Вместо этого нужно удалить элемент, предшествующий i. Заключение:

• чтобы эмулировать удаление в позиции, заданной итератором ri типа reverse_iterator, выполните удаление в позиции, предшествующей ri.base. По отношению к операции удаления ri и ri.base не эквивалентны, a ri.base не является объектом iterator, соответствующим ri.