c++stl之lower_bound,upper_bound和equal_range函数的详细介绍!!!
C++ 函数 介绍 详细 STL range Bound equal
2023-09-14 09:13:36 时间
lower_bound,upper_bound和equal_range函数初识
lower_bound.(k) | 返回一个迭代器,指向第一个值不小于k的元素 |
upper_bound(k) | 返回一个迭代器,指向第一个值大于k的元素 |
equal_range(k) | 返回一个迭代器pair,表示值等于k的元素的范围。若k不存在,pair两个成员均等于end()–尾迭代器 |
- 上面三个函数多用于容器中使用,但是对于普通的数组也是可以使用的,下面会讲到.
- 如果所查找值在容器中,lower_bound返回的迭代器将指向第一个具有给定值的元素,而upper_bound返回的迭代器指向最后一个匹配给定值的元素之后的位置。
- 如果元素不在容器中,则lower_bound和upper_bound会返回相等的迭代器----指向一个不影响排序的值插入位置
- 因此,用相同的值调用lower_bound和upper_bound会得到一个迭代器的范围,表示具有该关键字的元素范围。
- 当然,这两个操作返回的迭代器可能是容器的尾后迭代器。如果我们查找的元素具有容器中最大值,则此关键字的upper_bound返回尾后迭代器。如果关键字不存在,且大于容器中任何关键字,则lower_bound返回的也是尾后迭代器.
注意事项
- lower_bound返回的迭代器可能指向一个具有给定值的元素,但也可能不指向。
- 如果关键字不在容器中,则lower_bound会返回关键字的第一个安全插入点—不影响容器中元素顺序的插入位置
- 如果lower_bound和upper_bound返回相同的迭代器,则给定的关键字不在容器中.
具体使用说明
- 1.与map容器结合使用,打印map容器中作者英文名字对应为Tom的所有出版书籍.
void test()
{
//注意map容器不能插入重复关键字
map<string, string> author = {
{"Jerry","Jerry's travel"},
{"Boboy","Star Star Star"},
{"Tom","I Love Mouse"},
};
for (auto beg = author.lower_bound("Tom"), end = author.upper_bound("Tom"); beg != end; beg++)
cout << beg->second << endl;
}
- 2.与vector结合使用,打印vector数组中大于等于5的元素范围
//这里数组v最好是有序的
vector<int> v = { 1,2,3,4,5,6,7,8 };
for (auto beg = lower_bound(v.begin(), v.end(),5); beg != v.end(); beg++)
cout << *beg <<" " <<ends;
cout << endl;
注意:数组最好是有序的,不然打印范围是错误的
- 3,在vector数组中查找存在的元素2
注意:数组必须是有序的,不然查找结果会出错
//这里数组v最好是有序的
vector<int> v = { 1,2,3,4,5,6,7,8};
auto beg = lower_bound(v.begin(), v.end(), 5), end = upper_bound(v.begin(), v.end(), 5);
cout << *beg <<" " <<ends;
cout << endl<<*end << endl;
cout << endl;
注意观察这里beg和end查找到的对应值区别,beg从前往后找到第一个大于等于对应值的元素,而end从后往前查找第一个大于对应值的元素。
- 4,在vector数组中查找不存在的元素
1.如果查找的不存在元素是4
//这里数组v最好是有序的
vector<int> v = { 1,2,3,5,6,7,8};
auto beg = lower_bound(v.begin(), v.end(), 4), end = upper_bound(v.begin(), v.end(), 4);
if (beg == v.end())
cout << "beg此时指向尾迭代器" << endl;
else
cout << *beg << endl;
if (end == v.end())
cout << "end此时指向尾迭代器" << endl;
cout << *end << endl;
cout << endl;
2.如果查找的不存在元素是8
3.如果查找的不存在元素是10
- 4,利用equal_range函数打印map容器中所有关键字为2的元素
void test()
{
multimap<int, int> map = {
{1,0},
{1,520},
{2,4},
{2,3},
{2,6},
{4,5},
{7,8},
{10,22},
};
for (auto beg = map.lower_bound(2), end = map.upper_bound(2); beg!= end; beg++)
cout << beg->second << endl;
}
equal_range函数使用注意事项
-
此函数接受一个关键字,返回一个迭代器pair。
-
若关键字存在,则第一个迭代器指向第一个与关键字匹配的元素,第二个迭代器指向最后一个与关键字匹配的元素之后的位置。
-
若未找到匹配元素,则两个迭代器都指向关键字可以插入的位置.
-
其实equal_range返回的pair,此pair的first成员保存的迭代器与lower_bound返回的迭代器是一样的,second保存的迭代器与upper_bound的返回值是一样的。
高级用法
这里先介绍一种高级用法,用lower_bound来简化二分查找算法的写法:
- 这里顺便也补上lower_bound函数与普通数组结合使用的案例
bool BS(int* arr,int val)
{
auto pos=lower_bound(arr, arr + 8, val);
if (*pos== val)
return true;
return false;
}
int main()
{
int arr[8] = { 1,2,3,4,5,6,7,8 };
cout << "查找指定元素4是否在数组中" << endl;
if (BS(arr, 4))
cout << "查找到指定元素" << endl;
else
cout << "没有此元素" << endl;
return 0;
}
相关文章
- C++面向对象程序设计_面向对象程序设计的基本机制是
- C++学习之路——函数重载和运算符重载
- C++ stl_stl函数
- C++系列笔记(四)
- EasyC++39,函数模板
- C++中voliate关键字
- C++栈的基本操作及原理和STL函数
- c++ auto类型_auto C++
- pybind11 大大简化 Python 调用 C/C++
- C++——拷贝构造和 运算符重载
- c++ primer读书笔记
- 【C 语言】文件操作 ( 文件加密解密 | 使用第三方 DES 加密解密库 | 头文件导入 | 兼容 C++ 语言 | 加密解密函数说明 )
- C++ 夺冠!成为 TIOBE 2022 年度编程语言
- 【C++】通过priority_queue、reverse_iterator加深对于适配器和仿函数的理解
- 校招找C++后台开发该准备什么样的项目比较好呢?
- C++静态成员变量和静态成员函数详解
- C++函数重载完全攻略(无师自通)
- C++ while(do-while)循环详解
- C语言/C++字符编码方式解析
- C++ STL无序容器自定义哈希函数和比较规则(超级详细)
- 从C/C++迁移到PHP——判断字符类型的函数
- C++中delete和delete[]的区别说明
- 基于c++中的默认拷贝函数的使用详解
- 深入C++四种强制类型转换的总结
- c++利用windows函数实现计时示例