C++中std::set::upper_bound和std::upper_bound的区别

在C++中，有两个upper_bound函数：std::set::upper_bound和std::upper_bound。这两个函数看起来很相似，但它们的用法和功能有所不同。本文将详细讲解这两个函数的区别。

std::upper_bound

std::upper_bound是标准C++中的函数，定义在头文件中。其原型如下：

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

std::upper_bound用于在指定的范围内查找第一个大于指定值的元素，最终返回一个迭代器，指向第一个大于指定值的元素。其中，参数first和last分别为确定查找范围的前后迭代器，而参数val指定要查找的值。

下面是一个使用std::upper_bound函数的例子：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v {1, 3, 5, 7, 9};
    auto it = upper_bound(v.begin(), v.end(), 4);
    if (it != v.end())
        cout << *it << endl;
    else
        cout << "Not Found" << endl;
    return 0;
}

输出为：

在上面的例子中，我们定义了一个名为v的整数向量，并使用std::upper_bound函数在其中查找第一个大于4的元素。结果，我们得到了5这个值。

需要注意的是，std::upper_bound使用提供的比较函数在容器中进行二分查找，因此容器中的元素必须已经按照从小到大的顺序排好序了。

std::set::upper_bound

std::set::upper_bound是std::set类中的函数，定义在头文件中。其原型如下：

iterator upper_bound (const value_type& val);

std::set::upper_bound函数和std::upper_bound函数有一些相似之处，都用于查找第一个大于指定值的元素，但其使用方法不同。std::set::upper_bound函数的参数是一个值，而不是一个范围。它返回一个迭代器，指向第一个大于指定值的元素。

下面是一个使用std::set::upper_bound函数的例子：

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s {1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto it = s.upper_bound(4);
    if (it != s.end())
        cout << *it << endl;
    else
        cout << "Not Found" << endl;
    return 0;
}

输出为：

在上面的例子中，我们定义了一个名为s的整数集合，并使用std::set::upper_bound函数在其中查找第一个大于4的元素。结果，我们得到了5这个值。

需要注意的是，std::set::upper_bound函数是通过红黑树查找指定值的位置，因此其复杂度为O(log n)，具有较优的查找速度。同时，std::set类也保证了其元素是按照从小到大排好序的。

区别

std::set::upper_bound和std::upper_bound两个函数的区别主要在于查找范围和参数输入的方式上。

std::upper_bound查找的范围是通过迭代器给定的，需要指定要查找的范围。而std::set::upper_bound只需指定一个值，它将在整个set中查找这个值，并返回第一个大于此值的元素。此外，std::set::upper_bound还具有较优的查找速度，因为set集合中的元素是按照从小到大排好序的，可以通过红黑树进行快速查找。

通常情况下，建议在使用std::set的场景下使用std::set::upper_bound，因为std::set的元素具有排序性质，相对于std::upper_bound的迭代器范围，std::set::upper_bound的查找速度更快。

结论

std::upper_bound和std::set::upper_bound两个函数虽然作用相同，但使用方法和内部实现有所不同。对于有序容器std::set来说，建议使用std::set::upper_bound函数，以获得更好的查找效率。如果需要在非有序容器中进行查找，可以使用std::upper_bound函数，但需要注意提供的比较函数和区间范围。