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

集合是一种关联容器，其中每个元素都必须唯一，因为元素的值标识了它。一旦将元素添加到集合中，其值就不能被修改，尽管可以删除并添加该元素的修改值。

与Set相关的功能：

begin() ：返回指向集合中第一个元素的迭代器。
end() ：返回指向集合中最后一个元素之后的理论元素的迭代器。
size() ：返回集合中元素的数量。
max_size() ：返回集合可以容纳的最大元素数量。
empty() ：返回集合是否为空。

本文重点介绍C++中std::set::upper_bound和std::upper_bound之间的区别。

C++中的std::upper_bound()

C++中的upper_bound()方法用于返回指向范围[first，last）中第一个大于给定值的元素的迭代器。

C++中的std::set::upper_bound()

set::upper_bound()是C++ STL中的内置函数，它返回指向容器中刚刚大于传递的值“x”的元素的迭代器。如果传递的参数键超过容器中的最大值，则返回的迭代器指向set容器中的最后一个元素。

std::upper_bound() vs std::set::upper_bound()

下面是std::upper_bound()和std::set::upper_bound()之间的一些差异。

序号	std::upper_bound()	std::set::upper_bound()
1	语法 -std::upper_bound（ForwardIterator first，ForwardIterator last，const T& val）。	语法 -std::upper_bound（const value_type& val）。
2	std::upper_bound具有随机访问迭代器和非随机访问迭代器。	std::set::upper_bound优化了双向迭代器。
3	此函数通过随机访问迭代器优化比较次数，这对于随机访问迭代器是有效的。	此函数使用双向迭代器优化比较次数。
4	对于随机访问迭代器，运行时间复杂度为O(log2N)，但对于非随机访问迭代器，它为O(N)。	运行时间复杂度始终为O(log2N)，因为它采用了二叉搜索树实现。

在下面的示例中，我们说明了两个函数所需的CPU执行时间。通常情况下，首选std::set::upper_bound()方法。

示例：std::upper_bound()

下面是用于说明std::upper_bound()函数的C++程序。

// C ++程序，说明
// std :: set :: upper_bound
#include 
#include 
using namespace std;

// 要测量时间的功能
void myFunction()
{
    // 初始化集合
    set s;

    // 在集合中插入元素
    for（int i = 0; i <10; i ++）{
        s.insert(i);
    }

    // 使用upper_bound()函数查找5
    set :: iterator it;
    it = upper_bound（s.begin（），s.end（），5）;
}

// 驱动程序
int main()
{
    // 使用函数 gettimeofday（）
    // 可以获取时间
    struct timeval start， end;

    // 开始计时器
    gettimeofday（＆start，NULL）;

    // 不同步C和C++的I / O。
    ios_base :: sync_with_stdio(false);

    // 函数调用
    myFunction();

    // 停止计时器
    gettimeofday（＆end，NULL）;

    // 计算程序所用的总时间。
    double totalTime;

    totalTime =（end.tv_sec- start.tv_sec）* 1e6;

    totalTime
         =（totalTime +（end.tv_usec- start.tv_usec））
           * 1e-6;

    cout << "程序所用的时间是：" << fixed
         << totalTime << setprecision(6);
    cout << "秒" << endl;
    return 0;
}

输出

程序所用的时间是：0.000056秒

例：std :: set :: upper_bound()

下面是C ++程序，说明std :: set :: upper_bound()函数。

// C ++程序，说明
// std :: upper_bound
#include 
#include 
using namespace std;

// 要测量时间的功能
void myFunction()
{
    // 初始化集合
    set s;

    // 在集合中插入元素
    for（int i = 0; i <10; i ++）{
        s.insert(i);
    }

    // 使用set :: upper_bound()函数查找5
    set :: iterator it;
    it = s.upper_bound(5);
}

// 驱动程序
int main()
{
    // 使用函数 gettimeofday（）
    // 可以获取时间
    struct timeval start， end;

    // 开始计时器
    gettimeofday（＆start，NULL）;

    // 不同步C和C++的I / O。
    ios_base :: sync_with_stdio(false);

    myFunction();

    // 停止计时器
    gettimeofday（＆end，NULL）;

    // 计算程序所用的总时间。
    double totalTime;

    totalTime =（end.tv_sec- start.tv_sec）* 1e6;

    totalTime
         =（totalTime +（end.tv_usec- start.tv_usec））
           * 1e-6;

    cout << "程序所用的时间是：" << fixed
         << totalTime << setprecision(6);
    cout << "秒" << endl;
    return 0;
}

输出