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

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

typedef deque<int> IntDeque;                // Определения типов

typedef IntDeque:iterator Iter;             // упрощают работу

typedef IntDeque::const_iterator ConstIter; // с контейнерами STL

                                            // и типами итераторов

iter i;

ConstIter ci;

… // i и ci указывают на элементы

  // одного контейнера

if (i==ci)… // Сравнить iterator

            //c const_iterator

В данном примере происходит обычное сравнение двух итераторов контейнера, подобные сравнения совершаются в STL сплошь и рядом. Просто один объект относится к типу iterator, а другой — к типу const_iterator. Проблем быть не должно — iterator автоматически преобразуется в const_iterator, и в сравнении участвуют два const_iterator.

Именно это и происходит в хорошо спроектированных реализациях STL, но в некоторых случаях приведенный фрагмент не компилируется. Причина заключается в том, что такие реализации объявляют operator== функцией класса const_iterator вместо внешней функции. Впрочем, вас, вероятно, больше интересуют не корни проблемы, а ее решение, которое заключается в простом изменении порядка итераторов:

if (c==i)… // Обходное решение для тех случаев,

           // когда приведенное выше сравнение не работает

Подобные проблемы возникают не только при сравнении, но и вообще при смешанном использовании iterator и const_iterator (или reverse_iterator и const_reverse_iterator) в одном выражении, например, при попытке вычесть один итератор произвольного доступа из другого:

if (i-ci>=3)… // Если i находится минимум в трех позициях после ci…

ваш (правильный) код будет несправедливо отвергнут компилятором, если итераторы относятся к разным типам. Обходное решение остается прежним (перестановка i и ci), но в этом случае приходится учитывать, что i-ci не заменяется на ci-i:

if (c+3<=i)… // Обходное решение на случай, если

             // предыдущая команда не компилируется

Простейшая страховка от подобных проблем заключается в том, чтобы свести к минимуму использование разнотипных итераторов, а это в свою очередь подсказывает, что вместо const_iterator следует использовать iterator. На первый взгляд отказ от const_iterator только для предотвращения потенциальных недостатков реализации (к тому же имеющих обходное решение) выглядит неоправданным, но с учетом особого статуса iterator в некоторых функциях контейнеров мы неизбежно приходим к выводу, что итераторы const_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 в приведенном выше коде: