这两段代码为什么运行时间差了几十倍？

ym19940508

2017/9/14镜像同步6 回复

#include <iostream> #include <set> #include <algorithm> using namespace std; int main() { set<int> se; for (int i = 1; i < 100000; i++) { se.insert(i); } for (int i = 0; i < 100000; i++) { lower_bound(se.begin(), se.end(), 100000); se.lower_bound(1000000); } return 0; } lower_bound(se.begin(), se.end(), 100000);比se.lower_bound(1000000);慢了太多太多了，这是为什么呀哈

订阅后，新回复会通过你的通知中心匿名送达。

6 条回复

wjy1230机器人#1 · 2017/9/14

set版本的lower_bound应该针对红黑树进行了优化吧。通过『我邮2.0』发布

ym19940508机器人#2 · 2017/9/14

【在 wjy1230 的大作中提到: 】 : set版本的lower_bound应该针对红黑树进行了优化吧。 : 通过『我邮2.0』发布但是复杂度应该是相同的啊，效率上差了几十倍

wjy1230机器人#3 · 2017/9/14

看了一下msvc编译器的stl源码，algorithm中的lower_bound通过std::advance用偏移量来获得对应元素的迭代器，直接进行++操作，这个操作最终还是会转换为set迭代器的操作；set版本的lower_bound直接比较根节点关键字，然后进入左子树或右子树进一步查找。显然后者效率更高。你可以profiling一下，看看两种实现的差距出在哪。

intmain机器人#4 · 2017/9/14

泛型算法会根据传入参数的类型使用不同的方式，lower_bound算法面对随机迭代器时才会表现高效，而set的迭代器是单向顺序迭代器。 set容器自身的lower_bound的算法知道set的内部存储结构，所以可以根据红黑树的结构进行优化。

wjy1230机器人#5 · 2017/9/14

【在 ym19940508 的大作中提到: 】 : : 但是复杂度应该是相同的啊，效率上差了几十倍附件(816.6KB) 附件(1.3MB) 从这两幅图可以很清楚看出性能差距出在哪，algorithm的lower_bound直接对迭代器进行++操作。正如注释写的一样，它是通过偏移量来得到对应元素的迭代器。

hiyot机器人#6 · 2017/9/14

特意查了std:advance的复杂度, 是这样的: Linear. However, if InputIt additionally meets the requirements of RandomAccessIterator, complexity is constant.