我将指针存储在 std::unordered_set 中。我这样做是因为我不想要任何重复项（我删除了集合中的指针，所以如果有重复项，我将尝试删除一个已经删除的指针）。我在这些集合中大量循环，因为我知道 std::vector 是最快的循环容器（连续内存），我想知道 std::unordered_set 是否也这样做。
如果没有，使用 std::vector 并检查指针是否已被删除会更快吗？
问问题
4712 次
4 回答
19
是
std::unordered_set连续的吗？
标准没有详细说明容器的确切实现......但是标准确实规定了一些限制实际表示的行为。
例如，std::unordered_set需要内存稳定：即使添加/删除其他元素，对元素的引用/地址也是有效的。
实现这一点的唯一方法是或多或少独立地分配元素。它不能通过连续的内存分配来实现，因为这样的分配必然是有界的，因此可能会过度生长，不可能在更大的块中重新分配元素。
于 2013-01-17T18:05:23.813 回答
4
不，它不是连续内存，但由于哈希映射，它仍然非常快。
编辑：快速随机访问，如果你主要做循环，你应该考虑另一个容器，我认为。
Edit2：您应该进行分析，以便了解是否值得考虑另一个容器。（也许你应该优化其他地方......也许）。
于 2013-01-17T17:27:32.063 回答
4
提供以下成员函数的事实std::unordered_map表明它是基于散列表的，可能是
使用链表单独链接。
bucket_count, hash_function, load_factor, max_load_count, rehash
元素是否连续取决于分配器。和的默认分配器不会在连续内存中分配元素。unordered_maplist每个元素的内存是在插入时分配的。
但是，您可以提供自定义分配器（例如池分配器），它可以从预先分配的内存池中分配元素。尽管如此，数据结构中逻辑上相邻的元素在内存中可能并不物理上相邻。
因此，如果循环遍历所有元素是最频繁的操作，那么这unordered_map可能不是最佳解决方案。通过分析器为所有竞争解决方案运行主要用例将揭示最佳解决方案。
除此之外，unordered_map循环不是另一个原因的最佳选择。请注意名称中的“无序”一词，它传达了 - 与list,vector或不同map-元素没有顺序。例如，成员函数rehash可能会改变元素的相对顺序。事实上，
在任何操作期间，只要其负载因子将超过 ，容器就会自动执行重新散列。max_load_factor
于 2013-01-17T18:35:24.543 回答
1
std::unordered_set 应该是一个哈希映射容器，所以我们可以假设它与 std::vector 相比有一点性能损失。
但是我认为如果 unordered_set 访问是真正的热点，您必须检查实际的分析结果。
如果您使用的 STL 实现是合理的，它应该为指针或 int 类型键提供类似向量的特化。如果为真，则专门针对指针类型的 unordered_set 的行为将与自动增长/收缩向量非常相似，并且性能差异将不明显。
于 2013-01-17T17:50:42.507 回答