Reference
C Library
IOstream Library
Strings library
STL Containers
STL Algorithms
Miscellaneous
STL Algorithms
algorithm:
adjacent_find
binary_search
copy
copy_backward
count
count_if
equal
equal_range
fill
fill_n
find
find_end
find_first_of
find_if
for_each
generate
generate_n
includes
inplace_merge
iter_swap
lexicographical_compare
lower_bound
make_heap
max
max_element
merge
min
min_element
mismatch
next_permutation
nth_element
partial_sort
partial_sort_copy
partition
pop_heap
prev_permutation
push_heap
random_shuffle
remove
remove_copy
remove_copy_if
remove_if
replace
replace_copy
replace_copy_if
replace_if
reverse
reverse_copy
rotate
rotate_copy
search
search_n
set_difference
set_intersection
set_symmetric_difference
set_union
sort
sort_heap
stable_partition
stable_sort
swap
swap_ranges
transform
unique
unique_copy
upper_bound


equal_range

function template
<algorithm> 
template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value );

template <class ForwardIterator, class T, class Compare>
  pair<ForwardIterator,ForwardIterator>
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value,
                  Compare comp );

Get subrange of equal elements

Returns the bounds of the largest subrange that includes all the elements of the [first,last) with values equivalent to value.

The comparison is performed using either operator< for the first version, or comp for the second: A value, a, is considered equivalent to another, b, when (!(a<b) && !(b<a)) or (!comp(a,b) && !comp(b,a))
If value is not equivalent to any value in the range, the subrange returned has a length of zero, with both iterators pointing to the nearest value greater than value, if any, or to last, if value compares greater than all the elements in the range.

For the function to yield the expected result, the elements in the range shall already be ordered according to the same criterion (operator< or comp).

The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
 
template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value )
{
  ForwardIterator it = lower_bound (first,last,value);
  return make_pair ( it, upper_bound(it,last,value) );
}


Parameters

first, last
Forward iterators to the initial and final positions of the sequence to use. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
value
Element value to be checked for its bounds.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value

Iterator to the upper bound position for value in the range.

A pair, where its member pair::first is an iterator to the lower bound of the subrange of equivalent values, and pair::second its upper bound. The values are the same as those that would be returned by functions lower_bound and upper_bound respectively.

Example

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mygreater (int i,int j) { return (i>j); }
int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  pair<vector<int>::iterator,vector<int>::iterator> bounds;
  // using default comparison:
  sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
  bounds=equal_range (v.begin(), v.end(), 20);            //          ^        ^
  // using "mygreater" as comp:
  sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=equal_range (v.begin(), v.end(), 20, mygreater); //       ^        ^
  cout << "bounds at positions " << int(bounds.first - v.begin());
  cout << " and " << int(bounds.second - v.begin()) << endl;
  return 0;
}


Output:
bounds at positions 2 and 5

Complexity

At most, twice logarithmic number of comparisons and linear number of steps in the length of [first,last).
If used with random-access iterators, number of steps is reduced to twice logarithmic.

See also

lower_bound Return iterator to lower bound (function template)
upper_bound Return iterator to upper bound (function template)
binary_search Test if value exists in sorted array (function template)