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

Мейерс Скотт

Рассмотрим несколько сигнатур

insert

и

erase

в контейнере

vector<T>

:

iterator insert(iterator position, const T& x);

iterator erase(iterator position);

iterator erase(iterator rangeBegin, iterator rangeEnd);

Аналогичные функции имеются у всех стандартных контейнеров, но тип возвращаемого значения определяется типом контейнера. Обратите внимание: перечисленные функции требуют передачу параметров типа

iterator

. Не

const_iterator

, не

reverse_iterator

и не

const_reverse_iterator

—

только

iterator

. Хотя контейнеры поддерживают четыре типа итераторов, один из этих типов обладает привилегиями, отсутствующими у других типов. Тип

iterator

занимает особое место.

На следующей диаграмме показаны преобразования, возможные между итераторами разных типов.

Из рисунка следует, что

iterator

преобразуется в

const_iterator

и

reverse_iterator

, а

reverse_iterator

— в

const_reverse_iterator

. Кроме того,

reverse_iterator

преобразуется в

iterator

при помощи функции

base

типа

reverse_iterator

, а

const_reverse_iterator

аналогичным образом преобразуется в

const_iterator

. Однако из рисунка не видно, что итераторы, полученные при вызове

base

, могут оказаться не теми, которые вам нужны. За подробностями обращайтесь к совету 28.

Обратите внимание: не существует пути от

const_iterator

к

iterator

или от

const_reverse_iterator

к

reverse_iterator

. Из этого важного обстоятельства следует, что

const_iterator

и

const_reverse_iterator

могут вызвать затруднения с некоторыми функциями контейнеров. Таким функциям необходим тип

iterator

, а из-за отсутствия обратного перехода от

const

– итераторов к

iterator

первые становятся в целом бесполезными, если вы хотите использовать их для определения позиции вставки или удаления элементов.

Однако не стоит поспешно заключать, что

const

– итераторы вообще бесполезны. Это не так. Они прекрасно работают с алгоритмами, поскольку для алгоритмов обычно подходят все типы итераторов, относящиеся к нужной категории. Кроме того,

const

– итераторы подходят для многих функций контейнеров. Проблемы возникают лишь с некоторыми формами

insert

и

erase

.

Обратите внимание на формулировку:

const

– итераторы становятся в целом бесполезными, если вы хотите использовать их для определения позиции вставки или удаления элементов. Называть их полностью бесполезными было бы неправильно. Const-итераторы могут принести пользу, если вы найдете способ получения

iterator

для

const_iterator

или

const_reverse_iterator

. Такое возможно часто, но далеко не всегда, причем даже в благоприятном случае решение не очевидно, да и эффективным его не назовешь. В двух словах этот вопрос не изложить, если вас заинтересуют подробности — обращайтесь к совету 27. А пока имеющаяся информация позволяет понять, почему типу

iterator

отдается предпочтение перед его

const

– и

reverse

– аналогами.

• Некоторым версиям

insert

и

erase

при вызове должен передаваться тип

iterator

.

Const

– и

reverse

– итераторы им не подходят.

• Автоматическое преобразование

const

– итератора

в

iterator

невозможно, а методика получения

iterator

на основании

const_iterator

(совет 27) применима не всегда, да и эффективность ее не гарантируется.

• Преобразование

reverse_iterator

в

iterator

может требовать дополнительной регулировки итератора. В совете 28 рассказано, когда и почему возникает такая необходимость.

Из сказанного следует однозначный вывод: если вы хотите работать с контейнерами просто и эффективно и по возможности застраховаться от нетривиальных ошибок, выбирайте

iterator

вместо его

const

– и

reverse

– аналогов.

На практике выбирать обычно приходится между

iterator

и

const_iterator

. Выбор между

iterator

и

reverse_iterator

часто происходит помимо вашей воли — все зависит от того, в каком порядке должны перебираться элементы контейнера (в прямом или в обратном). А если после выбора

reverse_iterator

потребуется вызвать функцию контейнера, требующую

iterator

, вызовите функцию

base

(возможно, с предварительной регулировкой смещения — см. совет 28).

При выборе между

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…