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

Как упоминалось в совете 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 v;

… // См. ранее. В вектор v заносятся

// числа 1-5

vector::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;