如何使用algorithm库在set容器中快速查找小于等于给定值的元素

首先明确结论：不推荐使用algorithm库的通用查找算法实现该需求，性能会远低于set容器自带的成员函数方案。

set本身是有序的红黑树结构，自带的lower_bound、upper_bound成员函数时间复杂度为O(logn)，而algorithm库中的通用同名算法，针对set的双向迭代器只能顺序遍历，时间复杂度为O(n)，性能差异极大。

你要找小于等于给定值的最大元素，直接按以下逻辑实现即可：

• 调用set自带的upper_bound(目标值)，得到第一个大于目标值的元素迭代器
• 若迭代器等于begin()，说明容器内所有元素都大于目标值，无符合条件的结果
• 若迭代器不等于begin()，将迭代器前移1位，得到的就是小于等于目标值的最大元素

代码示例 #

#include <set>
#include <iostream>

int main() {
    std::set<int> test_set = {2, 4, 6, 8, 10};
    int target = 7;

    auto iter = test_set.upper_bound(target);
    if (iter != test_set.begin()) {
        --iter;
        std::cout << "小于等于" << target << "的元素为：" << *iter << std::endl; // 输出6
    } else {
        std::cout << "不存在小于等于" << target << "的元素" << std::endl;
    }
    return 0;
}

如果一定要用algorithm库实现，写法是std::prev(std::upper_bound(test_set.begin(), test_set.end(), target))，但还是要再次强调，该写法性能极低，除非特殊场景否则完全不建议使用。

内容的提问来源于stack exchange，提问作者Фёдор