equal_range
Finds a pair of positions in an ordered range, the first less than or equivalent to the position of a specified element and the second greater than the element's position, where the sense of equivalence or ordering used to establish the positions in the sequence may be specified by a binary predicate.
template<class ForwardIterator, class Type>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val
);
template<class ForwardIterator, class Type, class Predicate>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val,
Predicate _Comp
);
Parameters
_First
A forward iterator addressing the position of the first element in the range to be searched._Last
A forward iterator addressing the position one past the final element in the range to be searched._Val
The value in the ordered range that needs to be equivalent to the value of the element addressed by the first component of the pair returned and that needs to be less than the value of the element addressed by the second component of that pair returns._Comp
User-defined predicate function object that is true when the left-hand argument is less than the right-hand argument. The user-defined predicate function should return false when its arguments are equivalent.
Return Value
A pair of forward iterators addressing two positions in an ordered range in which the first component of the pair refers to the position where an element is or would be if it had a value that is less than or equivalent to a specified value and the second component of the pair refers to the first position where an element has a value that is greater than the value specified, where the sense of equivalence or ordering may be specified by a binary predicate.
Alternately, the pair of forward iterators may be described as specify a subrange, contained within the range searched, in which all of the elements are equivalent to the specified value in the sense defined by the binary predicate used.
Remarks
The first component of the pair of the algorithm returns lower_bound, and the second component returns upper_bound.
The subrange defined by the pair of iterators returned by the equal_range algorithm contains the equivalence class, in the standard set-theoretic sense, of the element whose value is specified as a parameter.
The sorted source range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position must be reachable from the first by incrementation.
The sorted range must each be arranged as a precondition to the application of the equal_range algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined ranges.
The range is not modified by the algorithm merge.
The value types of the forward iterators need be less-than comparable to be ordered, so that, given two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements
The complexity of the algorithm is logarithmic for random-access iterators and linear otherwise, with the number of steps proportional to (_Last1 – _First1).
Example
// alg_equal_range.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional> //For greater<int>( )
#include <iostream>
// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser ( int elem1, int elem2 )
{
if ( elem1 < 0 )
elem1 = - elem1;
if ( elem2 < 0 )
elem2 = - elem2;
return elem1 < elem2;
}
int main( )
{
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;
pair < vector <int> :: iterator , vector <int> :: iterator > Result1, Result2, Result3;
// Constructing vectors v1a & v1b with default less than ordering
int i;
for ( i = -1 ; i <= 4 ; i++ )
{
v1.push_back( i );
}
int ii;
for ( ii =-3 ; ii <= 0 ; ii++ )
{
v1.push_back( ii );
}
sort ( v1.begin ( ) , v1.end ( ) );
cout << "Original vector v1 with range sorted by the\n "
<< "binary predicate less than is v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Constructing vectors v2 with range sorted by greater
vector <int> v2 ( v1 );
vector <int>::iterator Iter2;
sort ( v2.begin ( ) , v2.end ( ) , greater<int> ( ) );
cout << "Original vector v2 with range sorted by the\n "
<< "binary predicate greater is v2 = ( " ;
for ( Iter2 = v2.begin ( ) ; Iter2 != v2.end ( ) ; Iter2++ )
cout << *Iter2 << " ";
cout << ")." << endl;
// Constructing vectors v3 with range sorted by mod_lesser
vector <int> v3 ( v1 );
vector <int>::iterator Iter3;
sort ( v3.begin ( ) , v3.end ( ) , mod_lesser );
cout << "Original vector v3 with range sorted by the\n "
<< "binary predicate mod_lesser is v3 = ( " ;
for ( Iter3 = v3.begin ( ) ; Iter3 != v3.end ( ) ; Iter3++ )
cout << *Iter3 << " ";
cout << ")." << endl << endl;
// equal_range of 3 in v1 with default binary predicate less <int> ( )
Result1 = equal_range ( v1.begin ( ) , v1.end ( ) , 3 );
cout << "The lower_bound in v1 for the element with a value of 3 is: "
<< *Result1.first << "." << endl;
cout << "The upper_bound in v1 for the element with a value of 3 is: "
<< *Result1.second << "." << endl;
cout << "The equivalence class for the element with a value of 3 in"
<< "\n v1 includes the elements: ( ";
for ( Iter1 = Result1.first ; Iter1 != Result1.second ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl << endl;
// equal_range of 3 in v2 with the binary predicate greater <int> ( )
Result2 = equal_range ( v2.begin ( ) , v2.end ( ) , 3 , greater <int> ( ) );
cout << "The lower_bound in v2 for the element with a value of 3 is: "
<< *Result2.first << "." << endl;
cout << "The upper_bound in v2 for the element with a value of 3 is: "
<< *Result2.second << "." << endl;
cout << "The equivalence class for the element with a value of 3 in"
<< "\n v2 includes the elements: ( ";
for ( Iter2 = Result2.first ; Iter2 != Result2.second ; Iter2++ )
cout << *Iter2 << " ";
cout << ")." << endl << endl;
// equal_range of 3 in v3 with the binary predicate mod_lesser
Result3 = equal_range ( v3.begin ( ) , v3.end ( ) , 3 ,mod_lesser );
cout << "The lower_bound in v3 for the element with a value of 3 is: "
<< *Result3.first << "." << endl;
cout << "The upper_bound in v3 for the element with a value of 3 is: "
<< *Result3.second << "." << endl;
cout << "The equivalence class for the element with a value of 3 in"
<< "\n v3 includes the elements: ( ";
for ( Iter3 = Result3.first ; Iter3 != Result3.second ; Iter3++ )
cout << *Iter3 << " ";
cout << ")." << endl << endl;
}
Original vector v1 with range sorted by the
binary predicate less than is v1 = ( -3 -2 -1 -1 0 0 1 2 3 4 ).
Original vector v2 with range sorted by the
binary predicate greater is v2 = ( 4 3 2 1 0 0 -1 -1 -2 -3 ).
Original vector v3 with range sorted by the
binary predicate mod_lesser is v3 = ( 0 0 -1 -1 1 -2 2 -3 3 4 ).
The lower_bound in v1 for the element with a value of 3 is: 3.
The upper_bound in v1 for the element with a value of 3 is: 4.
The equivalence class for the element with a value of 3 in
v1 includes the elements: ( 3 ).
The lower_bound in v2 for the element with a value of 3 is: 3.
The upper_bound in v2 for the element with a value of 3 is: 2.
The equivalence class for the element with a value of 3 in
v2 includes the elements: ( 3 ).
The lower_bound in v3 for the element with a value of 3 is: -3.
The upper_bound in v3 for the element with a value of 3 is: 4.
The equivalence class for the element with a value of 3 in
v3 includes the elements: ( -3 3 ).
Requirements
Header: <algorithm>
Namespace: std