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

Принципы внутреннего устройства реализаций SGI и Dinkumware очень сильно различаются. В реализации SGI использована традиционная схема открытого хэширования с массивом указателей на односвязные списки элементов. В реализации Dinkumware используется двусвязный список. Различие достаточно принципиальное, поскольку оно влияет на категории итераторов, поддерживаемых этими реализациями. Хэшированные контейнеры SGI поддерживают прямые итераторы, что исключает возможность обратного перебора; в них отсутствуют такие функции, как rbegin или rend. Реализация Dinkumware поддерживает двусторонние итераторы, что позволяет осуществлять перебор как в прямом, так и в обратном направлении. С другой стороны, реализация SGI чуть экономнее расходует память.

Какая из этих реализаций лучше подходит для ваших целей? Понятия не имею. Только вы можете ответить на этот вопрос, однако в этом совете я даже не пытался изложить все необходимое для принятия обоснованного решения. Речь идет о другом — вы должны знать, что несмотря на отсутствие хэшированных контейнеров непосредственно в STL, при необходимости можно легко найти STL-совместимые хэшированные контейнеры (с разными интерфейсами, возможностями и особенностями работы). Более того, в свободно распространяемых реализациях SGI и STLport вам за них даже не придется платить.

Итераторы

На первый взгляд итераторы представляются предметом весьма простым. Но стоит присмотреться повнимательнее, и вы заметите, что стандартные контейнеры STL поддерживают четыре разных типа итераторов: iterator, const_iterator, reverse_iterator и const_reverse_iterator. Проходит совсем немного времени, и выясняется, что в некоторых формах insert и erase только один из этих четырех типов принимается контейнером. И здесь начинаются вопросы. Зачем нужны четыре типа итераторов? Существует ли между ними какая-либо связь? Можно ли преобразовать итератор от одного типа к другому? Можно ли смешивать разные типы итераторов при вызове алгоритмов и вспомогательных функций STL? Как эти типы связаны с контейнерами и их функциями?

В настоящей главе вы найдете ответы на эти вопросы, а также поближе познакомитесь с разновидностью итераторов, которой обычно не уделяют должного внимания: istreambuf_iterator. Если вам нравится STL, но не устраивает быстродействие istream_iterator при чтении символьных потоков, возможно, istreambuf_iterator поможет справиться с затруднениями.

Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator

Как известно, каждый стандартный контейнер поддерживает четыре типа итераторов. Для контейнера container тип iterator работает как T* тогда как const_iterator работает как const T* (также встречается запись T const*). При увеличении iterator или const_iterator происходит переход к следующему элементу контейнера в прямом порядке перебора (от начала к концу контейнера). Итераторы reverse_iterator и const_reverse_iterator также работают как T* и const T* соответственно, но при увеличении эти итераторы переходят к следующему элементу в обратном порядке перебора (от конца к началу).

Рассмотрим несколько сигнатур insert и erase в контейнере vector:

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.