13.3. Boost.Unordered

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==() 操作符。