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

C++中的std::lower_bound：

在C++中，lower_bound()方法用于返回一个迭代器，该迭代器指向指定范围内第一个值不小于给定值的元素。这意味着该函数返回比该数字稍大的下一个最小数字的索引。

C++中的std::set::lower_bound：

std::set::lower_bound()是C++ STL中的内置函数，它返回指向容器中等于参数传递的 K 的元素的迭代器。如果在 set 容器中不存在K，则该函数返回一个指向接下来一个刚好大于 K 的元素的迭代器。如果在参数中传递的键超过了容器中的最大值，则迭代器返回指向set容器中的最后一个元素。

下面是 std::lower_bound 和 std::set::lower_bound 之间的区别：

序号	std::lower_bound()	std::set::lower_bound()
1	语法：std::lower_bound(ForwardIterator first, ForwardIterator last, const T& val)。	语法：std::lower_bound(const value_type& val)。
2	std::lower_bound具有随机访问迭代器和非随机访问迭代器。	std::set::lower_bound具有双向迭代器。
3	该函数通过使用随机访问迭代器优化比较的次数，这对于随机访问迭代器是有效的。	该函数使用双向迭代器优化比较的次数。
4	对于随机访问迭代器，其运行时间复杂度为 O(log 2 N)，但对于非随机访问迭代器，其运行时间复杂度为 O(N)。	由于其二叉查找树的实现方式，其运行时间复杂度始终为 O(log 2 N)。

下面是 CPU 执行时间的程序，用于说明这两个函数的运行时间。

讲解std::lower_bound()的程序：

// C++ program to illustrate
// std::set::lower_bound
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
  
// Function whose time is to
// be measured
void fun()
{
    // Initialise the set
    set<int> s;
  
    // Insert element in the set
    for (int i = 0; i < 10; i++) {
        s.insert(i);
    }
  
    // Use lower_bound() function
    // to find 5
    set<int>::iterator it;
    it = lower_bound(s.begin(), s.end(), 5);
}
  
// Driver Code
int main()
{
    // Use function gettimeofday()
    // can get the time
    struct timeval start, end;
  
    // Start timer
    gettimeofday(&start, NULL);
  
    // unsync the I/O of C and C++.
    ios_base::sync_with_stdio(false);
  
    // Function Call
    fun();
  
    // Stop timer
    gettimeofday(&end, NULL);
  
    // Calculating total time taken
    // by the program.
    double time_taken;
  
    time_taken = (end.tv_sec
                  - start.tv_sec)
                 * 1e6;
  
    time_taken = (time_taken
                  + (end.tv_usec
                     - start.tv_usec))
                 * 1e-6;
  
    cout << "程序执行时间为："
         << fixed
         << time_taken << setprecision(6);
    cout << " 秒" << endl;
    return 0;
}

程序所耗时间为：0.000046秒

演示 std::set::lower_bound() 的程序：

//C++程序演示
//std::lower_bound
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

//要测量时间的函数
void fun()
{
    //初始化集合
    set<int> s;

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

    //使用set::lower_bound()函数查找5
    set<int>::iterator it;
    it = s.lower_bound(5);
}

//主函数
int main()
{
    //使用gettimeofday()函数计算时间
    struct timeval start, end;

    //开始计时
    gettimeofday(&start, NULL);

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

    fun();

    //停止计时
    gettimeofday(&end, NULL);

    //计算程序所用总时间
    double time_taken;

    time_taken = (end.tv_sec
                  - start.tv_sec)
                  * 1e6;

    time_taken = (time_taken
                  + (end.tv_usec
                     - start.tv_usec))
                  * 1e-6;

    cout << "程序所耗时间为："
         << fixed
         << time_taken << setprecision(6);
    cout << "秒" << endl;
    return 0;
}