Скотт Мейерс - Эффективное использование STL
distance(InputIterator first, InputIterator last);
При вызове distance компилятор должен определить тип, представленный InputIterator, для чего он анализирует аргументы, переданные при вызове. Еще раз посмотрим на вызов distance в приведенном выше коде:
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. Заключение:
• чтобы эмулировать вставку в позицию, заданную итератором 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.
Однако к коду стоит присмотреться повнимательнее, поскольку вас ждет сюрприз:
vector<int> v;
… // См. ранее. В вектор v заносятся
// числа 1-5
vector<int>::reverse_iterator ri = // Установить ri на элемент 3
find(v.rbegin(), v.rend(), 3);
v.erase(--ri.base()); // Попытка стирания в позиции.
// предшествующей ri-base():
// для вектора обычно
// не компилируется
Решение выглядит вполне нормально. Выражение --ri.base() правильно определяет элемент, предшествующий удаляемому. Более того, приведенный фрагмент будет нормально работать для всех стандартных контейнеров, за исключением vector и string. Наверное, он бы мог работать и для этих контейнеров, но во многих реализациях vector и string он не будет компилироваться. В таких реализациях типы iterator (и const_iterator) реализованы в виде встроенных указателей, поэтому результатом вызова i.base() является указатель. В соответствии с требованиями как C, так и C++ указатели, возвращаемые функциями, не могут модифицироваться, поэтому на таких платформах STL выражения типа --i.base() не компилируются. Чтобы удалить элемент в позиции, заданной итератором reverse_iterator, и при этом сохранить переносимость, необходимо избегать модификации возвращаемого значения base. Впрочем, это несложно. Если мы не можем уменьшить результат вызова base, значит, нужно увеличить reverse_iterator и после этого вызвать base!
… //См. ранее
v.erase((++ri).base()); // Удалить элемент, на который указывает ri;
// команда всегда компилируется
Такая методика работает во всех стандартных контейнерах и потому считается предпочтительным способом удаления элементов, определяемых итератором reverse_iterator.
