C++算法 equal_range()函数是二进制搜索的版本。此函数用于返回子参数的下限和上限,该子参数包括与[first,last)参数内的val等效的所有元素。
default (1) template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val); custom (2) template <class ForwardIterator, class T, class Compare> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
first:一个正向迭代器,指向要搜索参数内的第一个元素。
last:前向迭代器,指向要搜索参数内的最后一个最后一个元素。
comp:用户定义的二进制谓词函数,该函数接受两个参数,如果两个参数顺序正确,则返回true,否则返回false。
val :比较参数内元素的上限值。
它返回两个迭代器,一个指向不小于val的第一个元素,另一个指向大于val的第一个元素。
如果找不到这样的元素,则最后返回。
让我们看一个简单的示例来演示equal_range()的用法:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v = {3, 1, 4, 2, 5}; sort(v.begin(), v.end()); auto result = equal_range(v.begin(), v.end(), 3); cout << "Lower Bound of 3 is: "<<*result.first << endl; cout << "Upper Bound of 3 is: "<<*result.second << endl; return 0; }
输出:
Lower Bound of 3 is: 3 Upper Bound of 3 is: 4
让我们看另一个简单的示例,使用operator <来比较元素:
#include <algorithm> #include <vector> #include <iostream> using namespace std; struct S { int number; char name; S ( int number, char name ) : number ( number ), name ( name ) {} //only the number is relevant with this comparison bool operator< ( const S& s ) const { return number < s.number; } }; int main() { //note: not ordered, only partitioned w.r.t. S defined below vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} }; S value ( 2, '?' ); auto p = equal_range(vec.begin(),vec.end(),value); for ( auto i = p.first; i != p.second; ++i ) cout << i->name << ' '; return 0; }
输出:
B C D
在上面的示例中,运算符<用于比较元素并返回等于2的范围内的所有元素。
让我们看另一个使用比较函数比较元素的简单示例:
#include <algorithm> #include <vector> #include <iostream> using namespace std; struct S { int number; char name; S ( int number, char name ) : number ( number ), name ( name ) {} //only the number is relevant with this comparison bool operator< ( const S& s ) const { return number < s.number; } }; struct Comp { bool operator() ( const S& s, int i ) { return s.number < i; } bool operator() ( int i, const S& s ) { return i < s.number; } }; int main() { //note: not ordered, only partitioned w.r.t. S defined below vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} }; auto p = equal_range(vec.begin(),vec.end(),2,Comp()); for ( auto i = p.first; i != p.second; ++i ) cout << i->name << ' '; return 0; }
输出:
B C D
让我们看另一个简单的例子:
#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)<<" "; pair<vector<int>::iterator, vector<int>::iterator> bounds; bounds = equal_range(v.begin(), v.end(), 3); if (bounds.first != v.end()) cout <<"\nLower bound of 3 in v = "<<*bounds.first; if (bounds.first != v.end()) cout <<"\nUpper bound of 3 in v = "<<*bounds.second; bounds = equal_range(v.begin(), v.end(), 4); if (bounds.first != v.end()) cout <<"\nLower bound of 4 in v = "<<*bounds.first; if (bounds.first != v.end()) cout <<"\nUpper bound of 4 in v = "<<*bounds.second; bounds = equal_range(v.begin(), v.end(), 5); if (bounds.first != v.end()) cout <<"\nLower bound of 5 in v = "<<*bounds.first; if (bounds.first != v.end()) cout <<"\nUpper bound of 5 in v = "<<*bounds.second; bounds = equal_range(v.begin(), v.end(), 7); if (bounds.first != v.end()) cout <<"\nLower bound of 7 in v = "<<*bounds.first; cout <<"\nThis is the first of the three 7's, since the value " "before this 7 is "<<*(bounds.first-1)<<"."; if (bounds.first != v.end()) cout <<"\nUpper bound of 7 in v = "<<*bounds.second; bounds = equal_range(v.begin(), v.end(), 0); if (bounds.first != v.end()) cout <<"\nLower bound of 0 in v = "<<*bounds.first; if (bounds.first != v.end()) cout <<"\nUpper bound of 0 in v = "<<*bounds.second; bounds = equal_range(v.begin(), v.end(), 15); if (bounds.first != v.end()) cout <<"\nLower bound of 15 in v = "<<*bounds.first; if (bounds.first != v.end()) cout <<"\nUpper bound of 15 in v = "<<*bounds.second; cout <<"\nNote that both the lower and upper bound locations " "\nof 15 are the 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 Lower bound of 3 in v = 3 Upper bound of 3 in v = 5 Lower bound of 4 in v = 5 Upper bound of 4 in v = 5 Lower bound of 5 in v = 5 Upper bound of 5 in v = 6 Lower bound of 7 in v = 7 This is the first of the three 7's, since the value before this 7 is 6. Upper bound of 7 in v = 8 Lower bound of 0 in v = 2 Upper bound of 0 in v = 2 Note that both the lower and upper bound locations of 15 are the end (one-past-the-last) vector position.
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)