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:
