equal_range

Algorithm

• Summary
• Data Type and Member Function Indexes
• Synopsis
• Description
• Complexity
• Example
• Warnings
• See Also

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

None

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

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 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. Type T must be LessThanComparable.

equal_range performs at most 2 * log(last - first) + 1 comparisons.

//
// 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 )

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.

binary_function, lower_bound, upper_bound