C++算法 upper_bound()函数是二进制搜索的版本。此函数用于返回一个迭代器,该迭代器指向[first,last)参数内大于指定值val的第一个元素。
default (1) template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val); custom (2) template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
first:一个正向迭代器,指向要搜索参数内的第一个元素。
last:前向迭代器,指向要搜索参数内的最后一个最后一个元素。
comp :用户定义的二进制谓词函数,该函数接受两个参数,如果两个参数按顺序排列,则返回true,否则返回false。
val :比较参数内元素的上限值。
它返回一个指向参数内第一个大于val的元素的迭代器,如果找不到该元素,则返回last。
让我们看一个简单的例子来演示upper_bound()的用法:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v = {3, 1, 4, 6, 5}; decltype(v)::iterator it = upper_bound(v.begin(), v.end(), 3); cout<<"Upper bound of 3 is: "; cout << *it << endl; return 0; }
输出:
Upper bound of 3 is: 4
让我们看另一个简单的例子:
#include <iostream> //std::cout #include <algorithm> //std::lower_bound, std::upper_bound, std::sort #include <vector> //std::vector using namespace std; int main () { int myints[] = {10,20,30,30,20,10,10,20}; vector<int> v(myints,myints+8); //10 20 30 30 20 10 10 20 sort (v.begin(), v.end()); //10 10 10 20 20 20 30 30 vector<int>::iterator low,up; low=lower_bound (v.begin(), v.end(), 20);// ^ up= upper_bound (v.begin(), v.end(), 20);// ^ cout << "lower_bound at position " << (low- v.begin()) << '\n'; cout << "upper_bound at position " << (up - v.begin()) << '\n'; return 0; }
输出:
lower_bound at position 3 upper_bound at position 6
让我们看另一个简单的例子:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a[] = {2, 3, 5, 6, 7, 7, 7, 8, 9, 10}; vector<int> v(a, a+10); cout <<"\nHere are the contents of v:\n"; for (vector<int>::size_type i=0; i<v.size(); i++) cout <<v.at(i)<<" "; vector<int>::iterator upper; upper = upper_bound(v.begin(), v.end(), 3); if (upper != v.end()) cout <<"\nUpper bound of 3 in v = "<<*upper; upper = upper_bound(v.begin(), v.end(), 4); if (upper != v.end()) cout <<"\nUpper bound of 4 in v = "<<*upper; upper = upper_bound(v.begin(), v.end(), 5); if (upper != v.end()) cout <<"\nUpper bound of 5 in v = "<<*upper; upper = upper_bound(v.begin(), v.end(), 7); if (upper != v.end()) cout <<"\nUpper bound of 7 in v = "<<*upper; upper = upper_bound(v.begin(), v.end(), 0); if (upper != v.end()) cout <<"\nUpper bound of 0 in v = "<<*upper; upper = upper_bound(v.begin(), v.end(), 15); if (upper != v.end()) cout <<"\nUpper bound of 15 in v = "<<*upper; cout <<"\n\nNote that the upper bound location of 15 is \nthe end (one-past-the-last) vector position."; return 0; }
输出:
Here are the contents of v: 2 3 5 6 7 7 7 8 9 10 Upper bound of 3 in v = 5 Upper bound of 4 in v = 5 Upper bound of 5 in v = 6 Upper bound of 7 in v = 8 Upper bound of 0 in v = 2 Note that the upper bound location of 15 is the end (one-past-the-last) vector position.
让我们看另一个简单的例子:
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool ignore_case(char a, char b) { return(tolower(a) == tolower(b)); } int main(void) { vector<char> v = {'A', 'b', 'C', 'd', 'E'}; auto it = upper_bound(v.begin(), v.end(), 'C'); cout << "Upper bound of \'C\' is " << *it << endl; it = upper_bound(v.begin(), v.end(), 'C', ignore_case); cout << "Upper bound of \'C\' is " << *it << endl; it = upper_bound(v.begin(), v.end(), 'z', ignore_case); cout << "All elements are less than \'z\'." << endl; return 0; }
输出:
Upper bound of 'C' is d Upper bound of 'C' is C All elements are less than 'z'.
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)