.\" ident @(#)equal_range.3
.\" Standard Template Library
.\" $$RW_INSERT_HEADER "slyrs.man"
.TH equal_range 3C++ "02 Apr 1998" "Rogue Wave Software" "-"
.ce2
Standard C++ Library   
Copyright 1998, Rogue Wave Software, Inc.   

.SH NAME

\f2equal_range\fP

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



.SH  SYNOPSIS


.br
#include <algorithm>
.br
template <class ForwardIterator, class T>
.br
pair<ForwardIterator, ForwardIterator>
.RE
.RS 1
equal_range(ForwardIterator first, ForwardIterator last,
.RE
.RS 12
const T& value);
.RE
.RS 0

.br
template <class ForwardIterator, class T, class Compare>
.RE
.RS 1
pair<ForwardIterator, ForwardIterator>
.RE
.RS 2
equal_range(ForwardIterator first, ForwardIterator last,
.RE
.RS 13
const T& value, Compare comp);



.SH  DESCRIPTION


The equal_range algorithm performs a binary search on an ordered container to determine where the element \f2value\fP 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 (\f2operator <\fP) 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 \f2Compare\fP, and assumes that \f2Compare\fP was the function used to sort the sequence. The function object must be a binary predicate. 

equal_range returns a pair of iterators, \f2i\fP and \f2j\fP, that define a range containing elements equivalent to \f2value\fP, in other words, the first and last valid insertion points for \f2value\fP. If \f2value\fP is not an element in the container, \f2i\fP and \f2j\fP are equal. Otherwise, \f2i\fP points to the first element not "less" than \f2value\fP, and \f2j\fP 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 \f2[i, j)\fP such that \f2value\fP can be inserted at any iterator \f2k\fP within the range. Depending upon the version of the algorithm used, \f2k\fP must satisfy one of the following conditions: 

\f2!(*k <  value)  &&  !(value  <  *k)\fP

 or 

\f2comp(*k,value) == false && comp(value, *k) == false\fP

The range \f2[first,last)\fP is assumed to be sorted. Type \f2T\fP must be LessThanComparable.



.SH  COMPLEXITY


equal_range performs at most \f22 * log(last - first) + 1\fP comparisons.



.SH  EXAMPLE



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

.br
.RE
.RS 0
Program Output



.RE
.RS 0

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



.SH  WARNINGS


If your compiler does not support default template parameters, then you always need to supply the \f2Allocator\fP template argument. For instance, you have to write:

\f2vector<int,allocator<int> >\fP

instead of:

\f2vector<int>\fP

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



.SH  SEE ALSO


binary_function, lower_bound, upper_bound