hash_map：为什么它定义 less，而不是 equal_to

Question

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

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

但是，我需要为 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;
   };

以下是 MSDN 中 bool operatod() 的详细描述：

对于序列中 位于 _Key2 之前且具有相同哈希值（哈希函数返回的值）的任何 Key 类型值 _Key1，hash_comp(_Key2, _Key1) 为 false。该函数必须对 Key 类型的值施加总排序。

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

为 FOO 编写 hash_compare 类很容易。这个问题不是询问如何实现一个类。然而，对我来说，为什么它们的默认特征参数为 less 并需要总排序，这对我来说并不简单。

hash_map 是一种无序数据结构。因此，我认为使用 equal_to 或 not_equal_to 而不是 less 或 greater 就足够了。然而，MSDN 的描述明确指出键是有序的，这让我很困惑。

我是否误解了 hash_map 的定义？为什么STL的hash_map实际上需要它的key的顺序？

Answer 1

对于序列中 位于 _Key2 之前且具有相同哈希值（值
由哈希函数返回），hash_comp(_Key2, _Key1) 为 false。该函数必须强加一个
Key 类型值的总排序。

具有相同哈希值的键的总排序保证了哈希到同一桶的键的总排序。

这为更有效地实现特定存储桶内的键搜索提供了机会 - 例如，可以进行 θ(log n) 二分搜索。如果没有这样的保证排序，最坏的情况（许多不同的键都在同一个桶中，因为它们都散列到相同的值）是 θ(n)。

Answer 2

您正在查看的 hash_map 是 VS2003 中引入的 Microsoft 扩展，实际上现在位于 Visual C++ 中的 stdext 中 - 它不是 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;

Answer 3

hash_map 的具体要求因实现而异，其中一些要求（如您所见）没有多大意义。这就是他们决定不在 TR1 和/或 C++0x 中包含 hash_map（或 hash_*）的部分原因。相反，它们有 unordered_[multi](map|set)，只需要 equal_key，而不需要 operator<。

底线：除非您确实有充分的理由要这样做，否则请使用 unordered_map 而不是 hash_map。