std::equal_range
Defined in header <algorithm> | ? | ? |
|---|---|---|
template< class ForwardIt, class T > std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value ); | (1) | ? |
template< class ForwardIt, class T, class Compare > std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (2) | ? |
返回包含所有元素的范围，这些元素相当于value在范围内[first, last)...
范围[first, last)的比较，则必须对其进行分区。value，即必须满足下列所有要求：
- 的分区
element < value或comp(element, value)
- 的分区
!(value < element)或!comp(value, element)
- 对于所有元素，如果
element < value或comp(element, value)是true然后!(value < element)或!comp(value, element)也是true
完全排序的范围符合这些条件，调用std::partition...
返回的范围由两个迭代器定义，一个指向第一个元素，即不折不扣比value另一个指向第一个元素更大比value.第一迭代器可与std::lower_bound()，第二个std::upper_bound()...
第一个版本使用operator<为了比较元素，第二个版本使用给定的比较函数。comp...
参数
first, last | - | the range of elements to examine | |||
|---|---|---|---|---|---|
value | - | value to compare the elements to | |||
comp | - | comparison function which returns ?true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function must not modify the objects passed to it. cmp will be called as both cmp(value, *iterator) and cmp(*iterator, value). | bool cmp(const Type1 &a, const Type2 &b); | ? | ? |
bool cmp(const Type1 &a, const Type2 &b); | ? | ? |
类型要求
---。
返回值
std::pair包含一对迭代器，定义所需范围，第一个迭代器指向第一个元素，即不折不扣比value第二个指向第一个元素更大比value...
如果没有元素不折不扣比value，，，last作为第一个元素返回。类似地，如果没有元素更大比value，，，last作为第二个元素返回。
复杂性
执行的比较数为对数，其距离为first和last%28，最多2%2A原木
2%28最后-首%29+O%281%29比较%29。但是，对于非-RandomAccessIterator斯，迭代器增量的数目是线性的。
可能的实施
第一版
*。
模板<类向前，类T>std：：对<前进，向前>相等[医]范围%28 Forwardit First，Forwardit Lest，Const T&value%29{返回std：：make[医]对%28 std：：较低[医]界%281，最后，值%29，std：：上限[医]绑定%281，最后，值%29%29；}
第二版
模板<类向前，类T，类比较>std：：对<前进，向前>相等[医]范围%28前进第一，前进最后，控制T&值，比较comp%29；{返回std：：make[医]对%28 std：：较低[医]界%281，最后，值，comp%29，std：：上限[医]界%281，最后，值，comp%29%29；}
例
二次
#include <algorithm>
#include <vector>
#include <iostream>
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
std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };
S value ( 2, '?' );
auto p = std::equal_range(vec.begin(),vec.end(),value);
for ( auto i = p.first; i != p.second; ++i )
std::cout << i->name << ' ';
}二次
产出：
二次
B C D二次
用比较器举例
二次
#include <algorithm>
#include <vector>
#include <iostream>
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
std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };
auto p = std::equal_range(vec.begin(),vec.end(),2,Comp());
for ( auto i = p.first; i != p.second; ++i )
std::cout << i->name << ' ';
}二次
产出：
二次
B C D二次
另见
lower_bound | returns an iterator to the first element not less than the given value (function template) |
|---|---|
upper_bound | returns an iterator to the first element greater than a certain value (function template) |
binary_search | determines if an element exists in a certain range (function template) |
partition | divides a range of elements into two groups (function template) |
? cppreference.com在CreativeCommonsAttribution下授权-ShareAlike未移植许可v3.0。
本文档系腾讯云开发者社区成员共同维护，如有问题请联系 cloudcommunity@tencent.com
