16.3.6. Basic Searching and Sorting Algorithms
Figure 16.6 demonstrates some basic searching and sorting Standard Library algorithms, including find, find_if, sort, binary_search, all_of, any_of, none_of and find_if_not.
1 // Fig. 16.6: fig16_06.cpp
2 // Standard Library search and sort algorithms.
3 #include <iostream>
4 #include <algorithm> // algorithm definitions
5 #include <array> // array class-template definition
6 #include <iterator>
7 using namespace std;
8
9 bool greater10( int value ); // predicate function prototype
10
11 int main()
12 {
13 const size_t SIZE = 10;
14 array< int, SIZE > a = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 };
15 ostream_iterator< int > output( cout, " " );
16
17 cout << "array a contains: ";
18 copy( a.cbegin(), a.cend(), output ); // display output vector
19
20 // locate first occurrence of 16 in a
21 auto location = find( a.cbegin(), a.cend(), 16 );
22
23 if ( location != a.cend() ) // found 16
24 cout << "
Found 16 at location " << ( location - a.cbegin() );
25 else // 16 not found
26 cout << "
16 not found";
27
28 // locate first occurrence of 100 in a
29 location = find( a.cbegin(), a.cend(), 100 );
30
31 if ( location != a.cend() ) // found 100
32 cout << "
Found 100 at location " << ( location - a.cbegin() );
33 else // 100 not found
34 cout << "
100 not found";
35
36 // locate first occurrence of value greater than 10 in a
37 location = find_if( a.cbegin(), a.cend(), greater10 );
38
39 if ( location != a.cend() ) // found value greater than 10
40 cout << "
The first value greater than 10 is " << *location
41 << "
found at location " << ( location - a.cbegin() );
42 else // value greater than 10 not found
43 cout << "
No values greater than 10 were found";
44
45 // sort elements of a
46 sort( a.begin(), a.end() );
47 cout << "
array a after sort: ";
48 copy( a.cbegin(), a.cend(), output );
49
50 // use binary_search to locate 13 in a
51 if ( binary_search( a.cbegin(), a.cend(), 13 ) )
52 cout << "
13 was found in a";
53 else
54 cout << "
13 was not found in a";
55
56 // use binary_search to locate 100 in a
57 if ( binary_search( a.cbegin(), a.cend(), 100 ) )
58 cout << "
100 was found in a";
59 else
60 cout << "
100 was not found in a";
61
62 // determine whether all of the elements of a are greater than 10
63 if ( all_of( a.cbegin(), a.cend(), greater10 ) )
64 cout << "
All the elements in a are greater than 10";
65 else
66 cout << "
Some elements in a are not greater than 10";
67
68 // determine whether any of the elements of a are greater than 10
69 if ( any_of( a.cbegin(), a.cend(), greater10 ) )
70 cout << "
Some of the elements in a are greater than 10";
71 else
72 cout << "
None of the elements in a are greater than 10";
73
74 // determine whether none of the elements of a are greater than 10
75 if ( none_of( a.cbegin(), a.cend(), greater10 ) )
76 cout << "
None of the elements in a are greater than 10";
77 else
78 cout << "
Some of the elements in a are greater than 10";
79
80 // locate first occurrence of value that's not greater than 10 in a
81 location = find_if_not( a.cbegin(), a.cend(), greater10 );
82
83 if ( location != a.cend() ) // found a value less than or eqaul to 10
84 cout << "
The first value not greater than 10 is " << *location
85 << "
found at location " << ( location - a.cbegin() );
86 else // no values less than or equal to 10 were found
87 cout << "
Only values greater than 10 were found";
88
89 cout << endl;
90 } // end main
91
92 // determine whether argument is greater than 10
93 bool greater10( int value )
94 {
95 return value > 10;
96 } // end function greater10
array a contains: 10 2 17 5 16 8 13 11 20 7
Found 16 at location 4
100 not found
The first value greater than 10 is 17
found at location 2
array a after sort: 2 5 7 8 10 11 13 16 17 20
13 was found in a
100 was not found in a
Some elements in a are not greater than 10
Some of the elements in a are greater than 10
Some of the elements in a are greater than 10
The first value not greater than 10 is 2
found at location 0
Fig. 16.6. Standard Library search and sort algorithms.
find Algorithm
Line 21 uses the find algorithm to locate the value 16 in the range from a.cbegin() up to, but not including, a.cend(). The algorithm requires its two iterator arguments to be at least input iterators and returns an input iterator that either is positioned at the first element containing the value or indicates the end of the sequence (as is the case in line 29).
find_if Algorithm
Line 37 uses the find_if algorithm (a linear search) to locate the first value in the range from a.cbegin() up to, but not including, a.cend() for which the unary predicate function greater10 returns true. Function greater10 (defined in lines 93–96) takes an integer and returns a bool value indicating whether the integer argument is greater than 10. Algorithm find_if requires its two iterator arguments to be at least input iterators. The algorithm returns an input iterator that either is positioned at the first element containing a value for which the predicate function returns true or indicates the end of the sequence.
sort Algorithm
Line 46 uses sort algorithm to arrange the elements in the range from a.begin() up to, but not including, a.end() in ascending order. The algorithm requires its two iterator arguments to be random-access iterators. A second version of this algorithm takes a third argument that’s a binary predicate function taking two arguments that are values in the sequence and returning a bool indicating the sorting order—if the return value is true, the two elements being compared are in sorted order.
binary_search Algorithm
Line 51 uses the binary_search algorithm to determine whether the value 13 is in the range from a.cbegin() up to, but not including, a.cend(). The values must be sorted in ascending order. Algorithm binary_search requires its two iterator arguments to be at least forward iterators. The algorithm returns a bool indicating whether the value was found in the sequence. Line 57 demonstrates a call to binary_search in which the value is not found. A second version of this algorithm takes a fourth argument that’s a binary predicate function taking two arguments that are values in the sequence and returning a bool. The predicate function returns true if the two elements being compared are in sorted order. To obtain the location of the search key in the container, use the lower_bound or find algorithms.
C++11: all_of Algorithm
Line 63 uses the all_of algorithm to determine whether the unary predicate function greater10 returns true for all of the elements in the range from a.cbegin() up to, but not including, a.cend(). Algorithm all_of requires its two iterator arguments to be at least input iterators.
C++11: any_of Algorithm
Line 69 uses the any_of algorithm to determine whether the unary predicate function greater10 returns true for at least one of the elements in the range from a.cbegin() up to, but not including, a.cend(). Algorithm any_of requires its two iterator arguments to be at least input iterators.
C++11: none_of Algorithm
Line 75 uses the none_of algorithm to determine whether the unary predicate function greater10 returns false for all of the elements in the range from a.cbegin() up to, but not including, a.cend(). Algorithm none_of requires its two iterator arguments to be at least input iterators.
C++11: find_if_not Algorithm
Line 81 uses the find_if_not algorithm to locate the first value in the range from a.cbegin() up to, but not including, a.cend() for which the unary predicate function greater10 returns false. Algorithm find_if requires its two iterator arguments to be at least input iterators. The algorithm returns an input iterator that either is positioned at the first element containing a value for which the predicate function returns false or indicates the end of the sequence.