Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации SGI. Главное различие между ними заключается в том, что в реализации SGI для типов HashFunction и CompareFunction предусмотрены значения по умолчанию. Объявление hash_set в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):
template
typename HashFunction = hash
typename CompareFunction = equal_to
typename Allocator = allocator
class hash_set;
В реализации SGI следует обратить внимание на использование equal_to в качестве функции сравнения по умолчанию. В этом она отличается от стандартных ассоциативных контейнеров, где по умолчанию используется функция сравнения less. Смысл этого изменения не сводится к простой замене функции. Хэшированные контейнеры SGI сравнивают два объекта, проверяя
В реализации 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
Чтобы это объявление нормально компилировалось, хэш-таблица должна содержать данные целочисленных типов (например, int), поскольку стандартные хэш-функции обычно ограничиваются целочисленными типами (в реализации SGI стандартные хэш-функции обладают более широкими возможностями; о том, где найти дополнительную информацию, рассказано в совете 50).
