16.3.11. lower_bound, upper_bound and equal_range
Figure 16.11 demonstrates algorithms lower_bound, upper_bound and equal_range.
1 // Fig. 16.11: fig16_11.cpp
2 // Algorithms lower_bound, upper_bound and
3 // equal_range for a sorted sequence of values.
4 #include <iostream>
5 #include <algorithm> // algorithm definitions
6 #include <array> // aray class-template definition
7 #include <iterator> // ostream_iterator
8 using namespace std;
9
10 int main()
11 {
12 const size_t SIZE = 10;
13 array< int, SIZE > a = { 2, 2, 4, 4, 4, 6, 6, 6, 6, 8 };
14 ostream_iterator< int > output( cout, " " );
15
16 cout << "array a contains:
";
17 copy( a.cbegin(), a.cend(), output );
18
19 // determine lower-bound insertion point for 6 in a
20 auto lower = lower_bound( a.cbegin(), a.cend(), 6 );
21 cout << "
Lower bound of 6 is element "
22 << ( lower - a.cbegin() ) << " of array a";
23
24 // determine upper-bound insertion point for 6 in a
25 auto upper = upper_bound( a.cbegin(), a.cend(), 6 );
26 cout << "
Upper bound of 6 is element "
27 << ( upper - a.cbegin() ) << " of array a";
28
29 // use equal_range to determine both the lower- and
30 // upper-bound insertion points for 6
31 auto eq = equal_range( a.cbegin(), a.cend(), 6 );
32 cout << "
Using equal_range:
Lower bound of 6 is element "
33 << ( eq.first - a.cbegin() ) << " of array a";
34 cout << "
Upper bound of 6 is element "
35 << ( eq.second - a.cbegin() ) << " of array a";
36 cout << "
Use lower_bound to locate the first point
"
37 << "at which 5 can be inserted in order";
38
39 // determine lower-bound insertion point for 5 in a
40 lower = lower_bound( a.cbegin(), a.cend(), 5 );
41 cout << "
Lower bound of 5 is element "
42 << ( lower - a.cbegin() ) << " of array a";
43 cout << "
Use upper_bound to locate the last point
"
44 << "at which 7 can be inserted in order";
45
46 // determine upper-bound insertion point for 7 in a
47 upper = upper_bound( a.cbegin(), a.cend(), 7 );
48 cout << "
Upper bound of 7 is element "
49 << ( upper - a.cbegin() ) << " of array a";
50 cout << "
Use equal_range to locate the first and
"
51 << "last point at which 5 can be inserted in order";
52
53 // use equal_range to determine both the lower- and
54 // upper-bound insertion points for 5
55 eq = equal_range( a.cbegin(), a.cend(), 5 );
56 cout << "
Lower bound of 5 is element "
57 << ( eq.first - a.cbegin() ) << " of array a";
58 cout << "
Upper bound of 5 is element "
59 << ( eq.second - a.cbegin() ) << " of array a" << endl;
60 } // end main
Array a contains:
2 2 4 4 4 6 6 6 6 8
Lower bound of 6 is element 5 of array a
Upper bound of 6 is element 9 of array a
Using equal_range:
Lower bound of 6 is element 5 of array a
Upper bound of 6 is element 9 of array a
Use lower_bound to locate the first point
at which 5 can be inserted in order
Lower bound of 5 is element 5 of array a
Use upper_bound to locate the last point
at which 7 can be inserted in order
Upper bound of 7 is element 9 of array a
Use equal_range to locate the first and
last point at which 5 can be inserted in order
Lower bound of 5 is element 5 of array a
Upper bound of 5 is element 5 of array a
Fig. 16.11. Algorithms lower_bound, upper_bound and equal_range for a sorted sequence of values.
lower_bound Algorithm
Line 20 uses the lower_bound algorithm to find the first location in a sorted sequence of values at which the third argument could be inserted in the sequence such that the sequence would still be sorted in ascending order. The first two iterator arguments must be at least forward iterators. The third argument is the value for which to determine the lower bound. The algorithm returns a forward iterator pointing to the position at which the insert can occur. A second version of lower_bound takes as a fourth argument a binary predicate function indicating the order in which the elements were originally sorted.
upper_bound Algorithm
Line 25 uses the upper_bound algorithm to find the last location in a sorted sequence of values at which the third argument could be inserted in the sequence such that the sequence would still be sorted in ascending order. The first two iterator arguments must be at least forward iterators. The third argument is the value for which to determine the upper bound. The algorithm returns a forward iterator pointing to the position at which the insert can occur. A second version of upper_bound takes as a fourth argument a binary predicate function indicating the order in which the elements were originally sorted.
equal_range Algorithm
Line 31 uses the equal_range algorithm to return a pair of forward iterators containing the results of performing both a lower_bound and an upper_bound operation. The first two arguments must be at least forward iterators. The third is the value for which to locate the equal range. The algorithm returns a pair of forward iterators for the lower bound (eq.first) and upper bound (eq.second), respectively.
Locating Insertion Points in Sorted Sequences
Algorithms lower_bound, upper_bound and equal_range are often used to locate insertion points in sorted sequences. Line 40 uses lower_bound to locate the first point at which 5 can be inserted in order in a. Line 47 uses upper_bound to locate the last point at which 7 can be inserted in order in a. Line 55 uses equal_range to locate the first and last points at which 5 can be inserted in order in a.