hash_map：为什么它定义的更少，而不是equal_to [英] hash_map: why it defines less, rather than equal_to

问题描述

C ++，使用Visual Studio 2010.有关为什么 hash_map 的用户定义特征实际上需要总排序的问题。

C++, using Visual Studio 2010. A question about why a user-defined trait of hash_map actually requires total ordering.

我有一个简单的结构，例如 FOO ，它只有一些整数。我想使用 hash_map ，这是一个哈希表，其键是无序，用于存储 FOO 。我只需要快速搜索其相关值，因此这是一个正确的选择： hash_map 。

I have a simple structure, say FOO, which only has a number of integers. I'd like to use hash_map, which is a hash table whose keys are unordered, to store the structure of FOO. I just need a fast searching of its associated value, so this is a right choice: hash_map<FOO, int32_t>.

但是，我需要实现自己的哈希函数和一些比较函数 FOO 。下面是从MSDN中获取的 hash_map 的定义：

However, I need to implement my own hash function and some compare functions for FOO. Here is the definitions of hash_map, taken from 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 functors：

It turned out that I needed to implement hash_compare functors:

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;
   };

以下是MSDN中bool操作的详细说明：

Here is the detailed description of the bool operatod() from MSDN:

对于序列中 _Key2之前的类型Key的任何值_Key1，并且具有相同的散列值（散列函数返回的值），hash_comp（_Key2， _Key1）为false。

For any value _Key1 of type Key that precedes _Key2 in the sequence and has the same hash value (value returned by the hash function), hash_comp(_Key2, _Key1) is false. The function must impose a total ordering on values of type Key.

hash_compare提供的函数返回comp（_Key2，_Key1），其中comp是类型Traits的存储对象，您可以在构造对象hash_comp时指定。对于默认的Traits参数类型less，排序键的值不会减小。

The function supplied by hash_compare returns comp(_Key2, _Key1), where comp is a stored object of type Traits that you can specify when you construct the object hash_comp. For the default Traits parameter type less, sort keys never decrease in value.

很容易写 hash_compare 类 FOO 。这个问题不是用于询问如何实现一个类。然而，我不明白为什么他们有默认的trait参数少< key> 并且需要总排序。

It was easy to write the hash_compare class for FOO. This question is not for asking how to implement a class. However, it's not straightforward for me that why they have the default trait parameter as less<key> and require total ordering.

hash_map 是无序的数据结构。所以，我认为只需要 equal_to 或 not_equal_to 而不是 less 或 greater 。

hash_map is an unordered data structure. So, I thought that it would be sufficient to have equal_to or not_equal_to instead of less or greater. However, the description of MSDN explicitly states that keys are ordered, which confuses me.

我误解了 hash_map ？为什么STL的 hash_map 实际上需要其关键字的订单？

Did I misunderstand the definition of hash_map? Why STL's hash_map actually require orders of its key?

推荐答案

对于序列中 _Key2之前的类型Key的任何值_Key1，并且具有相同的散列值（散列函数返回值
），hash_comp（_Key2，_Key1）是假的。该函数必须对Key类型的值强制执行
总排序。

具有相同散列值的键保证了散列到同一存储桶的键的总排序。

A total ordering of keys with the same hash value guarantees a total ordering of keys which hash to the same bucket.

这提供了更有效地实现对键的搜索的机会在特定桶内 - 例如Θ（log n）二进制搜索是可能的。如果没有这样的保证排序，则最坏情况（许多不同的密钥都在相同桶中，因为它们都散列到相同的值）是Θ（n）。

That provides the opportunity for a more efficient implementation of search for a key within a particular bucket - e.g. Θ(log n) binary search is possible. If there is no such guaranteed ordering, the worst case (many different keys which are all in the same bucket because they all hash to the same value) is Θ(n).

这篇关于hash_map：为什么它定义的更少，而不是equal_to的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！