Line 16 defines a 10-element array of char values. Line 17 uses the fill algorithm to place the character '5' in every element of chars from chars.begin() up to, but not including, chars.end(). 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). Forward iterators are required here (rather than output iterators) because the iterators must be compared to determine when the end of the sequence has been reached.

Line 24 uses the fill_n algorithm to place the character 'A' in the first five elements of chars. The iterator supplied as the first argument must be at least an output iterator (i.e., it can be used to write into 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 30 uses the generate algorithm to place the result of a call to generator function nextLetter in every element of 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 (lines 10–13) defines a static local char variable named letter and initializes it to 'A'. The statement in line 12 returns the current value of letter then postincrements its value for use in the next call to the function.

Line 36 uses the generate_n algorithm to place the result of a call to generator function nextLetter in five elements of chars, starting from chars.begin(). The iterator supplied as the first argument must be at least an output iterator.

Lines 44–49 once again use the generate_n algorithm to place the result of a call to a generator function into elements of chars, starting from chars.begin(). In this case, the generator function is implemented as a lambda (lines 45–48) with no arguments—as specified by the empty parentheses—and returns a generated letter. For lambdas with no arguments, the parameter lists’ paretheses are not required. The compiler infers from the return statement that the lambda’s return type is char.

When you look at the Standard Library algorithms documentation for algorithms that can receive function pointers as arguments, you’ll notice that the corresponding parameters do not show pointer declarations. Such parameters can actually receive as arguments function pointers, function objects (Section 16.5) or lambda expressions (Section 16.3). For this reason, the Standard Library declares such parameters using names that represent the parameter’s purpose.

For example, generate’s prototype is listed in the C++ standard document as

template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
  Generator gen);

indicating that generate expects as arguments ForwardIterators representing the range of elements to process and a Generator function. The standard explains that the algorithm calls the Generator function to obtain a value for each element in the range specified by the ForwardIterators. The standard also specifies that the Generator must take no arguments and return a value that can be assigned to the element type.

Similar documentation is provided for each algorithm that can receive a function pointer, function object or lambda expression. In most of this chapter’s examples, as we present each algorithm, we specify the requirements for such parameters.

Line 24 uses the C++14 version of the equal algorithm to compare two sequences of values for equality. The second sequence must contain at least as many elements as the first—equal returns false if the sequences are not of the same length. The == operator (whether built-in or overloaded) performs the element comparisons. In this example, the elements in a1 from a1.cbegin() up to, but not including, a1.cend() are compared to the elements in a2 starting from a2.cbegin() up to, but not including, a2.cend(). In this example, a1 and a2 are equal. The four iterator arguments must be at least input iterators (i.e., they can be used for input from a sequence in the forward direction). Line 28 uses function equal to compare a1 and a3, which are not equal.

Each version of equal also has an overloaded version that takes a binary predicate function as the last 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 32–33 call the C++14 version of the mismatch algorithm to compare two sequences of values. The algorithm returns a pair of iterators indicating the location in each sequence of the first mismatched elements. If all the elements match, the two iterators in the pair are equal to the end iterator for each sequence. The four iterator arguments must be at least input iterators. We infer the type of the pair object location with C++11’s auto keyword (line 32). Line 35 determines the actual location of the mismatch in the arrays with the expression location.first - a1.begin(), which evaluates to the number of elements between the iterators in the returned pair (this is analogous to pointer arithmetic; Chapter 8). This corresponds to the element number in this example, because the comparison is performed from the beginning of each array. As with equal, there are overloaded versions of mismatch take a binary predicate function as the last parameter.

Lines 32–33 use an equal sign (=) rather than braces to initialize the variable location. This is due to a known limitation with variables that are declared auto and initialized with braced initializers. There is a proposal to fix this limitation in C++17.1

