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

В реализации Dinkumware принят несколько иной подход. Она также позволяет задать тип объектов, хэш-функцию, функцию сравнения и распределитель, но хэш-функция и функция сравнения по умолчанию перемещены в отдельный класс hash_compare, который передается по умолчанию в параметре HashingInfoшаблона контейнера.

Например, объявление hash_set(также отформатированное для наглядности) в реализации Dinkumware выглядит следующим образом:

template

class hash_compare;

template

typename Hashinglnfo = hash_compare>,

typename Allocator = allocator>

class hash_set;

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

После небольшого форматирования объявление hash_compare(значение по умолчанию для HashingInfo) выглядит примерно так:

template >

class hash_compare {

public:

enum {

bucket_size = 4, // Максимальное отношение числа элементов к числу гнезд

min_buckets = 8 // Минимальное количество гнезд

}

size_t operator()(const T&) 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_mapи hash_multimapосуществляется аналогичным образом.

Учтите, что в обоих вариантах все принятие решений можно поручить реализации и ограничиться объявлением следующего вида:

hash_set intTable; // Создать хешированное множество int

Чтобы это объявление нормально компилировалось, хэш-таблица должна содержать данные целочисленных типов (например, int), поскольку стандартные хэш-функции обычно ограничиваются целочисленными типами (в реализации SGI стандартные хэш-функции обладают более широкими возможностями; о том, где найти дополнительную информацию, рассказано в совете 50).

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

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