13.3. Boost.Unordered
Boost.Unordered 在 C++ 标准容器 std::set
, std::multiset
, std::map
和 std::multimap
的基础上多实现了四个容器: boost::unordered_set
, boost::unordered_multiset
, boost::unordered_map
和 boost::unordered_multimap
。 那些名字很相似的容器之间并没有什么不同, 甚至还提供了相同的接口。 在很多情况下, 替换这两种容器 (std 和 boost) 对你的应用不会造成任何影响。
Boost.Unordered 和 C++ 标准里的容器的不同之处在于—— Boost.Unordered 不要求其中的元素是可排序的, 因为它不会做出排序操作。 在排序操作无足轻重时(或是根本不需要), Boost.Unordered 就很合适了。
为了能够快速的查找元素, 我们需要使用 Hash 值。 Hash 值是一些可以唯一标识容器中元素的数字, 它在比较时比起类似 String 的数据类型会更加有效率。 为了计算 Hash 值, 容器中的所有元素都必须支持对他们自己唯一 ID 的计算。 比如 std::set
要求其中的元素都要是可比较的, 而 boost::unordered_set
要求其中的元素都要可计算 Hash 值。 尽管如此, 在对排序没有需求时, 你还是应该倾向使用 Boost.Unordered 。
下面的例子展示了 boost::unordered_set
的用法。
- #include <boost/unordered_set.hpp>
- #include <iostream>
- #include <string>
- int main()
- {
- typedef boost::unordered_set<std::string> unordered_set;
- unordered_set set;
- set.insert("Boris");
- set.insert("Anton");
- set.insert("Caesar");
- for (unordered_set::iterator it = set.begin(); it != set.end(); ++it)
- std::cout << *it << std::endl;
- std::cout << set.size() << std::endl;
- std::cout << set.max_size() << std::endl;
- std::cout << (set.find("David") != set.end()) << std::endl;
- std::cout << set.count("Boris") << std::endl;
- }
boost::unordered_set
提供了与 std::set
相似的函数。 当然, 这个例子不需要多大改进就可以用 std::set
来实现。
下面的例子展示了如何用 boost::unordered_map
来存储每一个的 person 的 name 和 age。
- #include <boost/unordered_map.hpp>
- #include <iostream>
- #include <string>
- int main()
- {
- typedef boost::unordered_map<std::string, int> unordered_map;
- unordered_map map;
- map.insert(unordered_map::value_type("Boris", 31));
- map.insert(unordered_map::value_type("Anton", 35));
- map.insert(unordered_map::value_type("Caesar", 25));
- for (unordered_map::iterator it = map.begin(); it != map.end(); ++it)
- std::cout << it->first << ", " << it->second << std::endl;
- std::cout << map.size() << std::endl;
- std::cout << map.max_size() << std::endl;
- std::cout << (map.find("David") != map.end()) << std::endl;
- std::cout << map.count("Boris") << std::endl;
- }
就像我们看到的, boost::unordered_map
和 std::map
之间并没多大区别。 同样地, 你可以很方便的用 std::map
来重新实现这个例子。
就像上面提到过的, Boost.Unordered 需要其中的元素可计算 Hash 值。 一些类似于 std::string
的数据类型“天生”就支持 Hash 值的计算。 对于那些自定义的类型, 你需要手动的定义 Hash 函数。
- #include <boost/unordered_set.hpp>
- #include <string>
- struct person
- {
- std::string name;
- int age;
- person(const std::string &n, int a)
- : name(n), age(a)
- {
- }
- bool operator==(const person &p) const
- {
- return name == p.name && age == p.age;
- }
- };
- std::size_t hash_value(person const &p)
- {
- std::size_t seed = 0;
- boost::hash_combine(seed, p.name);
- boost::hash_combine(seed, p.age);
- return seed;
- }
- int main()
- {
- typedef boost::unordered_set<person> unordered_set;
- unordered_set set;
- set.insert(person("Boris", 31));
- set.insert(person("Anton", 35));
- set.insert(person("Caesar", 25));
- }
在代码中, person
类型的元素被存到了 boost::unordered_set
中。 因为 boost::unordered_set
中的 Hash 函数不能识别 person
类型, Hash 值就变得无法计算了。 若果没有定义另一个 Hash 函数, 你的代码将不会通过编译。
Hash 函数的签名必须是: hash_value()
。 它接受唯一的一个参数来指明需要计算 Hash 值的对象的类型。 因为 Hash 值是单纯的数字, 所以函数的返回值为: std::size_t
。
每当一个对象需要计算它的 Hash 值时, hash_value()
都会自动被调用。 Boost C++ 库已经为一些数据类型定义好了 Hash 函数, 比如: std::string
。 但对于像 person
这样的自定义类型, 你就需要自己手工定义了。
hash_value()
的实现往往都很简单: 你只需要按顺序对其中的每个属性都调用 Boost 在 boost/functional/hash.hpp
中提供的 boost::hash_combine()
函数就行了。 当你使用 Boost.Unordered 时, 这个头文件已经自动被包含了。
除了自定义 hash_value()
函数, 自定义的类型还需要支持通过 ==
运算符的比较操作。 因此, person
就重载了相应的 operator==()
操作符。