# equal_range

Category: algorithms | Component type: function

### Prototype

`Equal_range` is an overloaded name; there are actually two `equal_range` functions.

    template <class ForwardIterator, class LessThanComparable>
    pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first, ForwardIterator last,
                const LessThanComparable& value);

    template <class ForwardIterator, class T, class StrictWeakOrdering>
    pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first, ForwardIterator last, const T& value,
                StrictWeakOrdering comp);

### Description

`Equal_range` is a version of binary search: it attempts to find the element `value` in an ordered range `[first, last)` [1]. The value returned by `equal_range` is essentially a combination of the values returned by `lower_bound` and `upper_bound`: it returns a pair of iterators `i` and `j` such that `i` is the first position where `value` could be inserted without violating the ordering and `j` is the last position where `value` could be inserted without violating the ordering. It follows that every element in the range `[i, j)` is equivalent to [1] `value`, and that `[i, j)` is the largest subrange of `[first, last)` that has this property. The first version of `equal_range` uses `operator<` for comparison, and the second uses the function object `comp`.

The first version of `equal_range` returns a pair of iterators `[i, j)`. `i` is the furthermost iterator in `[first, last)` such that, for every iterator `k` in `[first, i)`, `*k < value`. `j` is the furthermost iterator in `[first, last)` such that, for every iterator `k` in `[first, j)`, `value < *k` is `false`. For every iterator `k` in `[i, j)`, neither `value < *k` nor `*k < value` is `true`. [2]

The second version of `equal_range` returns a pair of iterators `[i, j)`. `i` is the furthermost iterator in `[first, last)` such that, for every iterator `k` in `[first, i)`, `comp(*k, value)` is `true`. `j` is the furthermost iterator in `[first, last)` such that, for every iterator `k` in `[first, j)`, `comp(value, *k)` is `false`. For every iterator `k` in `[i, j)`, neither `comp(value, *k)` nor `comp(*k, value)` is `true`. [2]

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

### Requirements on types

For the first version:

- `ForwardIterator` is a model of Forward Iterator.
- `LessThanComparable` is a model of LessThan Comparable.
- The ordering on objects of type `LessThanComparable` is a strict weak ordering, as defined in the LessThan Comparable requirements.
- `ForwardIterator`'s value type is the same type as `LessThanComparable`.

For the second version:

- `ForwardIterator` is a model of Forward Iterator.
- `StrictWeakOrdering` is a model of Strict Weak Ordering.
- `ForwardIterator`'s value type is the same type as `T`.
- `ForwardIterator`'s value type is convertible to `StrictWeakOrdering`'s argument type.

### Preconditions

For the first version:

- `[first, last)` is a valid range.
- `[first, last)` is ordered in ascending order according to `operator<`. That is, for every pair of iterators `i` and `j` in `[first, last)` such that `i` precedes `j`, `*j < *i` is `false`.

For the second version:

- `[first, last)` is a valid range.
- `[first, last)` is ordered in ascending order according to the function object `comp`. That is, for every pair of iterators `i` and `j` in `[first, last)` such that `i` precedes `j`, `comp(*j, *i)` is `false`.

### Complexity

The number of comparisons is logarithmic: at most `2 * log(last - first) + 1`. If `ForwardIterator` is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to `last - first`. [3]

### Example

    int main()
    {
      int A[] = { 1, 2, 3, 3, 3, 5, 8 };
      const int N = sizeof(A) / sizeof(int);

      for (int i = 2; i <= 4; ++i) {
        pair<int*, int*> result = equal_range(A, A + N, i);

        cout << endl;
        cout << "Searching for " << i << endl;
        cout << "  First position where " << i << " could be inserted: "
             << result.first - A << endl;
        cout << "  Last position where " << i << " could be inserted: "
             << result.second - A << endl;
        if (result.first < A + N)
          cout << "  *result.first = " << *result.first << endl;
        if (result.second < A + N)
          cout << "  *result.second = " << *result.second << endl;
      }
    }

The output is:

    Searching for 2
      First position where 2 could be inserted: 1
      Last position where 2 could be inserted: 2
      *result.first = 2
      *result.second = 3

    Searching for 3
      First position where 3 could be inserted: 2
      Last position where 3 could be inserted: 5
      *result.first = 3
      *result.second = 5

    Searching for 4
      First position where 4 could be inserted: 5
      Last position where 4 could be inserted: 5
      *result.first = 5
      *result.second = 5

### Notes

[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values `x` and `y` such that `x < y`, `x > y`, and `x == y` are all `false`. (See the LessThan Comparable requirements for a more complete discussion.) Finding `value` in the range `[first, last)`, then, doesn't mean finding an element that is equal to `value` but rather one that is equivalent to `value`: one that is neither greater than nor less than `value`. If you're using a total ordering, however (if you're using `strcmp`, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.

[2] Note that `equal_range` may return an empty range; that is, it may return a pair both of whose elements are the same iterator. `Equal_range` returns an empty range if and only if the range `[first, last)` contains no elements equivalent to `value`. In this case it follows that there is only one position where `value` could be inserted without violating the range's ordering, so the return value is a pair both of whose elements are iterators that point to that position.

[3] This difference between Random Access Iterators and Forward Iterators is simply because `advance` is constant time for Random Access Iterators and linear time for Forward Iterators.

### See also

`lower_bound`, `upper_bound`, `binary_search`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation