如何对 std::unordered_set 桶中的元素进行排序？

Question

在填充 STL 的 unordered_set 后，我试图根据特定顺序对每个存储桶中的元素进行排序（尽管容器名称相互矛盾）。众所周知，不能对容器中的元素进行任何更改，据我所知，它会阻止标准 std::sort 工作。例如下一个代码将无法编译：

#include <unordered_set>
int main()
{
    std::unordered_set<int> set_;

    set_.max_load_factor(100);

    set_.insert(6);
    set_.insert(3);
    set_.insert(8);
    set_.insert(17);
    set_.insert(1);
    set_.insert(2);
    set_.insert(9);

    for (int i = 0; i < set_.bucket_count(); ++i)
    {
        std::sort(set_.begin(i), set_.end(i));
    }
}

那么，是否有解决该障碍的方法？是否可以得到一个临时排序的列表，然后将其分配给初始存储桶？

Answer 1

没有API做你正在做的事情，因为容器暴露一个接口，而不是一个实现，这违反了STL设计原则。不能保证 "sorting each bucket" 在一般情况下有任何意义（即使在您的特定实现中是可能的）。

如果您确定需要在散列 table 中 "sort each bucket"，则需要实现您自己的散列 table。考虑到大量的开源实现，这并不难。在通常使用链表实现存储桶的地方，您可能会使用平衡二叉树。

Answer 2

"in my real code ... a custom hash function ... places the elements the way I need" - 你确定吗？ - 您的自定义哈希函数不直接选择存储桶 - unordered_set 将其用作其存储桶选择的 an 输入，通常会执行类似 % bucket_count() 的操作，或者如果 bucket_count() 始终是 2 的幂，则可能 & (bucket_count() - 1) 作为优化。而且您不一定能控制桶的数量 - 调用 reserve(n) 可能会将 n 舍入到例如附近的（不一定是下一个）质数或可能是二的幂。所有实现均已定义。也就是说，您可以在您的散列函数中使用 bucket_count() 来真正控制您的键如何分组到桶中，或者只产生小于 n 您的散列值已经提供给 reserve()，但是当您这样做时，您还不如将索引管理到 std::vector 个键中。无论如何，够了 - 让我们相信你确实按照你想要的方式控制了 hashed-to 桶：如果你想要桶中元素的排序列表，你可以简单地使用：

std::unordered_map<KeyOnly, AnotherContainer<KeyAndValue>> x;

其中 AnotherContainer 是任何固有排序的容器（例如 std::set），或者可以按照您在问题中尝试的方式在您的代码中明确排序（例如 std::list , std::vector).

如何对 std::unordered_set 桶中的元素进行排序？

How to sort elements in a bucket of std::unordered_set?

c++

stl

unordered-map

hashtable

unordered-set