| 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) with values equivalent to val.operator< for the first version, and comp for the second. Two elements, a and b are considered equivalent if (!(a<b) && !(b<a)) or if (!comp(a,b) && !comp(b,a)).operator< or comp), or at least partitioned with respect to val.1
2
3
4
5
6
7
template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it = std::lower_bound (first,last,val);
return std::make_pair ( it, std::upper_bound(it,last,val) );
}[first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.[first,last) as either operand of operator<.bool. The value returned indicates whether the first argument is considered to go before the second.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// equal_range example
// equal_range example
#include <iostream> // std::cout
#include <algorithm> // std::equal_range, std::sort
#include <vector> // std::vector
bool mygreater (int i,int j) { return (i>j); }
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;
// using default comparison:
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
bounds=std::equal_range (v.begin(), v.end(), 20); // ^ ^
// using "mygreater" as comp:
std::sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10
bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); // ^ ^
std::cout << "bounds at positions " << (bounds.first - v.begin());
std::cout << " and " << (bounds.second - v.begin()) << '\n';
return 0;
}bounds at positions 2 and 5
2*log2(N)+1 element comparisons (where N is this distance).[first,last) are accessed.