Lines 43–44 use the lexicographical_compare algorithm to compare the contents of two char built-in arrays. This algorithm’s four iterator arguments must be at least input iterators. As you know, pointers into built-in 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. Once again, we use the C++11 begin and end functions to determine the range of elements for each built-in array. While iterating through the sequences, if there is a mismatch between the corresponding elements in the sequences and the element in the first sequence is less than the corresponding element in the second sequence, the algorithm returns true; otherwise, the algorithm returns false. This algorithm can be used to arrange sequences lexicographically. Typically, such sequences contain strings.

Line 19 uses the remove algorithm to eliminate from a1 all elements with the value 10 in the range from a1.begin() up to, but not including, a1.end(). The first two iterator arguments must be forward iterators. This algorithm does not modify the number of elements in the container or destroy the eliminated elements, but it does move all elements that are not eliminated toward the beginning of the container. The algorithm returns an iterator positioned after the last element that was not removed. Elements from the iterator position to the end of the container have unspecified values and should not be used other than to assign them new values. Line 21 outputs the elements of a1 from a1.begin() up to but not including newEnd.

Line 29 uses the remove_copy algorithm to copy all elements from a2 that do not have the value 10 in the range from a2.cbegin() up to, but not including, a2.cend(). 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 written into into the destination container. This algorithm returns an iterator positioned after the last element copied into c. Line 31 outputs all of c’s elements.

Lines 38–39 use the remove_if algorithm to delete from a3 all those elements in the range from a3.begin() up to, but not including, a3.end() for which a unary predicate function (in this case, the lambda at line 39) returns true—a unary predicate function must receive one parameter and return a bool value. The lambda

[](auto x){return x > 9;}

returns true if the value passed to it is greater than 9; otherwise, the lambda returns false. The compiler uses type inference for both the lambda’s parameter and return types:

• We’re processing an array of ints, so the compiler infers the lambda’s parameter type as int.

• The lambda returns a condition’s result, so the compiler infers the lambda’s return type as bool.

The iterators supplied as the first two arguments must be forward iterators. This algorithm does not modify the number of elements in the container, but it does move to the beginning of the container all elements that are not removed. This algorithm returns an iterator positioned after the last element that was not removed. All elements from the iterator position to the end of the container have undefined values and should not be used. Line 41 outputs the elements of a3 from a3.begin() up to but not including newEnd.

Lines 51–52 use the remove_copy_if algorithm to copy the elements from a4 in the range from a4.cbegin() up to, but not including, a4.cend() for which a unary predicate function (the lambda at line 52) returns true. The elements are placed in the array c2, starting at 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 written into to the destination container. This algorithm returns an iterator positioned after the last element copied into c2. Line 55 outputs the entire contents of c2.

Line 19 uses the replace algorithm to replace all elements with the value 10 in the range a1.begin() up to, but not including, a1.end() 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 29 uses the replace_copy algorithm to copy all elements in the range a2.cbegin() up to, but not including, a2.cend(), 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 written into to the destination container. This function returns an iterator positioned after the last element copied into c1.

Line 38 uses the replace_if algorithm to replace all those elements from a3.begin() up to, but not including, a3.end() for which a unary predicate function returns true—the lambda specified as the third argument 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.

Lines 50–51 use the replace_copy_if algorithm to copy all elements from a4.cbegin() up to, but not including, a4.cend(). Elements for which a unary predicate function returns true—again for values greater than 9—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 written into to the destination container. This algorithm returns an iterator positioned after the last element copied into c2.

Line 21 uses the C++11 shuffle algorithm to reorder randomly the elements in the range a1.begin() up to, but not including, a1.end(). This algorithm takes two random-access iterator arguments and a C++11 random-number-generator engine. Line 20

default_random_engine randomEngine{random_device{}()};

creates a default_random_engine using a C++11 random_device object to seed the random-number generator—typically with a nondeterministic seed (i.e., a seed that cannot be predicted). In the expression

random_device{}()

the braces initialize the random_device object and the parentheses call its overloaded parentheses operator to get the seed. Line 23 displays the shuffled results.

Line 30 uses the count algorithm to count the elements with the value 8 in the range a2.cbegin() up to, but not including, a2.cend(). This algorithm requires its two iterator arguments to be at least input iterators.

