难道是set的遍历很慢的原因？
by 斗神·君莫笑 @ 2018-09-03 22:51:52
不是的，upper_bound是把你给的序列当成已经排好序的数组一样访问的（也就是说默认你给它的迭代器的iterator_category是random_access_iterator_tag，意思就是说它默认你的序列是连续存储的）。但是multiset是红黑树，它显然不是连续存储的，那么std::upper_bound用正常的二分法的时候就要花线性时间从当前区间的左端点移动到中点（如果是连续存储，这个操作就是O(1)的，因为地址直接加mid就好了）。这样的话可以证明时间复杂度是O(n)，当然就T了
而std::multiset::upper_bound是在这个红黑树上的二分（区别于在有序序列上的二分，因为地址不是连续存储的），当然是很稳的O(logn)
by GKxx @ 2018-09-03 23:09:54
其实std::upper_bound并不默认你的序列是连续存储，具体细节是这样：
在二分的过程中比方说当前区间是[left, right)，那么肯定要计算区间中点mid=left+distance(left, right)/2;。这个distance函数在头文件<iterator>里面，它会自动识别你的迭代器的类型（识别方法是依赖iterator_category，这是STL规定每个迭代器类都必须有的一个类型别名成员）。
如果你的迭代器上有operator-（比如vector的迭代器），就会直接返回相减的结果，那当然就是O(1)；但是如果没有，它就会从left开始++（因为STL规定所有迭代器都必须有operator++），一直++到等于right为止然后返回递增次数，这个distance的时间复杂度就是O(n*调用operator++一次需要的时间)。如果是在std::list上，就是O(n)，如果是在std::set之类的红黑树上可能就是O(nlogn)（所以我刚才回复的好像说错了，不是O(n)，应该是O(nlogn)），这只是一个distance的复杂度，那总的复杂度肯定就T飞了
by GKxx @ 2018-09-03 23:21:14
@[lcclcc](/space/show?uid=30033) emm STL还需要加`::`么?
`std::set`
总觉得STL加`::`怪怪的
by ToBiChi @ 2018-10-11 14:23:49