1. 问题引出
今天在查看ORB_SLAM2注释版源码keyframe.cpp文件的时候，发现注释者的意见：
// http://www.cplusplus.com/reference/algorithm/upper_bound/
// 从mvOrderedWeights找出第一个大于w的那个迭代器
// 这里应该使用lower_bound，因为lower_bound是返回小于等于，而upper_bound只能返回第一个大于的
仔细对比发现并没有错，估计注释者并没有深刻理解这个上阙界和下阙界。对lower_bound和upper_bound翻译为这个数学术语是有原因的，同于数学中常用的范围域“ [ ) ”。
2. 彻底明白lower_bound和upper_bound
小伙伴们可能从很多博客看到类似上述注释者这样的指导说明，但是往往让人难以理解，有点扰乱思路、抓狂。很简单的理解方法，数学中“a [ ) ”这串数学符号表示下界“[”小于等于a，上界“）”大于a，在数学中叫做“半开半闭”区间，即左闭右开。
说列这么多，那如何和c++中的vector list等联系起来，把vector/llist的数据看成一条数轴，给定比较值的左边是lower_bound---"["，右边是upper_bound---")"，这两个函数的使用要求vector/list等是排序好的，那是升序还是降序来着？默认情况是升序，降序需要指定。引入数学的理解，相信小伙伴们不会懵逼了，如果会，我也没办法。行上个代码增加一下理解。
3. 代码Code解释
3.1 升序情况
简书不好插入代码，吐槽一下，谁知道可以告诉我。
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
static bool weightComp( int a, int b)
{
return a>b;
}
int main(int argc,char**argv)
{
std::vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(19);
vecInt.push_back(2);
vecInt.push_back(4);
vecInt.push_back(7);
std::sort(vecInt.begin(),vecInt.end());
for(auto itt:vecInt)
{
std::cout<<itt<<endl;
}
std::vector<int>::iterator it=lower_bound(vecInt.begin(),vecInt.end(),4);
std::cout<<"lower bound: "<<*it<<endl;
it=upper_bound(vecInt.begin(),vecInt.end(),4);
std::cout<<"upper bound: "<<*it<<endl;
return 0;
}
输出：(插入图片也不太方便)
3.2 降序情况
降序情况一定要记得指定比较函数
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
static bool weightComp( int a, int b)//指定比较函数，重要事情说3遍
{
return a>b;
}
int main(int argc,char**argv)
{
std::vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(19);
vecInt.push_back(2);
vecInt.push_back(4);
vecInt.push_back(7);
std::sort(vecInt.begin(),vecInt.end(),weightComp);//指定比较函数，重要事情说3遍
for(auto itt:vecInt)
{
std::cout<<itt<<endl;
}
std::vector<int>::iterator it=lower_bound(vecInt.begin(),vecInt.end(),4,weightComp);//指定比较函数，重要事情说3遍
std::cout<<"lower bound: "<<*it<<endl;
it=upper_bound(vecInt.begin(),vecInt.end(),4,weightComp);//指定比较函数，重要事情说3遍
std::cout<<"upper bound: "<<*it<<endl;
return 0;
}
输出：
好了，到了这里小伙伴还有什么不明白的吗？可以联系@我。在次总结一下，a. 使用这两个函数前vector/list等要排序; b. 调用函数时默认是升序，降序记得指定并自己编写比较函数. c. 引入数学半开半闭区间是很好的理解方式。
网友评论