Line 34 uses the count_if algorithm to count elements in the range from a2.cbegin() up to, but not including, a2.cend() for which a unary predicate function returns true—once again we used a lambda to define a unary predicate that returns true for a value greater than 9. Algorithm count_if requires its two iterator arguments to be at least input iterators.

Line 39 uses the min_element algorithm to locate the smallest element in the range from a2.cbegin() up to, but not including, a2.cend(). The algorithm returns a forward iterator located at the first smallest element, or a2.end() if the range is empty. The algorithm’s two iterator arguments must be at least forward iterators. An overloaded version of this algorithm receives as its third argument a binary predicate function that compares two elements in the sequence and returns the bool value true if the first argument is less than the second.

Line 43 uses the max_element algorithm to locate the largest element in the range from a2.cbegin() up to, but not including, a2.cend(). The algorithm returns a forward iterator located at the first largest element. The algorithm’s two iterator arguments must be at least forward iterators. An overloaded version of this algorithm receives as its third argument a binary predicate function that compares two elements in the sequence and returns the bool value true if the first argument is less than the second.

Line 46 uses the C++11 minmax_element algorithm to locate both the smallest and largest elements in the range from a2.cbegin() up to, but not including, a2.cend(). The algorithm returns a pair of forward iterators located at the smallest and largest elements, respectively. If there are duplicate smallest or largest elements, the iterators are located at the first smallest and last largest values. The algorithm’s two iterator arguments must be at least forward iterators. A second version of this algorithm takes as its third argument a binary predicate function that compares the elements in the sequence. The binary function takes two arguments and returns the bool value true if the first argument is less than the second.

Line 53 uses the accumulate algorithm (the template of which is in header <numeric>) to sum the values in the range from a1.cbegin() up to, but not including, a1.cend(). The algorithm’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 algorithm 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. The function returns the result of the accumulation.

Lines 58–59 use the transform algorithm to apply a general function to every element in the range from a1.cbegin() up to, but not including, a1.cend(). The general function (the fourth argument) should take the current element as an argument, must not modify the element and should return the transformed value. Algorithm 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.

An overloaded version of transform accepts five arguments—the 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 and returns a result. 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.

Line 18 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’s either positioned at the first element containing the value or indicates the end of the sequence (as is the case in line 28).

Throughout this example, we test multiple times whether elements in the array a are greater than 10. You can store a lambda in a variable, as in line 38:

auto isGreaterThan10 = [](auto x){return x > 10;};

This variable can then be used at a later time to pass the lambda to other functions, as in lines 41, 73, 81, 89 and 97. You can also use the variable like a function name to invoke the lambda, as in

isGreaterThan10(5)

which returns false.

Line 41 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 a unary predicate function returns true—in this case, the unary predicate function is the lambda

[](auto x){return x > 10;}

that’s stored in the variable isGreaterThan10. The compiler infers parameter x’s type as int (because the array stores ints) and infers the return type as bool because the lambda returns the value of a condition. 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.

Line 52 uses the sort algorithm to arrange the elements in the range from a.begin() up to, but not including, a.end() in ascending order. This algorithm requires its two iterator arguments to be random-access iterators—so the algorithm can be used with built-in arrays and the Standard Library containers array, vector and deque. An overloaded version of this algorithm has a third argument that’s a binary predicate function taking two arguments and returning a bool indicating the sorting order. The predicate compares two values from the sequence being sorted. If the return value is true, the two elements are already in sorted order; otherwise, the two elements need to be reordered in the sequence.

Line 57 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 65 demonstrates a call to binary_search in which the value is not found. An overloaded version of this algorithm receives as a fourth argument a binary predicate function with 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. If you need to know the location of the search key in the container, use the lower_bound or find algorithms rather than binary_search.

Line 73 uses the all_of algorithm to determine whether the unary predicate function (the lambda stored in isGreaterThan10) 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.

