Category: algorithms | Component type: function |
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);
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]
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
[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.