Standard Template Library Programmer's Guide

Searching for 3. Result: index = 5, A[5] == 5

Searching for 4. Result: index = 5, A[5] == 5

Searching for 5. Result: index = 6, A[6] == 8

Searching for 6. Result: index = 6, A[6] == 8

Searching for 7. Result: index = 6, A[6] == 8

Searching for 8. Result: index = 7, which is off-the-end.

Searching for 9. Result: index = 7, which is off-the-end.

Searching for 10. Result: index = 7, which is off-the-end.

[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 even if an element that is equivalent to [1] value is already present in the range [first, last) , the return value of upper_bound will not point to that element. The return value is either last or else an iterator i such that value < *i . If i is not equal to first , however, then *(i – 1) is less than or equivalent to value .

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

lower_bound , equal_range , binary_search

Category: algorithms

Component type: function

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

template

pair equal_range(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);

template

pair equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);

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]

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

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.

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 .

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]

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