Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Equality Predicates and Hash Functions 等同性謂詞和散列函數

While the associative containers use an ordering relation to specify how the elements are stored, the unordered associative containers use an equality predicate and a hash function. For example, boost::unordered_map is declared as:
關聯式容器使用一個排序關係來指定如何保存元素,而無序關聯式容器則使用一個等同性謂詞和一個散列函數。例如,boost::unordered_map 被聲明為:

template <
class Key, class Mapped,
class Hash = boost::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class unordered_map;

The hash function comes first as you might want to change the hash function but not the equality predicate. For example, if you wanted to use the FNV-1 hash you could write:
散列函數被放在前面,因為你可能想修改散列函數而不修改等同性謂詞。例如,如果你想使用 FNV-1 hash,你可以寫:

boost::unordered_map<std::string, int, hash::fnv_1>
dictionary;

There is an implementation of FNV-1 in the examples directory.
在 examples 目錄下有一個 FNV-1 的實現

If you wish to use a different equality function, you will also need to use a matching hash function. For example, to implement a case insensitive dictionary you need to define a case insensitive equality predicate and hash function:
如果你希望使用一個不同的等同性謂詞,你也需要使用一個相匹配的散列函數。例如,要實現一個大小寫不敏感的字典,你需要定義一個大小寫不敏感的等同性謂詞 和散列函數:

struct iequal_to
: std::binary_function<std::string, std::string, bool>
{
bool operator()(std::string const& x,
std::string const& y) const
{
return boost::algorithm::iequals(x, y, std::locale());
}
};
struct ihash
: std::unary_function<std::string, std::size_t>
{
std::size_t operator()(std::string const& x) const
{
std::size_t seed = 0;
std::locale locale;
for(std::string::const_iterator it = x.begin();
it != x.end(); ++it)
{
boost::hash_combine(seed, std::toupper(*it, locale));
}
return seed;
}
};

Which you can then use in a case insensitive dictionary:
然後你就可以在大小寫不敏感的字典中使用它們了:

boost::unordered_map<std::string, int, ihash, iequal_to>
idictionary;

This is a simplified version of the example at /libs/unordered/examples/case_insensitive.hpp which supports other locales and string types.
在 /libs/unordered/examples/case_insensitive.hpp 中有這個例子的簡化版本,它支持其它的 locales 和字符串類型。

Custom Types 定制類型

Similarly, a custom hash function can be used for custom types:
同樣,對於定制的類型可以使用定制的散列函數:

struct point {
int x;
int y;
};
bool operator==(point const& p1, point const& p2)
{
return p1.x == p2.x && p1.y == p2.y;
}
struct point_hash
: std::unary_function<point, std::size_t>
{
std::size_t operator()(point const& p) const
{
std::size_t seed = 0;
boost::hash_combine(seed, p.x);
boost::hash_combine(seed, p.y);
return seed;
}
};
boost::unordered_multiset<point, point_hash> points;

Since the default hash function is Boost.Hash, we can extend it to support the type so that the hash function doesn't need to be explicitly given:
由於缺省的散列函數是 Boost.Hash, 我們可以 對它進行擴展以支 持這個類型,所以散列函數不需要顯式給出:

struct point {
int x;
int y;
};
bool operator==(point const& p1, point const& p2)
{
return p1.x == p2.x && p1.y == p2.y;
}
std::size_t hash_value(point const& p) {
std::size_t seed = 0;
boost::hash_combine(seed, p.x);
boost::hash_combine(seed, p.y);
return seed;
}
// Now the default function objects work. 現在缺省的函數對象可以工作了。
boost::unordered_multiset<point> points;

See the Boost.Hash documentation for more detail on how to do this. Remember that it relies on extensions to the draft standard - so it won't work on other implementations of the unordered associative containers.
關於如何實現的更多細節,請見 Boost.Hash 文檔。記住,它依賴於標準草案的擴展部分 - 所以它在無序關聯式容器的其它實現中不一定可用。

Table 24.3. Methods for accessing the hash and equality functions.
表 24.3. 訪問散列函數和等同性函數的方法。

Method 方法

Description 說明

hasher hash_function() const

Returns the container's hash function.

返回容器的散列函數。

key_equal key_eq() const

Returns the container's key equality function.

返回容器的鍵類型的等同性函數。



PrevUpHomeNext