## equal_range

    Algorithm

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

### Summary

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

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### 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 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.

### Complexity

equal_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 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 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

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998