1.? 問題引出
? ? 今天在查看ORB_SLAM2注釋版源碼keyframe.cpp文件的時(shí)候，發(fā)現(xiàn)注釋者的意見：
// http://www.cplusplus.com/reference/algorithm/upper_bound/
// 從mvOrderedWeights找出第一個(gè)大于w的那個(gè)迭代器
// 這里應(yīng)該使用lower_bound，因?yàn)閘ower_bound是返回小于等于，而upper_bound只能返回第一個(gè)大于的
仔細(xì)對(duì)比發(fā)現(xiàn)并沒有錯(cuò)，估計(jì)注釋者并沒有深刻理解這個(gè)上闕界和下闕界。對(duì)lower_bound和upper_bound翻譯為這個(gè)數(shù)學(xué)術(shù)語是有原因的，同于數(shù)學(xué)中常用的范圍域“ [? ) ”。
2. 徹底明白lower_bound和upper_bound
????小伙伴們可能從很多博客看到類似上述注釋者這樣的指導(dǎo)說明，但是往往讓人難以理解，有點(diǎn)擾亂思路、抓狂。很簡(jiǎn)單的理解方法，數(shù)學(xué)中“a [? ) ”這串?dāng)?shù)學(xué)符號(hào)表示下界“[”小于等于a，上界“）”大于a，在數(shù)學(xué)中叫做“半開半閉”區(qū)間，即左閉右開。
? ? 說列這么多，那如何和c++中的vector list等聯(lián)系起來，把vector/llist的數(shù)據(jù)看成一條數(shù)軸，給定比較值的左邊是lower_bound---"["，右邊是upper_bound---")"，這兩個(gè)函數(shù)的使用要求vector/list等是排序好的，那是升序還是降序來著？默認(rèn)情況是升序，降序需要指定。引入數(shù)學(xué)的理解，相信小伙伴們不會(huì)懵逼了，如果會(huì)，我也沒辦法。行上個(gè)代碼增加一下理解。
3. 代碼Code解釋
3.1 升序情況
????簡(jiǎn)書不好插入代碼，吐槽一下，誰知道可以告訴我。
#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 降序情況
? ? 降序情況一定要記得指定比較函數(shù)
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
static bool weightComp( int a, int b)//指定比較函數(shù)，重要事情說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);//指定比較函數(shù)，重要事情說3遍
? ? for(auto itt:vecInt)
? ? {
? ? ? ? std::cout<<itt<<endl;
? ? }
? ? std::vector<int>::iterator it=lower_bound(vecInt.begin(),vecInt.end(),4,weightComp);//指定比較函數(shù)，重要事情說3遍
? ? std::cout<<"lower bound: "<<*it<<endl;
? ? it=upper_bound(vecInt.begin(),vecInt.end(),4,weightComp);//指定比較函數(shù)，重要事情說3遍
? ? std::cout<<"upper bound: "<<*it<<endl;
? ? return 0;
}
輸出：
????好了，到了這里小伙伴還有什么不明白的嗎？可以聯(lián)系@我。在次總結(jié)一下，a. 使用這兩個(gè)函數(shù)前vector/list等要排序; b. 調(diào)用函數(shù)時(shí)默認(rèn)是升序，降序記得指定并自己編寫比較函數(shù). c. 引入數(shù)學(xué)半開半閉區(qū)間是很好的理解方式。
