equal_range (3C++std) - Tru64 UNIX
Standard C++ LibraryCopyright 1996, 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 provides 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, i.e., 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 will point to the first element not "less"
than value, and j will point 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 following conditions:
!(*k < value) && !(value < *k)
or
comp(*k,value) == false && comp(value, *k) == false
The range [first,last) is assumed to be sorted.
COMPLEXITY
equal_range performs at most 2 * log(last - first) + 1 comparisons.
EXAMPLE
//
// eqlrange.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
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;
}
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 parameters then you need
to always supply the Allocator template argument. For instance you'll have
to write:
vector<int,allocator<int> >
SEE ALSO
instead of:
vector<int> binary_function, lower_bound, upper_bound
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
|