2

我知道内部提升存储桶是作为喜欢列表实现的，对吗？至少根据http://www.boost.org/doc/libs/1_50_0/doc/html/unordered/buckets.html似乎是这样。

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

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

4

2 回答 2

1

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

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

在我看来，强制执行桶的 MRU 排序似乎首先违背了哈希映射类型结构的整个想法。这个想法是保持桶小，这样平均来说，桶中的第一个项目就是你真正要找的那个。

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

于 2012-10-09T20:40:12.617 回答
0

经过一些黑客攻击，回答我自己的问题。

Boost buckets 的实现位于： http: //www.boost.org/doc/libs/1_51_0/boost/unordered/detail/buckets.hpp。

尽管这是特定于实现的并且可能随时更改，但目前，对于侵入性 unordered_set，桶遍历 [in .find()]从最后插入的项目开始。

例如，如果您要声明一个包含 1000 个存储桶的 unordered_set：

class A : public unordered_set_base_hook<> { ... }
unordered_set<A>::bucket_type buckets[1000];
unordered_set<A> a(unordered_set<A>::bucket_traits(buckets, 1000));

并插入 10000 个随机抽样的项目 [负载因子 10 高得离谱]，最后插入的项目将具有更快的 [按数量级] 访问 [查找] 时间。

于 2012-10-10T00:12:02.143 回答