为何对std::set使用全局std::upper_bound时时间复杂度为线性？

【警告！】
若将s.upper_bound(7)替换为upper_bound(s.begin(), s.end(), 7)——即前置模块中用于vector的语法，虽能得到预期结果，但时间复杂度为集合s大小的线性O(n)，而非对数级O(logN)，请务必避免！

核心差异说明 #

这两种写法最终都能找到集合中大于7的第一个元素，但底层实现逻辑完全不同：

• upper_bound(s.begin(), s.end(), 7)是C++标准库的通用算法，它只识别迭代器，不了解容器内部结构。执行时会从起始迭代器开始逐个遍历元素做比较，直到找到符合条件的元素，因此时间复杂度为线性O(n)，元素数量越多，耗时越长。
• s.upper_bound(7)是std::set的成员函数，而std::set底层基于红黑树（一种平衡二叉搜索树）实现。该成员函数可以直接利用红黑树的有序结构，通过二分查找快速定位目标元素，时间复杂度为对数级O(logN)，数据量越大，和通用算法的效率差距就越显著。

代码示例对比 #

// 通用算法版本：O(n) 线性遍历
upper_bound(s.begin(), s.end(), 7 );
// set成员函数版本：O(logN) 二分查找
s.upper_bound(7);

内容的提问来源于stack exchange，提问作者Abdullah Kassar