В реализации Dinkumware принят несколько иной подход. Она также позволяет задать тип объектов, хэш-функцию, функцию сравнения и распределитель, но хэш-функция и функция сравнения по умолчанию перемещены в отдельный класс hash_compare, который передается по умолчанию в параметре HashingInfo шаблона контейнера.
Например, объявление hash_set (также отформатированное для наглядности) в реализации Dinkumware выглядит следующим образом:
template<typename Т,typename CompareFunction>
class hash_compare;
template<typename T,
typename Hashinglnfo = hash_compare<T,less<T>>,
typename Allocator = allocator<T>>
class hash_set;
В этом интерфейсе внимание стоит обратить на использование параметра HashingInfo, содержащего функции хэширования и сравнения, а также перечисляемые типы, управляющие минимальным количеством гнезд в таблице и максимальным допустимым отношением числа элементов контейнера к числу гнезд. В случае превышения пороговой величины количество гнезд в таблице увеличивается, а некоторые элементы в таблице хэшируются заново (в реализации SGI предусмотрены функции, обеспечивающие аналогичные возможности управления количеством гнезд в таблице).
После небольшого форматирования объявление hash_compare (значение по умолчанию для HashingInfo) выглядит примерно так:
template<typename Т,typename CompareFunction=less<T>>
class hash_compare{
public:
enum{
bucket_size = 4. // Максимальное отношение числа элементов к числу гнезд
min_buckets = 8 // Минимальное количество гнезд
}
size_t operator()(const Т&) const; // Хэш-функция
bool operator() (const T&,
const T&) const;
// Некоторые подробности опущены,
// включая использование CompareFunction
};
Перегрузка operator() (в данном случае для реализации функций хэширования и сравнения) используется гораздо чаще, чем можно представить. Другое применение этой концепции продемонстрировано в совете 23.
Реализация Dinkumware позволяет программисту написать собственный касс-аналог hash_compare (возможно, объявленный производным от hash_compare). Если этот класс будет определять bucket_size, min_buckets, две функции operator() (с одним и с двумя аргументами) и еще несколько мелочей, не упомянутых выше, он может использоваться для управления конфигурацией и поведением контейнеров Dinkumware hash_set и hash_multiset. Управление конфигурацией hash_mnap и hash_ multimap осуществляется аналогичным образом.
Учтите, что в обоих вариантах все принятие решений можно поручить реализации и ограничиться объявлением следующего вида:
hash_set<int> intTable; // Создать хешированное множество int
Чтобы это объявление нормально компилировалось, хэш-таблица должна содержать данные целочисленных типов (например, int), поскольку стандартные хэш-функции обычно ограничиваются целочисленными типами (в реализации SGI стандартные хэш-функции обладают более широкими возможностями; о том, где найти дополнительную информацию, рассказано в совете 50).
Принципы внутреннего устройства реализаций 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? Как эти типы связаны с контейнерами и их функциями?
В настоящей главе вы найдете ответы на эти вопросы, а также поближе познакомитесь с разновидностью итераторов, которой обычно не уделяют должного внимания: isreambuf_iterator. Если вам нравится STL, но не устраивает быстродействие istream_iterator при чтении символьных потоков, возможно, isreambuf_ iterator поможет справиться с затруднениями.
Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator
Как известно, каждый стандартный контейнер поддерживает четыре типа итераторов. Для контейнера container<T> тип iterator работает как Т* тогда как const_iterator работает как const Т* (также встречается запись Т const*). При увеличении iterator или const_iterator происходит переход к следующему элементу контейнера в прямом порядке перебора (от начала к концу контейнера). Итераторы reverse_iterator и const_reverse_iterator также работают как Т* и const Т* соответственно, но при увеличении эти итераторы переходят к следующему элементу в обратном порядке перебора (от конца к началу).
Рассмотрим несколько сигнатур 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, a 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-итераторы становятся
