|
Программирование >> Включение нужных заголовков
хэшированных ассоциативных контейнеров с вполне стандартными именами: 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 вам за них даже не придется платить.
|
© 2006 - 2024 pmbk.ru. Генерация страницы: 0
При копировании материалов приветствуются ссылки. |