Line 81 uses the any_of algorithm to determine whether the unary predicate function (the lambda stored in isGreaterThan10) 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.

Line 89 uses the none_of algorithm to determine whether the unary predicate function (the lambda stored in isGreaterThan10) 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.

Line 97 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 (the lambda stored in isGreaterThan10) 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.

Line 17 uses the swap algorithm 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.

Line 23 uses function iter_swap to exchange the two elements. The function takes two forward iterator arguments (in this case, iterators to elements of an array) and exchanges the values in the elements to which the iterators refer.

Line 29 uses function swap_ranges to exchange the elements from a.begin() up to, but not including, a.begin() + 5 with the elements beginning at position a.begin() + 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. The sequences must not overlap. The destination sequence must be large enough to contain all the elements of the ranges being swapped.

Line 23 uses the copy_backward algorithm to copy elements in the range from a1.cbegin() up to, but not including, a1.cend(), placing the elements in results by starting from the element before results.end() and working toward the beginning of the array. The algorithm returns an iterator positioned at the last element copied into the results (i.e., the beginning of results, because of the backward copy). Though they’re copied in reverse order, the elements are placed in results in the same order as a1. This algorithm requires three bidirectional iterator arguments (iterators that can be incremented and decremented to iterate forward and backward through a sequence, respectively).

One difference between copy_backward and copy is that the iterator returned from copy is positioned after the last element copied and the one returned from copy_backward is positioned at the last element copied (i.e., the first element in the sequence). Also, copy_backward can manipulate overlapping ranges of elements in a container as long as the first element to copy is not in the destination range of elements.

In addition to copy and copy_backward, C++11’s move and move_backward algorithms use move semantics (discussed in Chapter 24, C++11 and C++14 Additional Features) to move, rather than copy, objects from one container to another.

Lines 30–31 use the merge algorithm to combine two sorted ascending sequences of values into a third sorted ascending sequence. The algorithm 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 (a1), the second two arguments specify the range of elements in the second sorted sequence (a2) and the last argument specifies the starting location in the third sequence (results2) where the elements will be merged. A second version of this algorithm takes as its sixth argument a binary predicate function that specifies the sorting order by comparing its two arguments and returning true if the first is less than the second.

Line 27 created the array results2 with the total number of elements in both a1 and a2. Using the merge algorithm requires that the sequence where the results are stored be at least the sum of the sizes of the 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 a dynamically growable vector and the following statements:

vector<int> results;
merge(a1.begin(), a1.end(), a2.begin(), a2.end(),
   back_inserter(results));

The argument back_inserter(results) uses the function template back_inserter (header <iterator>) to call the container’s default push_back function to insert an element at the end of the container—results in this case—rather than replacing an existing element’s value. If an element is inserted into a container that has no more space available, the container grows to accomodate the new element (we used a vector here, because arrays are fixed size). Thus, the number of elements in the container does not have to be known in advance.

There are two other inserters—front_inserter (uses push_front to insert an element at the beginning of a container specified as its argument) and inserter (uses insert to insert an element at the iterator supplied as its second argument in the container supplied as its first argument).

Line 37 uses the unique algorithm on the sorted sequence of elements in the range from results2.begin() up to, but not including, results2.end(). After this algorithm is applied to a sorted sequence with duplicate values, only a single copy of each value remains in the sequence. The algorithm takes two arguments that must be at least forward iterators. The algorithm 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 and should not be used. An overloaded version of this algorithm receives as a third argument a binary predicate function specifying how to compare two elements for equality.

Line 43 uses the reverse algorithm to reverse all the elements in the range from a1.begin() up to, but not including, a1.end(). The algorithm takes two arguments that must be at least bidirectional iterators.

C++11 added the copy algorithms copy_if and copy_n. The copy_if algorithm copies each element from a range if the unary predicate function in its fourth argument returns true for that element. 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 written into to the copy location. This algorithm returns an iterator positioned after the last element copied.

