std :: unordered_map中的bucket接口有什么用？

Question

我一直在观看CppCon 2014的这个视频,发现有一个接口可以访问下面的存储桶std::unordered_map.现在我有几个问题:

• 有没有合理的使用此接口的例子？
• 为什么委员会决定定义这个界面,为什么典型的STL容器接口还不够？

Answer 1

搜索引入项目的提案通常很有启发性,因为通常有一个附带的理由.在这种情况下,N1443说:

G.桶接口

与所有标准容器一样,每个散列容器都具有成员函数begin()和end().范围[c.begin(),c.end())包含容器中的所有元素,以平坦范围表示.存储桶中的元素是相邻的,但迭代器接口不提供有关一个存储桶结束和下一个存储桶开始的信息.

由于两个原因,暴露铲斗结构也很有用.首先,它允许用户调查他们的哈希函数的执行情况:它让他们测试元素在桶中的均匀分布,并查看存储桶中的元素以查看它们是否具有任何公共属性.其次,如果迭代器具有底层分段结构(就像它们在现有的单链表实现中那样),那么利用该结构的算法(具有显式嵌套循环)可能比将元素视为平坦范围的算法更有效.

bucket接口最重要的部分是begin()和end()的重载.如果n是整数,[begin(n),end(n))是指向第n个桶中元素的迭代器范围.当然,这些成员函数返回迭代器,但不是X :: iterator或X :: const_iterator类型.相反,它们返回X :: local_iterator或X :: const_local_iterator类型的迭代器.本地迭代器能够在桶内迭代,但不一定在桶之间迭代; 在某些实现中,X :: local_iterator可能是比X :: iterator更简单的数据结构.允许X :: iterator和X :: local_iterator使用相同的类型; 使用双向链表的实现可能会利用这种自由.

SGI,Dinkumware或Metrowerks实现不提供此存储桶接口.它部分受到了Metrowerks碰撞检测界面的启发,部分受到早期工作(参见[Austern 1998])关于分段容器算法的启发.