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

Совет 27. Используйте distance и advance для преобразования const_iterator в iterator

Совет 27. Используйте distance и advance для преобразования const_iterator в iterator

Как было сказано в совете 26, некоторые функции контейнеров, вызываемые с параметрами-итераторами, ограничиваются типом iterator;const_iterator им не подходит. Что же делать, если имеется const_iterator и вы хотите вставить новый элемент в позицию контейнера, обозначенную этим итератором? Const_iterator необходимо каким-то образом преобразовать в iterator, и вы должны принять в этом активное участие, поскольку, как было показано в совете 26, автоматического преобразования const_iterator в iterator не существует.

Я знаю, о чем вы думаете. «Если ничего не помогает, берем кувалду», не так ли? В мире C++ это может означать лишь одно: преобразование типа. Стыдитесь. И где вы набрались таких мыслей?

Давайте разберемся с вредным заблуждением относительно преобразования типа. Посмотрим, что происходит при преобразовании const_iterator в iterator:

typedef deque<int> IntDeque; // Вспомогательные определения типов
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
ConstIter ci; // ci - const iterator
Iter i(ci); // Ошибка! He существует автоматического
            // преобразования const_iterator
            // в iterator
Iter i(const_cast<Iter>(ci)); // Ошибка! Преобразование const_iterator
                              // в iterator невозможно!

В приведенном примере используется контейнер deque, но аналогичный результат будет получен и для list, set, muliset, mulimap и хэшированных контейнеров, упоминавшихся в совете 25. Возможно, строка с преобразованием будет откомпилирована для vector и string, но это особые случаи, которые будут рассмотрены ниже.

Почему же для этих типов контейнеров преобразование не компилируется? Потому что iterator и const_iterator относятся к разным классам, и сходства между ними не больше, чем между string и complex<double>. Попытка преобразования одного типа в другой абсолютно бессмысленна, поэтому вызов const_cast будет отвергнут. Попытки использования static_cast, reintepreter_cast и преобразования в стиле C приведут к тому же результату.

Впрочем, некомпилируемое преобразование все же может откомпилироваться, если итераторы относятся к контейнеру vector или string. Это объясняется тем, что в реализациях данных контейнеров в качестве итераторов обычно используются указатели. В этих реализациях vector<T>::iterator является определением типа для T*, vector<T>::const_iterator — для const T*, string::iterator — для char*, а string::const_iterator — для const char*. В реализациях данных контейнеров преобразование const_iterator в iterator вызовом const_cast компилируется и даже правильно работает, поскольку оно преобразует const T* в T*. Впрочем, даже в этих реализациях reverse_iterator и const_reverse_iterator являются полноценными классами, поэтому const_cast не позволяет преобразовать const_reverse_iterator в reverse_iterator. Кроме того, как объясняется в совете 50, даже реализации, в которых итераторы контейнеров vector и string представлены указателями, могут использовать это представление лишь при компиляции окончательной (release) версии. Все перечисленные факторы приводят к мысли, что преобразование const-итераторов в итераторы не рекомендуется и для контейнеров vector и string, поскольку переносимость такого решения будет сомнительной.

Если у вас имеется доступ к контейнеру, от которого был взят const_iterator, существует безопасный, переносимый способ получения соответствующего типа iterator без нарушения системы типов. Ниже приведена основная часть этого решения (возможно, перед компиляцией потребуется внести небольшие изменения):

typedef deque<int> IntDeque; //См. ранее
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
IntDeque d;
ConstIter ci;
…                  // Присвоить ci ссылку на d
Iter i(d.begin()); // Инициализировать i значением d.begin()
advance(i, distance(i, ci)); // Переместить i в позицию ci

Решение выглядит настолько простым и прямолинейным, что это невольно вызывает подозрения. Чтобы получить iterator, указывающий на тот же элемент контейнера, что и const_iterator, мы создаем новый iterator в начале контейнера и перемещаем его вперед до тех пор, пока он не удалится на то же расстояние, что и const_iterator! Задачу упрощают шаблоны функций advance и distance, объявленные в <iterator>. Distance возвращает расстояние между двумя итераторами в одном контейнере, a advance перемещает итератор на заданное расстояние. Когда итераторы i и ci относятся к одному контейнеру, выражение advance(i, distance(i, ci)) переводит их в одну позицию контейнера.

Все хорошо, если бы этот вариант компилировался… но этого не происходит. Чтобы понять причины, рассмотрим объявление distance:

template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);

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

template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
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-итераторами.

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