c++ - boost::intrusive::unordered_set 桶中使用的是什么存储策略？

Question

我知道 boost 桶在内部是作为喜欢的列表实现的，对吗？至少根据http://www.boost.org/doc/libs/1_50_0/doc/html/unordered/buckets.html好像是。

我的问题是，这些桶中元素的顺序是什么？如果它们是无序的，是否有任何方法可以对这些存储桶中的项目顺序强制执行 MRU(最近使用的)或其他一些移至前端的启发式方法？

编辑:我理解反对在存储桶内强制执行 MRU 的争论。但在我的具体情况下，我知道，强制执行 MRU [或什至采用后进先服务] 的性能优于较小的负载系数。问题是，顺序是什么？有没有一种简单的方法来至少强制执行最后插入先出&服务。

Answer 1

桶未排序。桶未排序的原因令人信服。虽然我确定您已经意识到这一点，但我将列举一些来帮助网站的 future 访问者。

1. 散列映射类型的数据结构不应使迭代器无效，除非插入导致重新散列
2. 为了保持快速查找，桶应该很小；理想情况下，每个桶中应该只有一个元素。

在我看来，强制对桶进行 MRU 排序似乎首先与散列映射类型结构的整个想法背道而驰。这个想法是保持桶小，这样平均而言，桶中的第一项就是您实际要查找的项目。

因此，我怀疑是否有任何内置方法可以在存储桶中强制执行 MRU 排序。我建议改为调整您的哈希算法，也许调低您的最大负载因子。