C++关于boost :: unordered_map和boost :: hash的一些问题

Question

我最近才开始关注boost和它的容器,我在网上阅读了一些文章,在stackoverflow上,boost :: unordered_map是大型集合中表现最快的容器.所以,我有这个类State,它必须在容器中是唯一的(没有重复),并且容器中将有数百万甚至数十亿个状态.因此,我一直在尝试优化它以实现小尺寸和尽可能少的计算.之前我正在使用boost :: ptr_vector,但是当我在stackoverflow上读到时,只要没有那么多对象,向量就是好的.在我的情况下,状态描述来自机器人的感觉运动信息,因此可能存在大量状态,因此快速查找是最重要的.在unordered_map 的boost文档之后,我意识到我可以做两件事来加快速度:使用hash_function,并使用相等运算符根据hash_function比较状态.因此,我实现了一个私有hash()函数,它接收状态信息并使用boost :: hash_combine,创建一个std :: size_t哈希值.operator ==基本上比较状态的哈希值.所以:

• 是std :: size_t足以覆盖数十亿可能的hash_function组合吗？为了避免重复状态,我打算使用他们的hash_values.

• 在创建state_map时,我应该使用State*或哈希值作为键吗？即:boost::unordered_map<State*,std::size_t> state_map; 或 boost::unordered_map<std::size_t,State*> state_map;

• 使用boost :: unordered_map :: iterator = state_map.find()的查找时间比通过boost :: ptr_vector并比较每个迭代器的键值更快吗？

• 最后,任何关于如何优化这种无序地图以获得速度和快速查找的提示或技巧将不胜感激.

编辑:我已经看到了不少答案,一个不使用boost而是使用C++ 0X,另一个不使用unordered_set,但说实话,我还是想看看boost :: unordered_set如何与hash函数一起使用.我已经按照boost的文档进行了实现,但我仍然无法弄清楚如何使用boost的hash函数和有序集.

Answer 1

这有点混乱。

• 你所说的不是“你可以做的事情来加快速度”；相反，它们是您的类型有资格作为无序映射的元素类型以及无序集（您可能更想要）的元素类型的强制性要求。

• 您需要提供一个比较对象而不是哈希值的相等运算符。相等的要点是区分具有相同哈希值的元素。

• size_t是无符号整数类型，x86 上为 32 位，x64 上为 64 位。由于您想要“数十亿个元素”，这意味着许多 GB 的数据，因此我假设您无论如何都有一台可靠的 x64 机器。

• 关键是你的哈希函数很好，即很少有冲突。

• 你想要一套，而不是地图。将对象直接放入集合中：std::unordered_set<State>。如果您要映射到某些内容（即状态到其他内容），请使用映射。哦，如果可以的话，使用 C++0x，而不是 boost。

• 使用起来hash_combine还是不错的。

宝贝例子：

struct State
{
  inline bool operator==(const State &) const;
  /* Stuff */
};

namespace std
{
  template <> struct hash<State>
  {
    inline std::size_t operator()(const State & s) const
    {
      /* your hash algorithm here */
    }
  };
}

std::size_t Foo(const State & s) { /* some code */ }

int main()
{
  std::unordered_set<State> states; // no extra data needed
  std::unordered_set<State, Foo> states; // another hash function
}