# 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 functors `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 ForwardIterator.
• `LessThanComparable` is a model of LessThanComparable.
• The ordering on objects of type `LessThanComparable` is a strict weak ordering, as defined in the LessThanComparable requirements.
• `ForwardIterator`'s value type is the same type as `LessThanComparable`.

For the second version:

• `ForwardIterator` is a model of ForwardIterator.
• `StrictWeakOrdering` is a model of StrictWeakOrdering.
• `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 functors `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 RandomAccessIterator 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 LessThanComparable 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 RandomAccessIterator and ForwardIterator is simply because `advance` is constant time for RandomAccessIterator and linear time for ForwardIterator.

`lower_bound`, `upper_bound`, `binary_search`