对于操作count().哪个更快std :: set <void*>或std :: unordered_set <void*>？

Question

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

我知道怎么std::set运作,但我不熟悉std::unordered_set.好吧,我知道无序集使用散列和桶,如果没有交叉(这是我的情况),复杂性是O(1).但我不知道这种复杂程度有多大.

如果容器中的日期相关,我的实际情况使用不到一百¹.但是我的好奇心只涉及几个元素和很多元素的情况.

¹元素的数量很少,甚至std::vector可以表现良好.

Answer 1

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

元素的数量很少,甚至一个std::vector表现也不错.

std::vector是多个高速缓存比友好std::set和std::unordered_set,因为它分配其在存储器的连续区域的元素(这是由标准规定的).

虽然查找和插入复杂性std::vector比std::setor或std::unordered_set(线性对O(log N)和分摊的O(1)分别更差),但数据位置和更高的缓存命中率可能会主导计算复杂性并产生更好的性能.

一般而言,无论如何,您选择的数据结构对性能的影响还取决于您要对它们执行的操作类型及其频率 - 这在您的帖子中没有提到.

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