21xrx.com
2024-12-23 00:47:53 Monday
登录
文章检索 我的文章 写文章
C++中的lower_bound和upper_bound函数
2023-07-05 22:10:01 深夜i     --     --
C++ lower_bound upper_bound 函数 查找

C++中的lower_bound和upper_bound函数是用来在有序容器中查找特定元素的函数。这两个函数都是在algorithm头文件中定义的。

lower_bound函数用于查找第一个不小于给定值的元素,它的原型如下:


template <class ForwardIterator, class T>

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

其中,first和last分别是要查找的序列的起点和终点,value是要查找的值。

例如,我们有一个vector容器v,它内部有以下元素:1, 2, 3, 4, 4, 5, 6。如果我们要查找第一个不小于4的元素,可以这样写:


auto iter = lower_bound(v.begin(), v.end(), 4);

函数的返回值iter是一个指向容器中第一个值不小于4的元素的迭代器。在这个例子中,iter指向的是容器中的第四个元素(值为4)。

如果在容器中没有大于等于给定值的元素,lower_bound函数返回last。

我们也可以自定义比较函数来进行比较。这时候需要在函数调用的时候传入自定义的比较函数作为第三个参数。比较函数需要满足严格弱序(Strict Weak Ordering)的定义。

upper_bound函数与lower_bound函数类似,它用于查找第一个大于给定值的元素。其原型如下:


template <class ForwardIterator, class T>

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

例如,我们用上一个例子的vector容器v,如果要查找第一个大于4的元素,可以这样写:


auto iter = upper_bound(v.begin(), v.end(), 4);

函数的返回值iter是一个指向容器中第一个值大于4的元素的迭代器。在这个例子中,iter指向的是容器中的第六个元素(值为5)。

如果在容器中没有大于给定值的元素,upper_bound函数返回last。

由于lower_bound和upper_bound函数都只适用于有序容器,所以在使用这两个函数之前,一定要确保容器中的元素已经按照从小到大的顺序排好。如果容器是无序的,那么这两个函数的寻找结果可能是不准确的。

总的来说,C++中的lower_bound和upper_bound函数是非常实用的函数,能够提高程序的查找效率。在实际编程中,需要根据具体情况选择使用哪个函数,以达到最佳的效果。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复