equal_range(3C++) - equal_range(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEequal_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 con‐
tainer 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 (opera‐
tor <) 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 ele‐
ment 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 algorithm used, k must satisfy one of the fol‐
lowing 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.
COMPLEXITYequal_range performs at most 2 * log(last - first) + 1 comparisons.
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 OutputThe equal range for 3 is: ( 3 , 4 )
The equal range for 2 is: ( 2 , 3 )
WARNINGS
If your compiler does not support default template parameters, then you
always need to supply the Allocator template argument. For instance,
you have to write:
vector<int,allocator<int> >
instead of:
vector<int>
If your compiler does not support namespaces, then you do not need the
using declaration for std.
SEE ALSO
binary_function, lower_bound, upper_bound
Rogue Wave Software 02 Apr 1998 equal_range(3C++)