又是兩個黑科技一般的存在。

首先我們來介紹一下這兩個函數(shù)：

?

ForwardIter?lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)

返回一個非遞減序列[first, last)中的第一個大于等于值val的位置。

?

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)

返回一個非遞減序列[first, last)中第一個大于val的位置。

?

如圖：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

兩種函數(shù)均采用了二分的方法。

?

注意：

函數(shù)調(diào)用序列必須有序。

upper_bound()和lower_bound()的返回值都是迭代器的位置，不能直接與int等類型進(jìn)行賦值。

?

?

std::lower_bound：

default (1)

template <class ForwardIterator, class T>ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val);

custom (2)

template <class ForwardIterator, class T, class Compare>ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

作用：

返回一個非遞減序列[first, last)中的第一個大于等于值val的位置。

?

源代碼為：

1 template <class ForwardIterator, class T> 2 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val) 3 { 4 ForwardIterator it; 5 iterator_traits<ForwardIterator>::difference_type count, step; 6 count = distance(first,last); 7 while (count>0) 8 { 9 it = first; step=count/2; advance (it,step); 10 if (*it<val) { // or: if (comp(*it,val)), for version (2) 11 first=++it; 12 count-=step+1; 13 } 14 else count=step; 15 } 16 return first; 17 }

?

Example：

1 // lower_bound/upper_bound example 2 #include <iostream> // std::cout 3 #include <algorithm> // std::lower_bound, std::upper_bound, std::sort 4 #include <vector> // std::vector 5 6 int main () { 7 int myints[] = {10,20,30,30,20,10,10,20}; 8 std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 9 10 std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 11 12 std::vector<int>::iterator low,up; 13 low=std::lower_bound (v.begin(), v.end(), 20); // ^ 14 up= std::upper_bound (v.begin(), v.end(), 20); // ^ 15 16 std::cout << "lower_bound at position " << (low- v.begin()) << '\n'; 17 std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; 18 19 return 0; 20 }

?

Output:

lower_bound at position 3 upper_bound at position 6

?

資料參考：

http://www.cplusplus.com/reference/algorithm/lower_bound/

?

std::upper_bound：

default (1)custom (2)

template <class ForwardIterator, class T>ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val);

template <class ForwardIterator, class T, class Compare>ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

作用：

返回一個非遞減序列[first, last)中第一個大于val的位置。

?

源代碼為：

1 template <class ForwardIterator, class T> 2 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val) 3 { 4 ForwardIterator it; 5 iterator_traits<ForwardIterator>::difference_type count, step; 6 count = std::distance(first,last); 7 while (count>0) 8 { 9 it = first; step=count/2; std::advance (it,step); 10 if (!(val<*it)) // or: if (!comp(val,*it)), for version (2) 11 { first=++it; count-=step+1; } 12 else count=step; 13 } 14 return first; 15 }

?

Example：

1 // lower_bound/upper_bound example 2 #include <iostream> // std::cout 3 #include <algorithm> // std::lower_bound, std::upper_bound, std::sort 4 #include <vector> // std::vector 5 6 int main () { 7 int myints[] = {10,20,30,30,20,10,10,20}; 8 std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 9 10 std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 11 12 std::vector<int>::iterator low,up; 13 low=std::lower_bound (v.begin(), v.end(), 20); // ^ 14 up= std::upper_bound (v.begin(), v.end(), 20); // ^ 15 16 std::cout << "lower_bound at position " << (low- v.begin()) << '\n'; 17 std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; 18 19 return 0; 20 }

?

Output:

lower_bound at position 3 upper_bound at position 6

?

資料參考：

http://www.cplusplus.com/reference/algorithm/upper_bound/

?

附一道簡單例題：

Interesting drink

轉(zhuǎn)載于:https://www.cnblogs.com/Kiven5197/p/5767583.html

總結(jié)

以上是生活随笔為你收集整理的STL--lower_bound()upper_bound();的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。