-2

假设那个sizeof(void*) == sizeof(size_t)和那个散列指针只是将它转换为size_t. 所以我想知道我的集合是否包含一个元素,哪个会更快std::set<void*>std::unordered_set<void*>

我知道如何std::set工作,但我不熟悉std::unordered_set. 好吧,我知道无序集使用散列和桶,如果没有发生交集(这是我的情况),复杂性是O(1)。但我不知道这种恒定的复杂性有多少。

如果容器中有多少日期是相关的,我的实际场景使用不到一百个¹。但我的好奇心涉及元素很少和元素很多的两种情况。

¹ 元素的数量是如此之少,以至于即使 astd::vector也会表现良好。

4

2 回答 2

8

我认为重要的是在小脚注中:

元素的数量是如此之少,以至于即使 astd::vector也会表现良好。

std::vectorstd::setand对缓存更友好std::unordered_set,因为它在内存的连续区域中分配其元素(这是标准规定的)。

尽管查找和插入复杂度std::vector比 for std::setor更差std::unordered_set(分别是线性与O(log N)和摊销O(1)),但数据局部性和更高的缓存命中率可能会主导计算复杂性并产生更好的性能.

一般来说,无论如何,您选择的数据结构对性能的影响还取决于您想要对它们执行的操作类型和它们的频率——这在您的帖子中没有提到。

但是,与往常一样,在您承诺使用一种替代方案之前,请先衡量不同的替代方案,并且当您没有证据表明它代表了阻碍您的应用程序满足其性能要求的瓶颈时,总是倾向于使用更简单的设计。

于 2013-05-23T23:12:34.697 回答
2

unordered_set具有比set许多实现更好的缓存局部性。但是由于在您的情况下元素的数量非常少,因此 avector可能完全适合缓存,因此尽管查找元素的复杂度为 O(n),但它还是一个更好的选择。

于 2013-05-23T23:12:27.587 回答