Man Page equal_range.3

```
Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.

```

NAME

```     equal_range

- Find the largest subrange in a collection  into  which  a
given  value  can be inserted without violating the ordering
of the collection.

```

SYNOPSIS

```     #include <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);

```

DESCRIPTION

```     The equal_range algorithm performs a  binary  search  on  an
ordered  container  to determine where the element value can
be inserted without violating the container's ordering.  The
library  includes  two  versions of the algorithm. The first
version uses the less than operator (operator <)  to  search
for the valid insertion range, and assumes that the sequence
was sorted using the less than operator. The second  version
allows you to specify a function object of type Compare, and
assumes that Compare was  the  function  used  to  sort  the
sequence. The function object must be a binary predicate.

equal_range returns a pair  of  iterators,  i  and  j,  that
define  a  range containing elements equivalent to value, in
other words, the first and last valid insertion  points  for
value.  If value is not an element in the container, i and j
are equal. Otherwise, i points  to  the  first  element  not
"less" than value, and j points to the first element greater
than value. In the second version, "less" is defined by  the
comparison object. Formally, equal_range returns a sub-range
[i, j) such that value can be inserted  at  any  iterator  k
within  the  range.  Depending upon the version of the algo-
rithm used, k must satisfy one of the following conditions:
!(*k <  value)  &&  !(value  <  *k)

or

comp(*k,value) == false && comp(value, *k) == false

The range [first,last) is assumed to be sorted. Type T  must
be LessThanComparable.

```

COMPLEXITY

```     equal_range performs at most 2 * log(last - first) + 1  com-
parisons.

```

EXAMPLE

```     //
// eqlrange.cpp
//
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
int main()
{
typedef vector<int>::iterator iterator;
int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};
//
// Set up a vector
//
vector<int> v1(d1+0, d1 + 11);
//
// Try equal_range variants
//
pair<iterator,iterator> p1 =
equal_range(v1.begin(),v1.end(),3);
// p1 = (v1.begin() + 4,v1.begin() + 5)
pair<iterator,iterator> p2 =
equal_range(v1.begin(),v1.end(),2,less<int>());
// p2 = (v1.begin() + 4,v1.begin() + 5)
// Output results
cout << endl  << "The equal range for 3 is: "
<< "( " << *p1.first << " , "
<< *p1.second << " ) " << endl << endl;
cout << endl << "The equal range for 2 is: "
<< "( " << *p2.first << " , "
<< *p2.second << " ) " << endl;

return 0;
}

Program Output

The equal range for 3 is: ( 3 , 4 )
The equal range for 2 is: ( 2 , 3 )

```

WARNINGS

```     If your compiler does not support default  template  parame-
ters,  then you always need to supply the Allocator template
argument. For instance, you have to write:

vector<int,allocator<int> >

vector<int>

If your compiler does not support namespaces,  then  you  do
not need the using declaration for std.

```

```     binary_function, lower_bound, upper_bound

```