使用Visual Studio 2010的C++。一个关于为什么用户定义的hash_map
特征实际上需要完全排序的问题。
我有一个简单的结构,比如说FOO
,它只有一些整数。我想要使用hash_map
来存储FOO
的结构,hash_map
是一个哈希表,其键是无序的。我只需要快速搜索它的相关值,所以这是一个正确的选择: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;
};
以下是对 MSDN 中 bool operatod() 的详细描述:
对于序列中任何类型为 Key 的值 _Key1,如果它在序列中位于 _Key2 之前并且具有相同的哈希值(哈希函数返回的值),则 hash_comp(_Key2, _Key1) 为 false。该函数必须对类型为 Key 的值施加完全排序。
由 hash_compare 提供的函数返回 comp(_Key2, _Key1),其中 comp 是您在构造对象 hash_comp 时可以指定的类型 Traits 的存储对象。对于默认的 Traits 参数类型 less,排序键永远不会减小其值。
编写 FOO 的 hash_compare 类非常容易。这个问题不是要求您如何实现一个类。然而,我不太明白为什么它们将默认的特征参数设置为 less 并要求完全排序。
hash_map 是一种无序数据结构。因此,我认为只需要 equal_to 或 not_equal_to 而不是 less 或 greater 就足够了。但是,MSDN 的描述明确说明键是有序的,这让我感到困惑。
我是否误解了 hash_map 的定义?为什么 STL 的 hash_map 实际上要求其键有序?