C++中lower_bound和upper_bound的用法
时间: 2024-06-16 10:06:17 浏览: 22
在C++中,`lower_bound`和`upper_bound是两个用于查找有序容器中元素位置的函数。
1. `lower_bound`函数用于查第一个大于或等于给定值的元素的位置。它接受两个参数:容器的起始迭代器和要查找的值。返回值是一个迭代器,指向第一个大于或等于给定值的元素位置。如果容器中不存在大于或等于给定值的元素,则返回指向容器末尾的迭代器。
2. `upper_bound`函数用于查找第一个大于给定值的元素的位置。它接受两个参数:容器的起始迭代器和要查找的值。返回值是一个迭代器,指向第一个大于给定值的元素位置。如果容器中不存在大于给定值的元素,则返回指向容器末尾的迭代器。
这两个函数通常用于有序容器(如vector、set、map)中进行二分查找。它们的时间复杂度为O(log n),其中n是容器中元素的个数。
相关问题
c++ lower_bound和upper_bound
lower_bound和upper_bound都是C++标准库中的算法函数,用于在有序序列中查找某个值的下界和上界。
lower_bound函数接受两个参数:第一个参数是指向有序序列的起始位置的迭代器,第二个参数是要查找的值。它返回一个迭代器,指向序列中第一个大于或等于给定值的元素。如果所有元素都小于给定值,则返回指向序列尾部的迭代器。
upper_bound函数也接受两个参数,与lower_bound函数类似。它返回一个迭代器,指向序列中第一个大于给定值的元素。换句话说,upper_bound返回的迭代器指向的元素是大于给定值的最小元素。如果所有元素都小于或等于给定值,则返回指向序列尾部的迭代器。
这两个函数通常用于有序序列中进行二分查找。可以根据返回的迭代器判断是否找到了目标值,以及得到目标值在序列中的位置或范围。
注意:lower_bound和upper_bound函数要求序列是有序的,否则结果将不确定。
set中的lower_bound和upper_bound
set中的lower_bound和upper_bound是两个函数,它们都用于在有序集合中查找元素。其中,lower_bound函数返回一个迭代器,指向第一个不小于给定值的元素,而upper_bound函数返回一个迭代器,指向第一个大于给定值的元素。如果给定值在集合中不存在,那么lower_bound和upper_bound函数都返回一个指向第一个大于给定值的元素的迭代器。
以下是一个使用lower_bound和upper_bound函数的例子:
假设我们有一个set s,其中包含以下元素:{1, 2, 4, 5, 7}。现在我们想要查找集合中第一个不小于3的元素和第一个大于3的元素,可以使用lower_bound和upper_bound函数来实现:
```C++
#include <iostream>
#include <set>
int main() {
std::set<int> s = {1, 2, 4, 5, 7};
auto it1 = s.lower_bound(3);
auto it2 = s.upper_bound(3);
std::cout << "lower_bound(3) = " << *it1 << std::endl; // 输出:lower_bound(3) = 4
std::cout << "upper_bound(3) = " << *it2 << std::endl; // 输出:upper_bound(3) = 4
return 0;
}
```
在上面的例子中,lower_bound(3)返回一个指向4的迭代器,因为4是集合中第一个不小于3的元素。而upper_bound(3)也返回一个指向4的迭代器,因为4是集合中第一个大于3的元素。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)