The copy_n algorithm copies the number of elements specified by its second argument from the location specified by its first argument (an input iterator). The elements are output to the location specified by its third argument (an output iterator).

Line 20 uses the inplace_merge algorithm to merge two sorted sequences of elements in the same container. In this example, the elements from a1.begin() up to, but not including, a1.begin() + 5 are merged with the elements from a1.begin() + 5 up to, but not including, a1.end(). This algorithm requires its three iterator arguments to be at least bidirectional iterators. A second version of this algorithm takes as a fourth argument a binary predicate function for comparing elements in the two sequences.

Line 28 uses the unique_copy algorithm to make a copy of all the unique elements in the sorted sequence of values from a1.cbegin() up to, but not including, a1.cend(). 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 a1. Instead, we use function back_inserter (defined in header <iterator>), as discussed in Section 16.4.8, to insert elements at the end of results1. A second version of the unique_copy algorithm takes as a fourth argument a binary predicate function for comparing elements for equality.

Line 35 uses the reverse_copy algorithm to make a reversed copy of the elements in the range from a1.cbegin() up to, but not including, a1.cend(). 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. Algorithm reverse_copy requires its first two iterator arguments to be at least bidirectional iterators and its third to be at least an output iterator.

Lines 25 and 33 call the includes algorithm, which 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 25, the first set consists of the elements from a1.cbegin() up to, but not including, a1.cend(). The last two iterator arguments must be at least input iterators and must describe the second set of values. In line 25, the second set consists of the elements from a2.cbegin() up to, but not including, a2.cend(). An overloaded version of includes takes a fifth argument that’s a binary predicate function indicating whether its first argument is less than its second. The two sequences must be sorted using the same comparison function.

Lines 43–44 use the set_difference algorithm 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 algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. An overloaded version of set_difference takes a sixth argument that’s a binary predicate function indicating whether its first argument is less than its second. The two sequences must be sorted using the same comparison function.

Lines 51–52 use the set_intersection algorithm 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 algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. An overloaded version of set_intersection takes a sixth argument that’s a binary predicate function indicating whether its first argument is less than its second. The two sequences must be sorted using the same comparison function.

Lines 60–61 use the set_symmetric_difference algorithm 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 algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. An overloaded version of set_symmetric_difference takes a sixth argument that’s a binary predicate function indicating whether its first argument is less than its second. The two sequences must be sorted using the same comparison function.

Lines 68–69 use the set_union algorithm 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 copied only 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 algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. An overloaded version of set_union takes a sixth argument that’s a binary predicate function indicating whether its first argument is less than its second. The two sequences must be sorted in ascending order using the same comparison function.

Line 19 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.

Line 24 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.

Line 30 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.

Algorithms lower_bound, upper_bound and equal_range are often used to locate insertion points in sorted sequences. Line 39 uses lower_bound to locate the first point at which 5 can be inserted in order in a. Line 46 uses upper_bound to locate the last point at which 7 can be inserted in order in a. Line 54 uses equal_range to locate the first and last points at which 5 can be inserted in order in a.

Algorithms min and max (demonstrated in lines 9–12) determine the minimum and the maximum of two elements, respectively.

C++11 added overloaded versions of the algorithms min and max that each receive an initializer_list parameter and return the smallest or largest item in the list initializer that’s passed as an argument. For example, the following statement returns 7:

int minimum = min({ 10, 7, 14, 21, 17 });

Each of these new min and max algorithms is overloaded with a version that takes as a second argument a binary predicate function for determining whether the first argument is less than the second.

C++11 also added the minmax algorithm (line 15) that receives two items and returns a pair in which the smaller item is stored in first and the larger item is stored in second. A second version of this algorithm takes as a third argument a binary predicate function for determining whether the first argument is less than the second.

In addition, C++11 added the minmax_element algorithm (line 25) that receives two input iterators representing a range of elements and returns a pair of iterators in which first points to the smallest element in the range and second points to the largest. A second version of this algorithm takes as a third argument a binary predicate function for determining whether the first argument is less than the second.