13.3. Boost.Unordered

Boost.Unordered 在 C++ 标准容器 std::setstd::multisetstd::mapstd::multimap 的基础上多实现了四个容器: boost::unordered_setboost::unordered_multisetboost::unordered_mapboost::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 的用法。

  1. #include <boost/unordered_set.hpp>
  2. #include <iostream>
  3. #include <string>
  4.  
  5. int main()
  6. {
  7. typedef boost::unordered_set<std::string> unordered_set;
  8. unordered_set set;
  9.  
  10. set.insert("Boris");
  11. set.insert("Anton");
  12. set.insert("Caesar");
  13.  
  14. for (unordered_set::iterator it = set.begin(); it != set.end(); ++it)
  15. std::cout << *it << std::endl;
  16.  
  17. std::cout << set.size() << std::endl;
  18. std::cout << set.max_size() << std::endl;
  19.  
  20. std::cout << (set.find("David") != set.end()) << std::endl;
  21. std::cout << set.count("Boris") << std::endl;
  22. }

boost::unordered_set 提供了与 std::set 相似的函数。 当然, 这个例子不需要多大改进就可以用 std::set 来实现。

下面的例子展示了如何用 boost::unordered_map 来存储每一个的 person 的 name 和 age。

  1. #include <boost/unordered_map.hpp>
  2. #include <iostream>
  3. #include <string>
  4.  
  5. int main()
  6. {
  7. typedef boost::unordered_map<std::string, int> unordered_map;
  8. unordered_map map;
  9.  
  10. map.insert(unordered_map::value_type("Boris", 31));
  11. map.insert(unordered_map::value_type("Anton", 35));
  12. map.insert(unordered_map::value_type("Caesar", 25));
  13.  
  14. for (unordered_map::iterator it = map.begin(); it != map.end(); ++it)
  15. std::cout << it->first << ", " << it->second << std::endl;
  16.  
  17. std::cout << map.size() << std::endl;
  18. std::cout << map.max_size() << std::endl;
  19.  
  20. std::cout << (map.find("David") != map.end()) << std::endl;
  21. std::cout << map.count("Boris") << std::endl;
  22. }

就像我们看到的, boost::unordered_mapstd::map 之间并没多大区别。 同样地, 你可以很方便的用 std::map 来重新实现这个例子。

就像上面提到过的, Boost.Unordered 需要其中的元素可计算 Hash 值。 一些类似于 std::string 的数据类型“天生”就支持 Hash 值的计算。 对于那些自定义的类型, 你需要手动的定义 Hash 函数。

  1. #include <boost/unordered_set.hpp>
  2. #include <string>
  3.  
  4. struct person
  5. {
  6. std::string name;
  7. int age;
  8.  
  9. person(const std::string &n, int a)
  10. : name(n), age(a)
  11. {
  12. }
  13.  
  14. bool operator==(const person &p) const
  15. {
  16. return name == p.name && age == p.age;
  17. }
  18. };
  19.  
  20. std::size_t hash_value(person const &p)
  21. {
  22. std::size_t seed = 0;
  23. boost::hash_combine(seed, p.name);
  24. boost::hash_combine(seed, p.age);
  25. return seed;
  26. }
  27.  
  28. int main()
  29. {
  30. typedef boost::unordered_set<person> unordered_set;
  31. unordered_set set;
  32.  
  33. set.insert(person("Boris", 31));
  34. set.insert(person("Anton", 35));
  35. set.insert(person("Caesar", 25));
  36. }

在代码中, 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==() 操作符。