由于标准库集合容器中的项目是经过排序的,在集合中使用查找成员通常会比对排序列表中的相同项目使用查找算法执行得更快吗?
由于列表是线性的并且集合通常使用排序树来实现,因此集合查找似乎应该更快。
最佳答案
对于链表,即使是排序的链表,查找元素也是 O(n)
。可以在 O(log n)
中搜索一个集合。因此,是的,在集合中查找元素渐近地更快。
可以使用二进制搜索在 O(log n)
中搜索排序的数组/vector 。不幸的是,由于链表不支持随机访问,因此不能使用相同的方法在 O(log n)
中搜索已排序的链表。
关于c++ - 设置查找成员与使用列表查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7516726/