Программирование >>  Включение нужных заголовков 

1 ... 29 30 31 [ 32 ] 33 34 35 ... 71


хэшированных ассоциативных контейнеров с вполне стандартными именами: hash set, hash multiset, hash mapH hash multiniap.

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

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

Хэшированные контейнеры относятся к категории ассоциативных, поэтому им, как и всем остальным ассоциативным контейнерам, при объявлении следует задать тип объектов, хранящихся в контейнере, функцию сравнения для этих объектов и распределитель памяти. Кроме того, для работы хэшированному контейнеру необходима хэш-функция. Естественно предположить, что объявление хэширо-ванного контейнера должно выглядеть примерно так:

tempiate<typename Т,

typename HashFunction,

typename CompareFunction,

typename Allocator = allocator<T> > class Ьа5Ь контвйнер:

Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации SQL Главное различие между ними заключается в том, что в реализации SGI для типов HashFunction и CompareFunction предусмотрены значения по умолчанию. Объявление hash set в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):

templare<typename Т,

typename HashFunction = hash<T>,

typename CompareFunction = equal to<T>,

typename Allocator = allocator<T> > class hash set:

В реализации SGI следует обратить внимание на использование equalto в качестве функции сравнения по умолчанию. В этом она отличается от стандартных ассоциативных контейнеров, где по умолчанию используется функция сравнения less. Смысл этого изменения не сводится к простой замене функции. Хэшированные контейнеры SGI сравнивают два объекта, проверяя их равенство, а неэквивалентность (см. совет 19). Для хэшированных контейнеров такое решение вполне разумно, поскольку в хэшированных ассоциативных контейнерах, в отличие от их стандартных аналогов (обычно построенных на базе деревьев), элементы не хранятся в отсортированном порядке.



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

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

tempiate<typename Т,typename CompareFunction> class hash compare;

tempiate<typename T.

typename Hashinglnfo = hash compare<T,less<T .

typename Allocator = anocator<T class hash set;

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

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

tempiate<typename Т.typename CompareFunction=less<T

class hash compare{

public:

enum{

bucket size = 4. Максимальное отношение числа элементов к числу гнезд min buckets = 8 Минимальное количество гнезд

size t operatorO(const Т&) const: Хзш-функция

bool operatorO (const T&,

const T&) const:

Некоторые подробности опущены,

включая использование CompareFunction

Перегрузка operatorO (в данном случае для реализации функций хэширования и сравнения) используется гораздо чаще, чем можно представить. Другое применение этой концепции продемонстрировано в совете 23.

Реализация Dinkumware позволяет программисту написать собственный класс-аналог hashcompare (возможно, объявленный производным от hashcompare). Если этот класс будет определять bucketsize, minbuckets, две функции operatorO (с одним и с двумя аргументами) и еще несколько мелочей, не упомянутых выше, он может использоваться для управления конфигурацией и поведением контейнеров Dinkumware hash set и hash multiset. Управление конфигурацией hash map и hash multimap осуществляется аналогичным образом.



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

hash set<int> intTable: Создать хзшированное множество int

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

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

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



1 ... 29 30 31 [ 32 ] 33 34 35 ... 71

© 2006 - 2024 pmbk.ru. Генерация страницы: 0
При копировании материалов приветствуются ссылки.
Яндекс.Метрика