极客笔记C++ 算法 equal_range()函数
C++算法 equal_range() 函数是二分搜索的版本。此函数用于返回包括范围[first, last)中所有与val等效的元素的下界和上界。
子范围由两个迭代器定义，一个指向第一个不小于val的元素，另一个指向第一个大于val的元素。
- 第一个版本使用运算符<来比较元素，第二个版本使用给定的比较函数comp。
- 范围[first, last)必须根据与val的比较进行分区，即必须满足以下所有条件：
- 根据元素<val或comp(element, val)进行分区
- 根据!(val<element)或!comp(val, element)进行分区
- 对于所有元素，如果element<val或comp(element, val)为真，则!(val<element)或!comp(val, element)也为真。
语法
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的元素。
如果没有找到这样的元素，则返回last。
复杂度
平均而言，复杂度在first和last之间的距离上是对数级别的：执行最多2 * log2（N）+ 1次元素比较，其中N = last – first。
数据竞争
访问范围内的对象[first，last）。
异常
如果元素比较或迭代器操作引发异常，则此函数会引发异常。
请注意，无效的参数会导致未定义行为。
示例1
让我们看一个简单的示例来演示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
示例2
让我们看看另一个简单的示例，使用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的元素。
示例3
让我们看一个简单的示例，使用比较函数来比较元素：
#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
示例4
让我们看看另一个简单的示例：
#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.