c++ - 将 unordered_set 存储为 unordered_map 中的键是个好主意吗

Question

我希望将 unordered_set 作为键存储在 unordered_map 中，这是个好主意还是我应该使用 std::set 存储一些数据，然后使用 std::map 将 std::set 存储为键。哪个更适合性能/查找？

任何建议都会有所帮助

Answer 1

与许多与数据结构性能相关的问题一样，准确的答案将取决于您的数据集。
考虑到您只对查找性能感兴趣，小型数据集通常会倾向于使用容器的有序版本，其中“数据集”是指键类型的键中元素的平均数量（set 与 unordered_set），以及外部地图类型（map vs. unordered_map）的（set，value_type）项的数量。顺便说一句，没有什么可以阻止您混合有序和无序容器，例如 unordered_map、value_type>
尽管如此，100% 确定哪个容器更好的唯一方法是使用您的实际数据对其进行分析。

考虑到这一点，这里有更多细节：

• 对于外部容器，使用 unordered_map 很有可能会根据散列容器的通常特性提供更​​好的查找性能。但是，有一个更微妙的影响，这取决于关键容器的哈希小于运算符和函数的比较性能。
• 对于关键容器，查找性能受容器小于运算符（如果您的外部容器是地图）或其散列函数（如果您的外部容器是 unordered_map）的相对性能的影响。

稍后我将尝试发布一些实际测试来衡量这一点。