C++ equal_range()
C++算法equal_range()
C++算法 equal_range()函数是二进制搜索的版本。此函数用于返回子范围的下限和上限，该子范围包括与[first，last)范围内的val等效的所有元素。
其中子范围是由两个迭代器定义的，一个指向不小于val的第一个元素，另一个指向大于val的第一个元素。
第一个版本使用运算符
<来比较元素，第二个版本使用给定的比较函数，即comp。< span>
为了与val比较，必须对范围[first，last)进行分区，即，它必须满足以下所有条件: 相对于元素 val或comp(element，val)进行了分区 针对!(val < element)或!comp(val，element)进行了分区 对于所有元素，如果element < val或comp(element，val)为true，则!(val < element)或!comp(val，element)也为true。
语法
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。
如果找不到此类元素，则最后返回。
复杂度
平均而言，复杂度在对数中是对数的首尾之间的距离: 最多进行2 * log2(N)+ 1个元素比较，其中N =尾数-首尾。
数据竞争
范围[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;
}
输出:
在上面的示例中，运算符
<用于比较元素并返回等于2的范围内的所有元素。< div>
示例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;
}
输出:
示例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.
