hash_map: почему он определяет меньше, а не equal_to - PullRequest
Новая
       6

hash_map: почему он определяет меньше, а не equal_to

4 голосов
/ 25 октября 2010

C ++, с использованием Visual Studio 2010. Вопрос о том, почему определяемая пользователем черта hash_map фактически требует полного упорядочения.

У меня есть простая структура, скажем, FOO, которая имеет только несколько целых чисел. Я хотел бы использовать hash_map, которая является хеш-таблицей, ключи которой неупорядочены , для хранения структуры FOO. Мне просто нужен быстрый поиск соответствующего значения, так что это правильный выбор: hash_map<FOO, int32_t>.

Однако мне нужно реализовать собственную хеш-функцию и некоторые функции сравнения для FOO. Вот определения hash_map, взятые из MSDN: 

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

Оказалось, что мне нужно реализовать hash_compare функторы: 

template<class Key, class Traits = less<Key> >
   class hash_compare
   {
   Traits comp;
public:
   const size_t bucket_size = 4;
   const size_t min_buckets = 8;
   hash_compare( );
   hash_compare( Traits pred );
   size_t operator( )( const Key& _Key ) const; // This is a hash function
   bool operator( )(                            // This is an ordering function
      const Key& _Key1,
      const Key& _Key2
   ) const;
   };

Вот подробное описание операции bool () из MSDN:

Для любого значения _Key1 типа Key, которое предшествует _Key2 в последовательности и имеет такое же хеш-значение (значение, возвращаемое хэш-функцией), hash_comp (_Key2, _Key1) равно false. Функция должна накладывать общее упорядочение на значения типа Key.

Функция, предоставляемая hash_compare, возвращает comp (_Key2, _Key1), где comp - это сохраненный объект типа Traits, который вы можете указать при создании объекта hash_comp. Для параметра типа Черты по умолчанию меньше, ключи сортировки никогда не уменьшаются в значении.

Было легко написать класс hash_compare для FOO. Этот вопрос не для того, чтобы спросить, как реализовать класс. Однако для меня непросто, почему они имеют параметр черты по умолчанию less<key> и требуют полного упорядочения.

hash_map - это неупорядоченная структура данных. Итак, я подумал, что было бы достаточно иметь equal_to или not_equal_to вместо less или greater. Однако в описании MSDN прямо указано, что ключи упорядочены, что меня смущает.

Я неправильно понял определение hash_map? Почему STL hash_map действительно требуют приказы своего ключа?

Ответы [ 3 ]

3 голосов
/ 26 октября 2010

hash_map, на которую вы смотрите, - это расширение Microsoft, появившееся в VS2003 и фактически теперь в stdext в Visual C ++ - оно не является частью STL.

std::unordered_map является официальной STL-версией ассоциативного контейнера с доступом к значению по хэш-ключу - предикат для этого равен, как вы и ожидали. 

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;
3 голосов
/ 26 октября 2010

Для любого значения _Key1 типа Key, которое предшествует _Key2 в последовательности и имеет такое же хеш-значение (значение, возвращаемое хэш-функцией), hash_comp (_Key2, _Key1) равно false.Функция должна наложить общее упорядочение на значения типа Key.

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

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

2 голосов
/ 26 октября 2010

Точные требования к hash_map варьируются в зависимости от реализации, и некоторые из них (как вы видели) не имеют большого смысла.Это часть того, почему они решили , а не , чтобы включить hash_map (или hash_*) в TR1 и / или C ++ 0x.Вместо этого они имеют unordered_[multi](map|set), для чего требуется только equal_key, а не operator<.

Итог: если у вас нет действительно веской причины поступить иначе, используйте unordered_map вместо hash_map.

...