Algorithms
Until the STL, class libraries of containers and algorithms were essentially incompatible among vendors. Early container libraries generally used inheritance and polymorphism, with the associated overhead of virtual function calls. Early libraries built the algorithms into the container classes as class behaviors. The STL separates the algorithms from the containers. This makes it much easier to add new algorithms. With the STL, the elements of containers are accessed through iterators. The next several subsections demonstrate many of the STL algorithms.
Performance Tip 23.22
|
The STL is implemented for efficiency. It avoids the overhead of virtual function calls. |
Software Engineering Observation 23.8
|
STL algorithms do not depend on the implementation details of the containers on which they operate. As long as the container's (or array's) iterators satisfy the requirements of the algorithm, STL algorithms can work on C-style, pointer-based arrays, on STL containers and on userdefined data structures. |
Software Engineering Observation 23.9
|
Algorithms can be added easily to the STL without modifying the container classes. |
23.5.1. fill, fill_n, generate and generate_n
Figure 23.26 demonstrates algorithms fill, fill_n, generate and generate_n. Functions fill and fill_n set every element in a range of container elements to a specific value. Functions generate and generate_n use a generator function to create values for every element in a range of container elements. The generator function takes no arguments and returns a value that can be placed in an element of the container.
Figure 23.26. Algorithms fill, fill_n, generate and generate_n.
(This item is displayed on pages 1153 - 1154 in the print version)
|
1 // Fig. 23.26: Fig23_26.cpp 2 // Standard Library algorithms fill, fill_n, generate and generate_n. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // algorithm definitions 8 #include // vector class-template definition 9 #include // ostream_iterator 10 11 char nextLetter(); // prototype of generator function 12 13 int main() 14 { 15 std::vector< char > chars( 10 ); 16 std::ostream_iterator< char > output( cout, " " ); 17 std::fill( chars.begin(), chars.end(), '5' ); // fill chars with 5s 18 19 cout << "Vector chars after filling with 5s: "; 20 std::copy( chars.begin(), chars.end(), output ); 21 22 // fill first five elements of chars with As 23 std::fill_n( chars.begin(), 5, 'A' ); 24 25 cout << " Vector chars after filling five elements with As: "; 26 std::copy( chars.begin(), chars.end(), output ); 27 28 // generate values for all elements of chars with nextLetter 29 std::generate( chars.begin(), chars.end(), nextLetter ); 30 31 cout << " Vector chars after generating letters A-J: "; 32 std::copy( chars.begin(), chars.end(), output ); 33 34 // generate values for first five elements of chars with nextLetter 35 std::generate_n( chars.begin(), 5, nextLetter ); 36 37 cout << " Vector chars after generating K-O for the" 38 << " first five elements: "; 39 std::copy( chars.begin(), chars.end(), output ); 40 cout << endl; 41 return 0; 42 } // end main 43 44 // generator function returns next letter (starts with A) 45 char nextLetter() 46 { 47 static char letter = 'A'; 48 return letter++; 49 } // end function nextLetter
|
Line 15 defines a 10-element vector that stores char values. Line 17 uses function fill to place the character '5' in every element of vector chars from chars.begin() up to, but not including, chars.end(). Note that the iterators supplied as the first and second argument must be at least forward iterators (i.e., they can be used for both input from a container and output to a container in the forward direction).
Line 23 uses function fill_n to place the character 'A' in the first five elements of vector chars. The iterator supplied as the first argument must be at least an output iterator (i.e., it can be used for output to a container in the forward direction). The second argument specifies the number of elements to fill. The third argument specifies the value to place in each element.
Line 29 uses function generate to place the result of a call to generator function nextLetter in every element of vector chars from chars.begin() up to, but not including, chars.end(). The iterators supplied as the first and second arguments must be at least forward iterators. Function nextLetter (defined at lines 4549) begins with the character 'A' maintained in a static local variable. The statement at line 48 postincrements the value of letter and returns the old value of letter each time nextLetter is called.
Line 35 uses function generate_n to place the result of a call to generator function nextLetter in five elements of vector chars, ostarting from chars.begin(). The iterator supplied as the first argument must be at least an output iterator.
23.5.2. equal, mismatch and lexicographical_compare
Figure 23.27 demonstrates comparing sequences of values for equality using algorithms equal, mismatch and lexicographical_compare.
Figure 23.27. Algorithms equal, mismatch and lexicographical_compare.
(This item is displayed on pages 1155 - 1156 in the print version)
|
1 // Fig. 23.27: Fig23_27.cpp 2 // Standard Library functions equal, mismatch and lexicographical_compare. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // algorithm definitions 8 #include // vector class-template definition 9 #include // ostream_iterator 10 11 int main() 12 { 13 const int SIZE = 10; 14 int a1[ SIZE ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 15 int a2[ SIZE ] = { 1, 2, 3, 4, 1000, 6, 7, 8, 9, 10 }; 16 std::vector< int > v1( a1, a1 + SIZE ); // copy of a1 17 std::vector< int > v2( a1, a1 + SIZE ); // copy of a1 18 std::vector< int > v3( a2, a2 + SIZE ); // copy of a2 19 std::ostream_iterator< int > output( cout, " " ); 20 21 cout << "Vector v1 contains: "; 22 std::copy( v1.begin(), v1.end(), output ); 23 cout << " Vector v2 contains: "; 24 std::copy( v2.begin(), v2.end(), output ); 25 cout << " Vector v3 contains: "; 26 std::copy( v3.begin(), v3.end(), output ); 27 28 // compare vectors v1 and v2 for equality 29 bool result = std::equal( v1.begin(), v1.end(), v2.begin() ); 30 cout << " Vector v1 " << ( result ? "is" : "is not" ) 31 << " equal to vector v2. "; 32 33 // compare vectors v1 and v3 for equality 34 result = std::equal( v1.begin(), v1.end(), v3.begin() ); 35 cout << "Vector v1 " << ( result ? "is" : "is not" ) 36 << " equal to vector v3. "; 37 38 // location represents pair of vector iterators 39 std::pair< std::vector< int >::iterator, 40 std::vector< int >::iterator > location; 41 42 // check for mismatch between v1 and v3 43 location = std::mismatch( v1.begin(), v1.end(), v3.begin() ); 44 cout << " There is a mismatch between v1 and v3 at location " 45 << ( location.first - v1.begin() ) << " where v1 contains " 46 << *location.first << " and v3 contains " << *location.second 47 << " "; 48 49 char c1[ SIZE ] = "HELLO"; 50 char c2[ SIZE ] = "BYE BYE"; 51 52 // perform lexicographical comparison of c1 and c2 53 result = std::lexicographical_compare( c1, c1 + SIZE, c2, c2 + SIZE ); 54 cout << c1 << ( result ? " is less than " : 55 " is greater than or equal to " ) << c2 << endl; 56 return 0; 57 } // end main
|
Line 29 uses function equal to compare two sequences of values for equality. Each sequence need not necessarily contain the same number of elementsequal returns false if the sequences are not of the same length. The == operator (whether built-in or overloaded) performs the comparison of the elements. In this example, the elements in vector v1 from v1.begin() up to, but not including, v1.end() are compared to the elements in vector v2 starting from v2.begin(). In this example, v1 and v2 are equal. The three iterator arguments must be at least input iterators (i.e., they can be used for input from a sequence in the forward direction). Line 34 uses function equal to compare vectors v1 and v3, which are not equal.
There is another version of function equal that takes a binary predicate function as a fourth parameter. The binary predicate function receives the two elements being compared and returns a bool value indicating whether the elements are equal. This can be useful in sequences that store objects or pointers to values rather than actual values, because you can define one or more comparisons. For example, you can compare Employee objects for age, social security number, or location rather than comparing entire objects. You can compare what pointers refer to rather than comparing the pointer values (i.e., the addresses stored in the pointers).
Lines 3943 begin by instantiating a pair of iterators called location for a vector of integers. This object stores the result of the call to mismatch (line 43). Function mismatch compares two sequences of values and returns a pair of iterators indicating the location in each sequence of the mismatched elements. If all the elements match, the two iterators in the pair are equal to the last iterator for each sequence. The three iterator arguments must be at least input iterators. Line 45 determines the actual location of the mismatch in the vectors with the expression location.first - v1.begin(). The result of this calculation is the number of elements between the iterators (this is analogous to pointer arithmetic, which we studied in Chapter 8). This corresponds to the element number in this example, because the comparison is performed from the beginning of each vector. As with function equal, there is another version of function mismatch that takes a binary predicate function as a fourth parameter.
Line 53 uses function lexicographical_compare to compare the contents of two character arrays. This function's four iterator arguments must be at least input iterators. As you know, pointers into arrays are random-access iterators. The first two iterator arguments specify the range of locations in the first sequence. The last two specify the range of locations in the second sequence. While iterating through the sequences, the lexicographical_compare checks if the element in the first sequence is less than the corresponding element in the second sequence. If so, the function returns TRue. If the element in the first sequence is greater than or equal to the element in the second sequence, the function returns false. This function can be used to arrange sequences lexicographically. Typically, such sequences contain strings.
23.5.3. remove, remove_if, remove_copy and remove_copy_if
Figure 23.28 demonstrates removing values from a sequence with algorithms remove, remove_if, remove_copy and remove_copy_if.
Figure 23.28. Algorithms remove, remove_if, remove_copy and remove_copy_if.
(This item is displayed on pages 1157 - 1159 in the print version)
|
1 // Fig. 23.28: Fig23_28.cpp 2 // Standard Library functions remove, remove_if, 3 // remove_copy and remove_copy_if. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include // algorithm definitions 9 #include // vector class-template definition 10 #include // ostream_iterator 11 12 bool greater9( int ); // prototype 13 14 int main() 15 { 16 const int SIZE = 10; 17 int a[ SIZE ] = { 10, 2, 10, 4, 16, 6, 14, 8, 12, 10 }; 18 std::ostream_iterator< int > output( cout, " " ); 19 std::vector< int > v( a, a + SIZE ); // copy of a 20 std::vector< int >::iterator newLastElement; 21 22 cout << "Vector v before removing all 10s: "; 23 std::copy( v.begin(), v.end(), output ); 24 25 // remove all 10s from v 26 newLastElement = std::remove( v.begin(), v.end(), 10 ); 27 cout << " Vector v after removing all 10s: "; 28 std::copy( v.begin(), newLastElement, output ); 29 30 std::vector< int > v2( a, a + SIZE ); // copy of a 31 std::vector< int > c( SIZE, 0 ); // instantiate vector c 32 cout << " Vector v2 before removing all 10s and copying: "; 33 std::copy( v2.begin(), v2.end(), output ); 34 35 // copy from v2 to c, removing 10s in the process 36 std::remove_copy( v2.begin(), v2.end(), c.begin(), 10 ); 37 cout << " Vector c after removing all 10s from v2: "; 38 std::copy( c.begin(), c.end(), output ); 39 40 std::vector< int > v3( a, a + SIZE ); // copy of a 41 cout << " Vector v3 before removing all elements" 42 << " greater than 9: "; 43 std::copy( v3.begin(), v3.end(), output ); 44 45 // remove elements greater than 9 from v3 46 newLastElement = std::remove_if( v3.begin(), v3.end(), greater9 ); 47 cout << " Vector v3 after removing all elements" 48 << " greater than 9: "; 49 std::copy( v3.begin(), newLastElement, output ); 50 51 std::vector< int > v4( a, a + SIZE ); // copy of a 52 std::vector< int > c2( SIZE, 0 ); // instantiate vector c2 53 cout << " Vector v4 before removing all elements" 54 << " greater than 9 and copying: "; 55 std::copy( v4.begin(), v4.end(), output ); 56 57 // copy elements from v4 to c2, removing elements greater 58 // than 9 in the process 59 std::remove_copy_if( v4.begin(), v4.end(), c2.begin(), greater9 ); 60 cout << " Vector c2 after removing all elements" 61 << " greater than 9 from v4: "; 62 std::copy( c2.begin(), c2.end(), output ); 63 cout << endl; 64 return 0; 65 } // end main 66 67 // determine whether argument is greater than 9 68 bool greater9( int x ) 69 { 70 return x > 9; 71 } // end function greater9
|
Line 26 uses function remove to eliminate all elements with the value 10 in the range from v.begin() up to, but not including, v.end() from v. The first two iterator arguments must be forward iterators so that the algorithm can modify the elements in the sequence. This function does not modify the number of elements in the vector or destroy the eliminated elements, but it does move all elements that are not eliminated toward the beginning of the vector. The function returns an iterator positioned after the last vector element that was not deleted. Elements from the iterator position to the end of the vector have undefined values (in this example, each "undefined" position has value 0).
Line 36 uses function remove_copy to copy all elements that do not have the value 10 in the range from v2.begin() up to, but not including, v2.end() from v2. The elements are placed in c, starting at position c.begin(). The iterators supplied as the first two arguments must be input iterators. The iterator supplied as the third argument must be an output iterator so that the element being copied can be inserted into the copy location. This function returns an iterator positioned after the last element copied into vector c. Note, in line 31, the use of the vector constructor that receives the number of elements in the vector and the initial values of those elements.
Line 46 uses function remove_if to delete all those elements in the range from v3.begin() up to, but not including, v3.end() from v3 for which our user-defined unary predicate function greater9 returns true. Function greater9 (defined at lines 6871) returns true if the value passed to it is greater than 9; otherwise, it returns false. The iterators supplied as the first two arguments must be forward iterators so that the algorithm can modify the elements in the sequence. This function does not modify the number of elements in the vector, but it does move to the beginning of the vector all elements that are not eliminated. This function returns an iterator positioned after the last element in the vector that was not deleted. All elements from the iterator position to the end of the vector have undefined values.
Line 59 uses function remove_copy_if to copy all those elements in the range from v4.begin() up to, but not including, v4.end() from v4 for which the unary predicate function greater9 returns true. The elements are placed in c2, starting at position c2.begin(). The iterators supplied as the first two arguments must be input iterators. The iterator supplied as the third argument must be an output iterator so that the element being copied can be inserted into the copy location. This function returns an iterator positioned after the last element copied into c2.
23.5.4. replace, replace_if, replace_copy and replace_copy_if
Figure 23.29 demonstrates replacing values from a sequence using algorithms replace, replace_if, replace_copy and replace_copy_if.
Figure 23.29. Algorithms replace, replace_if, replace_copy and replace_copy_if.
(This item is displayed on pages 1160 - 1161 in the print version)
|
1 // Fig. 23.29: Fig23_29.cpp 2 // Standard Library functions replace, replace_if, 3 // replace_copy and replace_copy_if. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include 9 #include 10 #include // ostream_iterator 11 12 bool greater9( int ); // predicate function prototype 13 14 int main() 15 { 16 const int SIZE = 10; 17 int a[ SIZE ] = { 10, 2, 10, 4, 16, 6, 14, 8, 12, 10 }; 18 std::ostream_iterator< int > output( cout, " " ); 19 20 std::vector< int > v1( a, a + SIZE ); // copy of a 21 cout << "Vector v1 before replacing all 10s: "; 22 std::copy( v1.begin(), v1.end(), output ); 23 24 // replace all 10s in v1 with 100 25 std::replace( v1.begin(), v1.end(), 10, 100 ); 26 cout << " Vector v1 after replacing 10s with 100s: "; 27 std::copy( v1.begin(), v1.end(), output ); 28 29 std::vector< int > v2( a, a + SIZE ); // copy of a 30 std::vector< int > c1( SIZE ); // instantiate vector c1 31 cout << " Vector v2 before replacing all 10s and copying: "; 32 std::copy( v2.begin(), v2.end(), output ); 33 34 // copy from v2 to c1, replacing 10s with 100s 35 std::replace_copy( v2.begin(), v2.end(), c1.begin(), 10, 100 ); 36 cout << " Vector c1 after replacing all 10s in v2: "; 37 std::copy( c1.begin(), c1.end(), output ); 38 39 std::vector< int > v3( a, a + SIZE ); // copy of a 40 cout << " Vector v3 before replacing values greater than 9: "; 41 std::copy( v3.begin(), v3.end(), output ); 42 43 // replace values greater than 9 in v3 with 100 44 std::replace_if( v3.begin(), v3.end(), greater9, 100 ); 45 cout << " Vector v3 after replacing all values greater" 46 << " than 9 with 100s: "; 47 std::copy( v3.begin(), v3.end(), output ); 48 49 std::vector< int > v4( a, a + SIZE ); // copy of a 50 std::vector< int > c2( SIZE ); // instantiate vector c2' 51 cout << " Vector v4 before replacing all values greater " 52 << "than 9 and copying: "; 53 std::copy( v4.begin(), v4.end(), output ); 54 55 // copy v4 to c2, replacing elements greater than 9 with 100 56 std::replace_copy_if( 57 v4.begin(), v4.end(), c2.begin(), greater9, 100 ); 58 cout << " Vector c2 after replacing all values greater " 59 << "than 9 in v4: "; 60 std::copy( c2.begin(), c2.end(), output ); 61 cout << endl; 62 return 0; 63 } // end main 64 65 // determine whether argument is greater than 9 66 bool greater9( int x ) 67 { 68 return x > 9; 69 } // end function greater9
|
Line 25 uses function replace to replace all elements with the value 10 in the range from v1.begin() up to, but not including, v1.end() in v1 with the new value 100. The iterators supplied as the first two arguments must be forward iterators so that the algorithm can modify the elements in the sequence.
Line 35 uses function replace_copy to copy all elements in the range from v2.begin() up to, but not including, v2.end() from v2, replacing all elements with the value 10 with the new value 100. The elements are copied into c1, starting at position c1.begin(). The iterators supplied as the first two arguments must be input iterators. The iterator supplied as the third argument must be an output iterator so that the element being copied can be inserted into the copy location. This function returns an iterator positioned after the last element copied into c1.
Line 44 uses function replace_if to replace all those elements in the range from v3.begin() up to, but not including, v3.end() in v3 for which the unary predicate function greater9 returns TRue. Function greater9 (defined at lines 6669) returns true if the value passed to it is greater than 9; otherwise, it returns false. The value 100 replaces each value greater than 9. The iterators supplied as the first two arguments must be forward iterators so that the algorithm can modify the elements in the sequence.
Lines 5657 use function replace_copy_if to copy all elements in the range from v4.begin() up to, but not including, v4.end() from v4. Elements for which the unary predicate function greater9 returns TRue are replaced with the value 100. The elements are placed in c2, starting at position c2.begin(). The iterators supplied as the first two arguments must be input iterators. The iterator supplied as the third argument must be an output iterator so that the element being copied can be inserted into the copy location. This function returns an iterator positioned after the last element copied into c2.
23.5.5. Mathematical Algorithms
Figure 23.30 demonstrates several common mathematical algorithms from the STL, including random_shuffle, count, count_if, min_element, max_element, accumulate, for_each and TRansform.
Figure 23.30. Mathematical algorithms of the Standard Library.
(This item is displayed on pages 1162 - 1164 in the print version)
|
1 // Fig. 23.30: Fig23_30.cpp 2 // Mathematical algorithms of the Standard Library. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // algorithm definitions 8 #include // accumulate is defined here 9 #include 10 #include 11 12 bool greater9( int ); // predicate function prototype 13 void outputSquare( int ); // output square of a value 14 int calculateCube( int ); // calculate cube of a value 15 16 int main() 17 { 18 const int SIZE = 10; 19 int a1[ SIZE ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 20 std::vector< int > v( a1, a1 + SIZE ); // copy of a1 21 std::ostream_iterator< int > output( cout, " " ); 22 23 cout << "Vector v before random_shuffle: "; 24 std::copy( v.begin(), v.end(), output ); 25 26 std::random_shuffle( v.begin(), v.end() ); // shuffle elements of v 27 cout << " Vector v after random_shuffle: "; 28 std::copy( v.begin(), v.end(), output ); 29 30 int a2[ SIZE ] = { 100, 2, 8, 1, 50, 3, 8, 8, 9, 10 }; 31 std::vector< int > v2( a2, a2 + SIZE ); // copy of a2 32 cout << " Vector v2 contains: "; 33 std::copy( v2.begin(), v2.end(), output ); 34 35 // count number of elements in v2 with value 8 36 int result = std::count( v2.begin(), v2.end(), 8 ); 37 cout << " Number of elements matching 8: " << result; 38 39 // count number of elements in v2 that are greater than 9 40 result = std::count_if( v2.begin(), v2.end(), greater9 ); 41 cout << " Number of elements greater than 9: " << result; 42 43 // locate minimum element in v2 44 cout << " Minimum element in Vector v2 is: " 45 << *( std::min_element( v2.begin(), v2.end() ) ); 46 47 // locate maximum element in v2 48 cout << " Maximum element in Vector v2 is: " 49 << *( std::max_element( v2.begin(), v2.end() ) ); 50 51 // calculate sum of elements in v 52 cout << " The total of the elements in Vector v is: " 53 << std::accumulate( v.begin(), v.end(), 0 ); 54 55 // output square of every element in v 56 cout << " The square of every integer in Vector v is: "; 57 std::for_each( v.begin(), v.end(), outputSquare ); 58 59 std::vector< int > cubes( SIZE ); // instantiate vector cubes 60 61 // calculate cube of each element in v; place results in cubes 62 std::transform( v.begin(), v.end(), cubes.begin(), calculateCube ); 63 cout << " The cube of every integer in Vector v is: "; 64 std::copy( cubes.begin(), cubes.end(), output ); 65 cout << endl; 66 return 0; 67 } // end main 68 69 // determine whether argument is greater than 9 70 bool greater9( int value ) 71 { 72 return value > 9; 73 } // end function greater9 74 75 // output square of argument 76 void outputSquare( int value ) 77 { 78 cout << value * value << ' '; 79 } // end function outputSquare 80 81 // return cube of argument 82 int calculateCube( int value ) 83 { 84 return value * value * value; 85 } // end function calculateCube
|
Line 26 uses function random_shuffle to reorder randomly the elements in the range from v.begin() up to, but not including, v.end() in v. This function takes two randomaccess iterator arguments.
Line 36 uses function count to count the elements with the value 8 in the range from v2.begin() up to, but not including, v2.end() in v2. This function requires its two iterator arguments to be at least input iterators.
Line 40 uses function count_if to count those elements in the range from v2.begin() up to, but not including, v2.end() in v2 for which the predicate function greater9 returns TRue. Function count_if requires its two iterator arguments to be at least input iterators.
Line 45 uses function min_element to locate the smallest element in the range from v2.begin() up to, but not including, v2.end() in v2. The function returns a forward iterator located at the smallest element or, if the range is empty, returns v2.end(). The function requires its two iterator arguments to be at least input iterators. A second version of this function takes as its third argument a binary function that compares the elements in the sequence. The binary function takes two arguments and returns a bool value.
Good Programming Practice 23.2
|
It is a good practice to check that the range specified in a call to min_element is not empty and that the return value is not the "past the end" iterator. |
Line 49 uses function max_element to locate the largest element in the range from v2.begin() up to, but not including, v2.end() in v2. The function returns an input iterator located at the largest element. The function requires its two iterator arguments to be at least input iterators. A second version of this function takes as its third argument a binary predicate function that compares the elements in the sequence. The binary function takes two arguments and returns a bool value.
Line 53 uses function accumulate (the template of which is in header file ) to sum the values in the range from v.begin() up to, but not including, v.end() in v. The function's two iterator arguments must be at least input iterators and its third argument represents the initial value of the total. A second version of this function takes as its fourth argument a general function that determines how elements are accumulated. The general function must take two arguments and return a result. The first argument to this function is the current value of the accumulation. The second argument is the value of the current element in the sequence being accumulated.
Line 57 uses function for_each to apply a general function to every element in the range from v.begin() up to, but not including, v.end() in v. The general function should take the current element as an argument and should not modify that element. Function for_each requires its two iterator arguments to be at least input iterators.
Line 62 uses function transform to apply a general function to every element in the range from v.begin() up to, but not including, v.end() in v. The general function (the fourth argument) should take the current element as an argument, should not modify the element and should return the transformed value. Function TRansform requires its first two iterator arguments to be at least input iterators and its third argument to be at least an output iterator. The third argument specifies where the TRansformed values should be placed. Note that the third argument can equal the first. Another version of TRansform accepts five argumentsthe first two arguments are input iterators that specify a range of elements from one source container, the third argument is an input iterator that specifies the first element in another source container, the fourth argument is an output iterator that specifies where the transformed values should be placed and the last argument is a general function that takes two arguments. This version of transform takes one element from each of the two input sources and applies the general function to that pair of elements, then places the transformed value at the location specified by the fourth argument.
23.5.6. Basic Searching and Sorting Algorithms
Figure 23.31 demonstrates some basic searching and sorting capabilities of the Standard Library, including find, find_if, sort and binary_search.
Figure 23.31. Basic searching and sorting algorithms of the Standard Library.
(This item is displayed on pages 1165 - 1167 in the print version)
|
1 // Fig. 23.31: Fig23_31.cpp 2 // Standard Library search and sort algorithms. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // algorithm definitions 8 #include // vector class-template definition 9 #include 10 11 bool greater10( int value ); // predicate function prototype 12 13 int main() 14 { 15 const int SIZE = 10; 16 int a[ SIZE ] = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 }; 17 std::vector< int > v( a, a + SIZE ); // copy of a 18 std::ostream_iterator< int > output( cout, " " ); 19 20 cout << "Vector v contains: "; 21 std::copy( v.begin(), v.end(), output ); // display output vector 22 23 // locate first occurrence of 16 in v 24 std::vector< int >::iterator location; 25 location = std::find( v.begin(), v.end(), 16 ); 26 27 if ( location != v.end() ) // found 16 28 cout << " Found 16 at location " << ( location - v.begin() ); 29 else // 16 not found 30 cout << " 16 not found"; 31 32 // locate first occurrence of 100 in v 33 location = std::find( v.begin(), v.end(), 100 ); 34 35 if ( location != v.end() ) // found 100 36 cout << " Found 100 at location " << ( location - v.begin() ); 37 else // 100 not found 38 cout << " 100 not found"; 39 40 // locate first occurrence of value greater than 10 in v 41 location = std::find_if( v.begin(), v.end(), greater10 ); 42 43 if ( location != v.end() ) // found value greater than 10 44 cout << " The first value greater than 10 is " << *location 45 << " found at location " << ( location - v.begin() ); 46 else // value greater than 10 not found 47 cout << " No values greater than 10 were found"; 48 49 // sort elements of v 50 std::sort( v.begin(), v.end() ); 51 cout << " Vector v after sort: "; 52 std::copy( v.begin(), v.end(), output ); 53 54 // use binary_search to locate 13 in v 55 if ( std::binary_search( v.begin(), v.end(), 13 ) ) 56 cout << " 13 was found in v"; 57 else 58 cout << " 13 was not found in v"; 59 60 // use binary_search to locate 100 in v 61 if ( std::binary_search( v.begin(), v.end(), 100 ) ) 62 cout << " 100 was found in v"; 63 else 64 cout << " 100 was not found in v"; 65 66 cout << endl; 67 return 0; 68 } // end main 69 70 // determine whether argument is greater than 10 71 bool greater10( int value ) 72 { 73 return value > 10; 74 } // end function greater10
|
Line 25 uses function find to locate the value 16 in the range from v.begin() up to, but not including, v.end() in v. The function 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 33).
Line 41 uses function find_if to locate the first value in the range from v.begin() up to, but not including, v.end() in v for which the unary predicate function greater10 returns true. Function greater10 (defined at lines 7174) takes an integer and returns a bool value indicating whether the integer argument is greater than 10. Function find_if requires its two iterator arguments to be at least input iterators. The function 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.
Line 50 uses function sort to arrange the elements in the range from v.begin() up to, but not including, v.end() in v in ascending order. The function requires its two iterator arguments to be random-access iterators. A second version of this function takes a third argument that is a binary predicate function taking two arguments that are values in the sequence and returning a bool indicating the sorting orderif the return value is true, the two elements being compared are in sorted order.
Common Programming Error 23.5
|
Attempting to sort a container by using an iterator other than a random-access iterator is a compilation error. Function sort requires a random-access iterator. |
Line 55 uses function binary_search to determine whether the value 13 is in the range from v.begin() up to, but not including, v.end() in v. The sequence of values must be sorted in ascending order first. Function binary_search requires its two iterator arguments to be at least forward iterators. The function returns a bool indicating whether the value was found in the sequence. Line 61 demonstrates a call to function binary_search in which the value is not found. A second version of this function takes a fourth argument that is 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.
23.5.7. swap, iter_swap and swap_ranges
Figure 23.32 demonstrates algorithms swap, iter_swap and swap_ranges for swapping elements. Line 20 uses function swap to exchange two values. In this example, the first and second elements of array a are exchanged. The function takes as arguments references to the two values being exchanged.
Figure 23.32. Demonstrating swap, iter_swap and swap_ranges.
|
1 // Fig. 23.32: Fig23_32.cpp 2 // Standard Library algorithms iter_swap, swap and swap_ranges. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // algorithm definitions 8 #include 9 10 int main() 11 { 12 const int SIZE = 10; 13 int a[ SIZE ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 14 std::ostream_iterator< int > output( cout, " " ); 15 16 cout << "Array a contains: "; 17 std::copy( a, a + SIZE, output ); // display array a 18 19 // swap elements at locations 0 and 1 of array a 20 std::swap( a[ 0 ], a[ 1 ] ); 21 22 cout << " Array a after swapping a[0] and a[1] using swap: "; 23 std::copy( a, a + SIZE, output ); // display array a 24 25 // use iterators to swap elements at locations 0 and 1 of array a 26 std::iter_swap( &a[ 0 ], &a[ 1 ] ); // swap with iterators 27 cout << " Array a after swapping a[0] and a[1] using iter_swap: "; 28 std::copy( a, a + SIZE, output ); 29 30 // swap elements in first five elements of array a with 31 // elements in last five elements of array a 32 std::swap_ranges( a, a + 5, a + 5 ); 33 34 cout << " Array a after swapping the first five elements " 35 << "with the last five elements: "; 36 std::copy( a, a + SIZE, output ); 37 cout << endl; 38 return 0; 39 } // end main
|
Line 26 uses function iter_swap to exchange the two elements. The function takes two forward iterator arguments (in this case, pointers to elements of an array) and exchanges the values in the elements to which the iterators refer.
Line 32 uses function swap_ranges to exchange the elements in the range from a up to, but not including, a + 5 with the elements beginning at position a + 5. The function requires three forward iterator arguments. The first two arguments specify the range of elements in the first sequence that will be exchanged with the elements in the second sequence starting from the iterator in the third argument. In this example, the two sequences of values are in the same array, but the sequences can be from different arrays or containers.
23.5.8. copy_backward, merge, unique and reverse
Figure 23.33 demonstrates STL algorithms copy_backward, merge, unique and reverse. Line 28 uses function copy_backward to copy elements in the range from v1.begin() up to, but not including, v1.end() in v1, placing the elements in results by starting from the element before results.end() and working toward the beginning of the vector. The function returns an iterator positioned at the last element copied into the results (i.e., the beginning of results, because of the backward copy). The elements are placed in results in the same order as v1. This function requires three bidirectional iterator arguments (iterators that can be incremented and decremented to iterate forward and backward through a sequence, respectively). The main difference between copy and copy_backward is that the iterator returned from copy is positioned after the last element copied and the iterator returned from copy_backward is positioned at the last element copied (which is really the first element in the sequence). Also, copy requires two input iterators and an output iterator as argument.
Figure 23.33. Demonstrating copy_backward, merge, unique and reverse.
(This item is displayed on pages 1169 - 1170 in the print version)
|
1 // Fig. 23.33: Fig23_33.cpp 2 // Standard Library functions copy_backward, merge, unique and reverse. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // algorithm definitions 8 #include // vector class-template definition 9 #include // ostream_iterator 10 11 int main() 12 { 13 const int SIZE = 5; 14 int a1[ SIZE ] = { 1, 3, 5, 7, 9 }; 15 int a2[ SIZE ] = { 2, 4, 5, 7, 9 }; 16 std::vector< int > v1( a1, a1 + SIZE ); // copy of a1 17 std::vector< int > v2( a2, a2 + SIZE ); // copy of a2 18 std::ostream_iterator< int > output( cout, " " ); 19 20 cout << "Vector v1 contains: "; 21 std::copy( v1.begin(), v1.end(), output ); // display vector output 22 cout << " Vector v2 contains: "; 23 std::copy( v2.begin(), v2.end(), output ); // display vector output 24 25 std::vector< int > results( v1.size() ); 26 27 // place elements of v1 into results in reverse order 28 std::copy_backward( v1.begin(), v1.end(), results.end() ); 29 cout << " After copy_backward, results contains: "; 30 std::copy( results.begin(), results.end(), output ); 31 32 std::vector< int > results2( v1.size() + v2.size() ); 33 34 // merge elements of v1 and v2 into results2 in sorted order 35 std::merge( v1.begin(), v1.end(), v2.begin(), v2.end(), 36 results2.begin() ); 37 38 cout << " After merge of v1 and v2 results2 contains: "; 39 std::copy( results2.begin(), results2.end(), output ); 40 41 // eliminate duplicate values from results2 42 std::vector< int >::iterator endLocation; 43 endLocation = std::unique( results2.begin(), results2.end() ); 44 45 cout << " After unique results2 contains: "; 46 std::copy( results2.begin(), endLocation, output ); 47 48 cout << " Vector v1 after reverse: "; 49 std::reverse( v1.begin(), v1.end() ); // reverse elements of v1 50 std::copy( v1.begin(), v1.end(), output ); 51 cout << endl; 52 return 0; 53 } // end main
|
Lines 3536 use function merge to combine two sorted ascending sequences of values into a third sorted ascending sequence. The function requires five iterator arguments. The first four must be at least input iterators and the last must be at least an output iterator. The first two arguments specify the range of elements in the first sorted sequence (v1), the second two arguments specify the range of elements in the second sorted sequence (v2) and the last argument specifies the starting location in the third sequence (results2) where the elements will be merged. A second version of this function takes as its sixth argument a binary predicate function that specifies the sorting order.
Note that line 32 creates vector results2 with the number of elements v1.size() + v2.size(). Using the merge function as shown here requires that the sequence where the results are stored be at least the size of the two sequences being merged. If you do not want to allocate the number of elements for the resulting sequence before the merge operation, you can use the following statements:
std::vector< int > results2(); std::merge ( v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter( results2 ) );
The argument std::back_inserter( results2 ) uses function template back_inserter (header file ) for the container results2. A back_inserter calls the container's default push_back function to insert an element at the end of the container. More importantly, if an element is inserted into a container that has no more space available, the container grows in size. Thus, the number of elements in the container does not have to be known in advance. There are two other insertersfront_inserter (to insert an element at the beginning of a container specified as its argument) and inserter (to insert an element before the iterator supplied as its second argument in the container supplied as its first argument).
Line 43 uses function unique on the sorted sequence of elements in the range from results2.begin() up to, but not including, results2.end() in results2. After this function is applied to a sorted sequence with duplicate values, only a single copy of each value remains in the sequence. The function takes two arguments that must be at least forward iterators. The function returns an iterator positioned after the last element in the sequence of unique values. The values of all elements in the container after the last unique value are undefined. A second version of this function takes as a third argument a binary predicate function specifying how to compare two elements for equality.
Line 49 uses function reverse to reverse all the elements in the range from v1.begin() up to, but not including, v1.end() in v1. The function takes two arguments that must be at least bidirectional iterators.
23.5.9. inplace_merge, unique_copy and reverse_copy
Figure 23.34 demonstrates STL algorithms inplace_merge, unique_copy and reverse_copy. Line 24 uses function inplace_merge to merge two sorted sequences of elements in the same container. In this example, the elements from v1.begin() up to, but not including, v1.begin() + 5 are merged with the elements from v1.begin() + 5 up to, but not including, v1.end(). This function requires its three iterator arguments to be at least bidirectional iterators. A second version of this function takes as a fourth argument a binary predicate function for comparing elements in the two sequences.
Figure 23.34. Demonstrating inplace_merge, unique_copy and reverse_copy.
(This item is displayed on pages 1171 - 1172 in the print version)
|
1 // Fig. 23.34: Fig23_34.cpp 2 // Standard Library algorithms inplace_merge, 3 // reverse_copy and unique_copy. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include // algorithm definitions 9 #include // vector class-template definition 10 #include // back_inserter definition 11 12 int main() 13 { 14 const int SIZE = 10; 15 int a1[ SIZE ] = { 1, 3, 5, 7, 9, 1, 3, 5, 7, 9 }; 16 std::vector< int > v1( a1, a1 + SIZE ); // copy of a 17 std::ostream_iterator< int > output( cout, " " ); 18 19 cout << "Vector v1 contains: "; 20 std::copy( v1.begin(), v1.end(), output ); 21 22 // merge first half of v1 with second half of v1 such that 23 // v1 contains sorted set of elements after merge 24 std::inplace_merge( v1.begin(), v1.begin() + 5, v1.end() ); 25 26 cout << " After inplace_merge, v1 contains: "; 27 std::copy( v1.begin(), v1.end(), output ); 28 29 std::vector< int > results1; 30 31 // copy only unique elements of v1 into results1 32 std::unique_copy( 33 v1.begin(), v1.end(), std::back_inserter( results1 ) ); 34 cout << " After unique_copy results1 contains: "; 35 std::copy( results1.begin(), results1.end(), output ); 36 37 std::vector< int > results2; 38 39 // copy elements of v1 into results2 in reverse order 40 std::reverse_copy( 41 v1.begin(), v1.end(), std::back_inserter( results2 ) ); 42 cout << " After reverse_copy, results2 contains: "; 43 std::copy( results2.begin(), results2.end(), output ); 44 cout << endl; 45 return 0; 46 } // end main
|
Lines 3233 use function unique_copy to make a copy of all the unique elements in the sorted sequence of values from v1.begin() up to, but not including, v1.end(). The copied elements are placed into vector results1. The first two arguments must be at least input iterators and the last must be at least an output iterator. In this example, we did not preallocate enough elements in results1 to store all the elements copied from v1. Instead, we use function back_inserter (defined in header file ) to add elements to the end of v1. The back_inserter uses class vector's capability to insert elements at the end of the vector. Because the back_inserter inserts an element rather than replacing an existing element's value, the vector is able to grow to accommodate additional elements. A second version of the unique_copy function takes as a fourth argument a binary predicate function for comparing elements for equality.
Lines 4041 use function reverse_copy to make a reversed copy of the elements in the range from v1.begin() up to, but not including, v1.end(). The copied elements are inserted into results2 using a back_inserter object to ensure that the vector can grow to accommodate the appropriate number of elements copied. Function reverse_copy requires its first two iterator arguments to be at least bidirectional iterators and its third to be at least an output iterator.
23.5.10. Set Operations
Figure 23.35 demonstrates Standard Library functions includes, set_difference, set_intersection, set_symmetric_difference and set_union for manipulating sets of sorted values. To demonstrate that Standard Library functions can be applied to arrays and containers, this example uses only arrays (remember, a pointer into an array is a randomaccess iterator).
Figure 23.35. set operations of the Standard Library.
(This item is displayed on pages 1173 - 1175 in the print version)
|
1 // Fig. 23.35: Fig23_35.cpp 2 // Standard Library algorithms includes, set_difference, 3 // set_intersection, set_symmetric_difference and set_union. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include // algorithm definitions 9 #include // ostream_iterator 10 11 int main() 12 { 13 const int SIZE1 = 10, SIZE2 = 5, SIZE3 = 20; 14 int a1[ SIZE1 ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 15 int a2[ SIZE2 ] = { 4, 5, 6, 7, 8 }; 16 int a3[ SIZE2 ] = { 4, 5, 6, 11, 15 }; 17 std::ostream_iterator< int > output( cout, " " ); 18 19 cout << "a1 contains: "; 20 std::copy( a1, a1 + SIZE1, output ); // display array a1 21 cout << " a2 contains: "; 22 std::copy( a2, a2 + SIZE2, output ); // display array a2 23 cout << " a3 contains: "; 24 std::copy( a3, a3 + SIZE2, output ); // display array a3 25 26 // determine whether set a2 is completely contained in a1 27 if ( std::includes( a1, a1 + SIZE1, a2, a2 + SIZE2 ) ) 28 cout << " a1 includes a2"; 29 else 30 cout << " a1 does not include a2"; 31 32 // determine whether set a3 is completely contained in a1 33 if ( std::includes( a1, a1 + SIZE1, a3, a3 + SIZE2 ) ) 34 cout << " a1 includes a3"; 35 else 36 cout << " a1 does not include a3"; 37 38 int difference[ SIZE1 ]; 39 40 // determine elements of a1 not in a2 41 int *ptr = std::set_difference( a1, a1 + SIZE1, 42 a2, a2 + SIZE2, difference ); 43 cout << " set_difference of a1 and a2 is: "; 44 std::copy( difference, ptr, output ); 45 46 int intersection[ SIZE1 ]; 47 48 // determine elements in both a1 and a2 49 ptr = std::set_intersection( a1, a1 + SIZE1, 50 a2, a2 + SIZE2, intersection ); 51 cout << " set_intersection of a1 and a2 is: "; 52 std::copy( intersection, ptr, output ); 53 54 int symmetric_difference[ SIZE1 + SIZE2 ]; 55 56 // determine elements of a1 that are not in a2 and 57 // elements of a2 that are not in a1 58 ptr = std::set_symmetric_difference( a1, a1 + SIZE1, 59 a3, a3 + SIZE2, symmetric_difference ); 60 cout << " set_symmetric_difference of a1 and a3 is: "; 61 std::copy( symmetric_difference, ptr, output ); 62 63 int unionSet[ SIZE3 ]; 64 65 // determine elements that are in either or both sets 66 ptr = std::set_union( a1, a1 + SIZE1, a3, a3 + SIZE2, unionSet ); 67 cout << " set_union of a1 and a3 is: "; 68 std::copy( unionSet, ptr, output ); 69 cout << endl; 70 return 0; 71 } // end main
|
Lines 27 and 33 call function includes in the conditions of if statements. Function includes compares two sets of sorted values to determine whether every element of the second set is in the first set. If so, includes returns TRue; otherwise, it returns false. The first two iterator arguments must be at least input iterators and must describe the first set of values. In line 27, the first set consists of the elements from a1 up to, but not including, a1 + SIZE1. The last two iterator arguments must be at least input iterators and must describe the second set of values. In this example, the second set consists of the elements from a2 up to, but not including, a2 + SIZE2. A second version of function includes takes a fifth argument that is a binary predicate function for comparing elements for equality.
Lines 4142 use function set_difference to find the elements from the first set of sorted values that are not in the second set of sorted values (both sets of values must be in ascending order). The elements that are different are copied into the fifth argument (in this case, the array difference). The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store a copy of the values that are different. The function returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of function set_difference takes a sixth argument that is a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
Lines 4950 use function set_intersection to determine the elements from the first set of sorted values that are in the second set of sorted values (both sets of values must be in ascending order). The elements common to both sets are copied into the fifth argument (in this case, array intersection). The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store a copy of the values that are the same. The function returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of function set_intersection takes a sixth argument that is a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
Lines 5859 use function set_symmetric_difference to determine the elements in the first set that are not in the second set and the elements in the second set that are not in the first set (both sets must be in ascending order). The elements that are different are copied from both sets into the fifth argument (the array symmetric_difference). The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store a copy of the values that are different. The function returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of function set_symmetric_difference takes a sixth argument that is a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
Line 66 uses function set_union to create a set of all the elements that are in either or both of the two sorted sets (both sets of values must be in ascending order). The elements are copied from both sets into the fifth argument (in this case the array unionSet). Elements that appear in both sets are only copied from the first set. The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store the copied elements. The function returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of function set_union takes a sixth argument that is a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
23.5.11. lower_bound, upper_bound and equal_range
Figure 23.36 demonstrates Standard Library functions lower_bound, upper_bound and equal_range. Line 24 uses function lower_bound 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 function returns a forward iterator pointing to the position at which the insert can occur. A second version of function lower_bound takes as a fourth argument a binary predicate function indicating the order in which the elements were originally sorted.
Figure 23.36. Algorithms lower_bound, upper_bound and equal_range.
(This item is displayed on pages 1176 - 1178 in the print version)
|
1 // Fig. 23.36: Fig23_36.cpp 2 // Standard Library functions lower_bound, upper_bound and 3 // equal_range for a sorted sequence of values. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include // algorithm definitions 9 #include // vector class-template definition 10 #include // ostream_iterator 11 12 int main() 13 { 14 const int SIZE = 10; 15 int a1[ SIZE ] = { 2, 2, 4, 4, 4, 6, 6, 6, 6, 8 }; 16 std::vector< int > v( a1, a1 + SIZE ); // copy of a1 17 std::ostream_iterator< int > output( cout, " " ); 18 19 cout << "Vector v contains: "; 20 std::copy( v.begin(), v.end(), output ); 21 22 // determine lower-bound insertion point for 6 in v 23 std::vector< int >::iterator lower; 24 lower = std::lower_bound( v.begin(), v.end(), 6 ); 25 cout << " Lower bound of 6 is element " 26 << ( lower - v.begin() ) << " of vector v"; 27 28 // determine upper-bound insertion point for 6 in v 29 std::vector< int >::iterator upper; 30 upper = std::upper_bound( v.begin(), v.end(), 6 ); 31 cout << " Upper bound of 6 is element " 32 << ( upper - v.begin() ) << " of vector v"; 33 34 // use equal_range to determine both the lower- and 35 // upper-bound insertion points for 6 36 std::pair< std::vector< int >::iterator, 37 std::vector< int >::iterator > eq; 38 eq = std::equal_range( v.begin(), v.end(), 6 ); 39 cout << " Using equal_range: Lower bound of 6 is element " 40 << ( eq.first - v.begin() ) << " of vector v"; 41 cout << " Upper bound of 6 is element " 42 << ( eq.second - v.begin() ) << " of vector v"; 43 cout << " Use lower_bound to locate the first point " 44 << "at which 5 can be inserted in order"; 45 46 // determine lower-bound insertion point for 5 in v 47 lower = std::lower_bound( v.begin(), v.end(), 5 ); 48 cout << " Lower bound of 5 is element " 49 << ( lower - v.begin() ) << " of vector v"; 50 cout << " Use upper_bound to locate the last point " 51 << "at which 7 can be inserted in order"; 52 53 // determine upper-bound insertion point for 7 in v 54 upper = std::upper_bound( v.begin(), v.end(), 7 ); 55 cout << " Upper bound of 7 is element " 56 << ( upper - v.begin() ) << " of vector v"; 57 cout << " Use equal_range to locate the first and " 58 << "last point at which 5 can be inserted in order"; 59 60 // use equal_range to determine both the lower- and 61 // upper-bound insertion points for 5 62 eq = std::equal_range( v.begin(), v.end(), 5 ); 63 cout << " Lower bound of 5 is element " 64 << ( eq.first - v.begin() ) << " of vector v"; 65 cout << " Upper bound of 5 is element " 66 << ( eq.second - v.begin() ) << " of vector v" << endl; 67 return 0; 68 } // end main
|
Line 30 uses function upper_bound 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 function returns a forward iterator pointing to the position at which the insert can occur. A second version of function upper_bound takes as a fourth argument a binary predicate function indicating the order in which the elements were originally sorted.
Line 38 uses function equal_range to return a pair of forward iterators containing the combined results of performing both a lower_bound and an upper_bound operation. The first two iterator arguments must be at least forward iterators. The third argument is the value for which to locate the equal range. The function returns a pair of forward iterators for the lower bound (eq.first) and upper bound (eq.second), respectively.
Functions lower_bound, upper_bound and equal_range are often used to locate insertion points in sorted sequences. Line 47 uses lower_bound to locate the first point at which 5 can be inserted in order in v. Line 54 uses upper_bound to locate the last point at which 7 can be inserted in order in v. Line 62 uses equal_range to locate the first and last points at which 5 can be inserted in order in v.
23.5.12. Heapsort
Figure 23.37 demonstrates the Standard Library functions for performing the heapsort sorting algorithm. Heapsort is a sorting algorithm in which an array of elements is arranged into a special binary tree called a heap. The key features of a heap are that the largest element is always at the top of the heap and the values of the children of any node in the binary tree are always less than or equal to that node's value. A heap arranged in this manner is often called a maxheap. Heapsort is discussed in detail in computer science courses called "Data Structures" and "Algorithms."
Figure 23.37. Using Standard Library functions to perform a heapsort.
(This item is displayed on pages 1178 - 1180 in the print version)
|
1 // Fig. 23.37: Fig23_37.cpp 2 // Standard Library algorithms push_heap, pop_heap, 3 // make_heap and sort_heap. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include 9 #include 10 #include 11 12 int main() 13 { 14 const int SIZE = 10; 15 int a[ SIZE ] = { 3, 100, 52, 77, 22, 31, 1, 98, 13, 40 }; 16 std::vector< int > v( a, a + SIZE ); // copy of a 17 std::vector< int > v2; 18 std::ostream_iterator< int > output( cout, " " ); 19 20 cout << "Vector v before make_heap: "; 21 std::copy( v.begin(), v.end(), output ); 22 23 std::make_heap( v.begin(), v.end() ); // create heap from vector v 24 cout << " Vector v after make_heap: "; 25 std::copy( v.begin(), v.end(), output ); 26 27 std::sort_heap( v.begin(), v.end() ); // sort elements with sort_heap 28 cout << " Vector v after sort_heap: "; 29 std::copy( v.begin(), v.end(), output ); 30 31 // perform the heapsort with push_heap and pop_heap 32 cout << " Array a contains: "; 33 std::copy( a, a + SIZE, output ); // display array a 34 cout << endl; 35 36 // place elements of array a into v2 and 37 // maintain elements of v2 in heap 38 for ( int i = 0; i < SIZE; i++ ) 39 { 40 v2.push_back( a[ i ] ); 41 std::push_heap( v2.begin(), v2.end() ); 42 cout << " v2 after push_heap(a[" << i << "]): "; 43 std::copy( v2.begin(), v2.end(), output ); 44 } // end for 45 46 cout << endl; 47 48 // remove elements from heap in sorted order 49 for ( unsigned int j = 0; j < v2.size(); j++ ) 50 { 51 cout << " v2 after " << v2[ 0 ] << " popped from heap "; 52 std::pop_heap( v2.begin(), v2.end() - j ); 53 std::copy( v2.begin(), v2.end(), output ); 54 } // end for 55 56 cout << endl; 57 return 0; 58 } // end main
|
Line 23 uses function make_heap to take a sequence of values in the range from v.begin() up to, but not including, v.end() and create a heap that can be used to produce a sorted sequence. The two iterator arguments must be random-access iterators, so this function will work only with arrays, vectors and deques. A second version of this function takes as a third argument a binary predicate function for comparing values.
Line 27 uses function sort_heap to sort a sequence of values in the range from v.begin() up to, but not including, v.end() that are already arranged in a heap. The two iterator arguments must be random-access iterators. A second version of this function takes as a third argument a binary predicate function for comparing values.
Line 41 uses function push_heap to add a new value into a heap. We take one element of array a at a time, append that element to the end of vector v2 and perform the push_heap operation. If the appended element is the only element in the vector, the vector is already a heap. Otherwise, function push_heap rearranges the elements of the vector into a heap. Each time push_heap is called, it assumes that the last element currently in the vector (i.e., the one that is appended before the push_heap function call) is the element being added to the heap and that all other elements in the vector are already arranged as a heap. The two iterator arguments to push_heap must be random-access iterators. A second version of this function takes as a third argument a binary predicate function for comparing values.
Line 52 uses pop_heap to remove the top heap element. This function assumes that the elements in the range specified by its two random-access iterator arguments are already a heap. Repeatedly removing the top heap element results in a sorted sequence of values. Function pop_heap swaps the first heap element (v2.begin(), in this example) with the last heap element (the element before v2.end() - i, in this example), then ensures that the elements up to, but not including, the last element still form a heap. Notice in the output that, after the pop_heap operations, the vector is sorted in ascending order. A second version of this function takes as a third argument a binary predicate function for comparing values.
23.5.13. min and max
Algorithms min and max determine the minimum of two elements and the maximum of two elements, respectively. Figure 23.38 demonstrates min and max for int and char values.
Figure 23.38. Algorithms min and max.
|
1 // Fig. 23.38: Fig23_38.cpp 2 // Standard Library algorithms min and max. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include 8 9 int main() 10 { 11 cout << "The minimum of 12 and 7 is: " << std::min( 12, 7 ); 12 cout << " The maximum of 12 and 7 is: " << std::max( 12, 7 ); 13 cout << " The minimum of 'G' and 'Z' is: " << std::min( 'G', 'Z' ); 14 cout << " The maximum of 'G' and 'Z' is: " << std::max( 'G', 'Z' ); 15 cout << endl; 16 return 0; 17 } // end main
|
23.5.14. STL Algorithms Not Covered in This Chapter
Figure 23.39 summarizes the STL algorithms that are not covered in this chapter.
|
Algorithm |
Description |
|---|---|
|
inner_product |
Calculate the sum of the products of two sequences by taking corresponding elements in each sequence, multiplying those elements and adding the result to a total. |
|
adjacent_difference |
Beginning with the second element in a sequence, calculate the difference (using operator ) between the current and previous elements, and store the result. The first two input iterator arguments indicate the range of elements in the container and the third indicates where the results should be stored. A second version of this algorithm takes as a fourth argument a binary function to perform a calculation between the current element and the previous element. |
|
partial_sum |
Calculate a running total (using operator +) of the values in a sequence. The first two input iterator arguments indicate the range of elements in the container and the third indicates where the results should be stored. A second version of this algorithm takes as a fourth argument a binary function that performs a calculation between the current value in the sequence and the running total. |
|
nth_element |
Use three random-access iterators to partition a range of elements. The first and last arguments represent the range of elements. The second argument is the partitioning element's location. After this algorithm executes, all elements before the partitioning element are less than that element and all elements after the partitioning element are greater than or equal to that element. A second version of this algorithm takes as a fourth argument a binary comparison function. |
|
partition |
This algorithm is similar to nth_element, but it requires less powerful bidirectional iterators, making it more flexible than nth_element. Algorithm partition requires two bidirectional iterators indicating the range of elements to partition. The third element is a unary predicate function that helps partition the elements so that all elements in the sequence for which the predicate is true are to the left (toward the beginning of the sequence) of all elements for which the predicate is false. A bidirectional iterator is returned indicating the first element in the sequence for which the predicate returns false. |
|
stable_partition |
This algorithm is similar to partition except that elements for which the predicate function returns TRue are maintained in their original order and elements for which the predicate function returns false are maintained in their original order. |
|
next_permutation |
Next lexicographical permutation of a sequence. |
|
prev_permutation |
Previous lexicographical permutation of a sequence. |
|
rotate |
Use three forward iterator arguments to rotate the sequence indicated by the first and last argument by the number of positions indicated by subtracting the first argument from the second argument. For example, the sequence 1, 2, 3, 4, 5 rotated by two positions would be 4, 5, 1, 2, 3. |
|
rotate_copy |
This algorithm is identical to rotate except that the results are stored in a separate sequence indicated by the fourth argumentan output iterator. The two sequences must have the same number of elements. |
|
adjacent_find |
This algorithm returns an input iterator indicating the first of two identical adjacent elements in a sequence. If there are no identical adjacent elements, the iterator is positioned at the end of the sequence. |
|
search |
This algorithm searches for a subsequence of elements within a sequence of elements and, if such a subsequence is found, returns a forward iterator that indicates the first element of that subsequence. If there are no matches, the iterator is positioned at the end of the sequence to be searched. |
|
search_n |
This algorithm searches a sequence of elements looking for a subsequence in which the values of a specified number of elements have a particular value and, if such a subsequence is found, returns a forward iterator that indicates the first element of that subsequence. If there are no matches, the iterator is positioned at the end of the sequence to be searched. |
|
partial_sort |
Use three random-access iterators to sort part of a sequence. The first and last arguments indicate the sequence of elements. The second argument indicates the ending location for the sorted part of the sequence. By default, elements are ordered using operator < (a binary predicate function can also be supplied). The elements from the second argument iterator to the end of the sequence are in an undefined order. |
|
partial_sort_copy |
Use two input iterators and two random-access iterators to sort part of the sequence indicated by the two input iterator arguments. The results are stored in the sequence indicated by the two random-access iterator arguments. By default, elements are ordered using operator < (a binary predicate function can also be supplied). The number of elements sorted is the smaller of the number of elements in the result and the number of elements in the original sequence. |
|
stable_sort |
The algorithm is similar to sort except that all equal elements are maintained in their original order. |