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

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

Совет 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.

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

Оглавление книги