- Table of Contents
- Previous Chapter
- Next Chapter

# Chapter 19: The STL Generic Algorithms

## 19.1: The Generic Algorithms

Before using the generic algorithms presented in this chapter, except for those in the `Operators` category (defined below), the `<algorithm>` header file must be included. Before using a generic algorithm in the `Operators` category the `<numeric>` header file must be included.

In the previous chapter the Standard Template Library (STL) was introduced. An important element of the STL, the generic algorithms, was not covered in that chapter as they form a fairly extensive part of the STL. Over time the STL has grown considerably, mainly as a result of a growing importance and appreciation of templates. Covering generic algorithm in the STL chapter itself would turn that chapter into an unwieldy one and so the generic algorithms were moved to a chapter of their own.

Generic algorithms perform an amazing task. Due to the strength of templates, algorithms could be developed that can be applied to a wide range of different data types while maintaining type safety. The prototypical example of this is the `sort` generic algorithm. To contrast: while C requires programmers to write callback functions in which type-unsafe `void const *` parameters have to be used, internally forcing the programmer to resort to casts, STL's `sort` frequently allows the programmer merely to state something akin to

        sort(first-element, last-element)

Generic algorithms should be used wherever possible. Avoid the urge to design your own code for commonly encountered algorithms. Make it a habit to first thoroughly search the generic algorithms for an available candidate. The generic algorithms should become your weapon of choice when writing code: acquire full familiarity with them and make their use your `second nature'.

On the other hand, without downgrading the importance of the generic algorithms, it's clear that over the years the number of available generic algorithms have seen an almost unlimited growth. Many new algorithms were added, even though for quite a few of them it's either very easy to provide direct implementations, or which may hardly ever be used. An example is the `is_sorted` generic algorithm, simply returning `true` if a range of elements is considered sorted and `false` if not. How hard is it to define such a function in the occasional situation you might need it? This applies to quite a few other generic algorithms. It's of course nice to have an extensive toolbox, but do you need, e.g., screwdrivers that perfectly match the screws' heads? Most likely not.... To avoid an excessive growth of this chapter, some sections contain comparable algorithms, and in some sections links to cppreference are provided when referring to comparable algorithms.

Nevertheless, this chapter's sections cover many of the STL's generic algorithms (in alphabetical order). For each algorithm the following information is provided:

- The required header file;
- The function prototype;
- A short description;
- A short example.

In the prototypes of the algorithms `Type` is used to specify a generic data type. Furthermore, the particular type of iterator (see section 18.2) that is required is mentioned as well as other generic types that might be required (e.g., performing `BinaryOperations`, like `plus<Type>`). Although iterators are commonly provided by abstract containers and comparable pre-defined data structures, at some point you may want to design your own iterators. Section 22.14 offers guidelines for constructing your own iterator classes and provides an overview of of operators that must be implemented for the various types of iterators.

Almost every generic algorithm expects an iterator range `[first, last)`, defining the series of elements on which the algorithm operates. The iterators point to objects or values. When an iterator points to a `Type` value or object, function objects used by the algorithms usually receive `Type const &` objects or values. Usually function objects cannot modify the objects they receive as their arguments. This does not hold true for modifying generic algorithms, which are of course able to modify the objects they operate upon.

Generic algorithms may be categorized. The C++ Annotations distinguishes the following categories of generic algorithms:

- Comparators: comparing (ranges of) elements:

  > all_of; any_of; equal; includes; lexicographical_compare; mismatch; none_of;

- Copiers / movers: performing copy / move operations:

  > copy; copy_backward; copy_if; move; move_backward; partition_copy; partial_sort_copy; remove_copy; remove_copy_if; replace_copy; replace_copy_if; reverse_copy; rotate_copy; sample; shift_left; shift_right; unique_copy;

- Counters: performing count operations:

  > count; count_if;

- Heap operators: manipulating a max-heap:

  > make_heap; pop_heap; push_heap; sort_heap;

- Initializers: initializing data:

  > fill; fill_n; generate; generate_n; iota; uninitialized (raw) memory;

- Limiters: determining boundaries of data:

  > begin; end;

- Operators: performing some kind of (arithmetic?) operations:

  > accumulate; adjacent_difference; exclusive_scan; inclusive_scan; inner_product; partial_sum; reduce; transform_reduce;

- Searchers: performing search (and find) operations:

  > adjacent_find; binary_search; equal_range; find; find_end; find_first_of; find_if; find_if_not; lower_bound; max; max_element; min_element; min; minmax; minmax_element; partition_point; search; search_n; set_difference; set_intersection; set_symmetric_difference; set_union; upper_bound;

- Shufflers: performing reordering operations (sorting, merging, permuting, swapping):

  > inplace_merge; iter_swap; merge; next_permutation; nth_element; partial_sort; partition; prev_permutation; remove; remove_copy; remove_copy_if; remove_if; reverse; reverse_copy; rotate; rotate_copy; shuffle; sort; stable_partition; stable_sort; swap; swap_ranges; unique;

- Verifiers: checking for specific conditions:

  > is_partitioned; is_permutation; is_sorted; is_sorted_until;

- Visitors: visiting elements in a range:

  > for_each; replace; replace_copy; replace_copy_if; replace_if; transform; unique_copy;

### 19.1.1: Execution policies

Many of the following generic algorithms could very well be parallized. E.g., one of the following algorithms is `generate` (section 19.1.19), filling the elements with values produced by a generating function. If those values are randomly generated values then `generated` could very well be parallized, where each parallel thread handles a separate section of the range to be filled. Another example where parallel execution may be useful is when sorting series of values. For this the the `sort` generic algorithm can be used (section 19.1.54, which also contains an example of parallelized sorting).

These (and many other) generic algorithms can be executed in parallel, depending on the specified execution policy. When no execution policy is specified then the algorithms operated in their standard, sequential, way. The generic algorithms supporting execution policies have overloaded versions where the first parameter specifies the execution policy to use, followed by their remaining parameters. Function prototypes listed the following sections showing a first parameter `[ExecPol,]` may specify one of the execution policies introduced in this section as their first arguments. E.g., one of the `sort` generic algorithm's prototypes is

       void sort([ExecPol,]
            RandomAccessIterator first, RandomAccessIterator last);

and to sort, e.g., a vector if strings (`vs`), it can be called as

       sort(vs.bgin(), vs.end());

or as (see below)

       sort(execution::par, vs.bgin(), vs.end());

In order to use execution policies the `<execution>` header file must be included, and the linking option `-ltbb` must be specified with linking the compiled object files(s).

There are four types of execution policies (all defined in the `std` namespace):

- `<execution::sequenced_policy>`, whose predefined object `execution::seq` is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy it will not be using parallel execution.

- `<execution::parallel_policy>`, whose predefined object `execution::par` is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy it may be using parallel execution: the generic algorithm may decide not to use parallel execution when it decides that the overhead of parallel execution is in fact reducing the efficiency of non-parallel execution. E.g., when sorting 100 elements sequential execution is faster than parallel execution and an algorithm like `sort` won't use parallel execution.

- `<execution::parallel_unsequenced_policy>`, whose predefined object `execution::par_unseq` is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy it may be using parallel execution, execution may be migrated across threads (using a so-called parent-stealing scheduler), or execution may be vectorized (i.e., a single thread is used accessing data items at completely different locations (like swapping the first and middle elements of vectors)). When using this policy the order in which processed elements are accessed and the threads from which these elements are accessed is undefined.

- `<execution::unsequenced_policy>`, whose predefined object `execution::unseq` is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy the algorithm uses vectorized execution.

Whenever algorithms are called using the above policy specifications and during the execution of these algorithms functions are called generating uncaught exceptions `std::terminate` is called.

When using parallel execution the objects or functions passed to the generic algorithms might access data defined elsewhere. If those data are modified then it is possible that modifications are requested from different execution threads, which could result in data races or deadlocks. The programmer should ensure that data races and/or dadlocks cannot occur when using parallel execution.

### 19.1.2: accumulate

- Header file: `<numeric>`
- Function prototypes:
  - `Type accumulate(InputIterator first, InputIterator last, Type init);`
  - `Type accumulate(InputIterator first, InputIterator last, Type init, BinaryOperation op);`
- Description:
  - The first prototype: `operator+` is applied to the initial value `init` (lhs argument) and, in sequence, all elements reached from the iterator range (rhs argument). The resulting value is returned.
  - The second prototype: the binary operator `op` is applied to the initial value `init` (lhs argument) and, in sequence, all elements reached from the iterator range. The resulting value is returned.
  At each step the initial value receives the result of that step's computation. E.g., if `minus<int>` is used with the intial value 1, and the iterators refer to 2 and 3, then at step 1: 1 - 2 = -1 is computed and at step 2: -1 - 3 = -4. So `accumulate` returns -4.

  (See also the `reduce` algorithm (section 19.1.43)).

- Example:

          #include <numeric>
          #include <vector>
          #include <iostream>
          using namespace std;

          int main()
          {
              int         ia[] = {1, 2, 3, 4};
              vector<int> iv(ia, ia + 4);

              cout <<
                  "Sum: " << accumulate(iv.begin(), iv.end(), int()) << "\n"
                  "Product: " << accumulate(iv.begin(), iv.end(), int(1),
                                                  multiplies<int>{}) << '\n';
          }
          //  Displays:
          //      Sum: 10
          //      Product: 24

### 19.1.3: adjacent_difference

- Header file: `<numeric>`
- Function prototypes:
  - `OutputIterator adjacent_difference([ExecPol,] InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator adjacent_difference([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);`
- Description: All operations are performed on the original values, all computed values are returned values.
  - The first prototype: the first returned element is equal to the first element of the input range. The remaining returned elements are equal to the difference of the corresponding element in the input range and its previous element.
  - The second prototype: the first returned element is equal to the first element of the input range. The remaining returned elements are equal to the result of the binary operator `op` applied to the corresponding element in the input range (left operand) and its previous element (right operand).
- Example:

          #include <numeric>
          #include <vector>
          #include <iterator>
          #include <iostream>
          using namespace std;

          int main()
          {
              int             ia[] = {1, 2, 5, 10};
              vector<int>     iv(ia, ia + 4);
              vector<int>     ov(iv.size());

              adjacent_difference(iv.begin(), iv.end(), ov.begin());

              copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
              cout << '\n';

              adjacent_difference(iv.begin(), iv.end(), ov.begin(), minus<int>());

              copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      1 1 3 5
          //      1 1 3 5

### 19.1.4: adjacent_find

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator adjacent_find([ExecPol,] ForwardIterator first, ForwardIterator last);`
  - `OutputIterator adjacent_find([ExecPol,] ForwardIterator first, ForwardIterator last, Predicate pred);`
- Description:
  - The first prototype: the iterator pointing to the first element of the first pair of two adjacent equal elements is returned. If no such element exists, `last` is returned.
  - The second prototype: the iterator pointing to the first element of the first pair of two adjacent elements for which the binary predicate `pred` returns `true` is returned. If no such element exists, `last` is returned.
- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          using namespace std;

          bool squaresDiff10(size_t first, size_t second)
          {
              return second * second - first * first >= 10;
          }

          int main()
          {
              string sarr[] =
                  {
                      "Alpha", "bravo", "charley", "delta", "echo", "echo",
                      "foxtrot", "golf"
                  };
              auto last = end(sarr);          // see the 'begin / end' section
              string *result = adjacent_find(sarr, last);

              cout << *result << '\n';
              result = adjacent_find(++result, last);

              cout << "Second time, starting from the next position:\n" <<
                  (
                      result == last ?
                          "** No more adjacent equal elements **"
                      :
                          "*result"
                  ) << '\n';

              size_t iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
              size_t *ires = adjacent_find(iv, end(iv), squaresDiff10);

              cout <<
                  "The first numbers for which the squares differ at least 10: "
                  << *ires << " and " << *(ires + 1) << '\n';
          }
          // Displays:
          //
          //   echo
          //   Second time, starting from the next position:
          //   ** No more adjacent equal elements **
          //   The first numbers for which the squares differ at least 10: 5 and 6

### 19.1.5: all_of / any_of / none_of

- Header file: `<algorithm>`
- Function prototypes:
  - `bool all_of([ExecPol,] InputIterator first, InputIterator last, Predicate pred);`
  - `bool any_of([ExecPol,] InputIterator first, InputIterator last, Predicate pred);`
  - `bool none_of([ExecPol,] InputIterator first, InputIterator last, Predicate pred);`
- Description:
  - The first prototype returns `true` if the unary predicate `pred` returns `true` for all elements reached from the iterator range `[first, last)`; otherwise `false` is returned.
  - The second prototype returns `true` if the unary predicate `pred` returns `true` for at least on of the elements reached from the iterator range `[first, last)`; otherwise `false` is returned.
  - The third prototype returns `true` if the unary predicate `pred` returns `true` for none of the elements reached from the iterator range `[first, last)`; otherwise `false` is returned.
- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          using namespace std;

          bool contains_a(string const &str)
          {
              return str.find('a') != string::npos;
          }

          int main()
          {
              string sarr[] =
                  { "Alpha", "Bravo", "Charley", "Delta", "Echo" };
              auto past = end(sarr);      // see the next section

              cout << "All elements contain 'a': " <<
                  all_of(sarr, past, contains_a) << "\n"
                  "At least one element contains 'a': " <<
                  any_of(sarr, past, contains_a) << "\n"
                  "None of the elements contains 'a': " <<
                  none_of(sarr, past, contains_a) << '\n';
          }
          //  Displays:
          //      All elements contain 'a': 0
          //      At least one element contains 'a': 1
          //      None of the elements contains 'a': 0

### 19.1.6: begin / end

- Header file: `<iterator>` (also available when including `<algorithm>`)
- Function prototypes:
  - `auto begin([const] &obj);`
  - `auto end([const] &obj);`
  - `Type [cons] *begin(Type [const] (&array)[N]);`
  - `Type [cons] *end(Type [const] (&array)[N]);`
  - `auto cbegin(const &obj);`
  - `auto cend(const &obj);`
- Description: The `begin` and `end` functions return, respectively, the begin- and end-iterators or pointers of objects offering `begin()` and `end()` members or of arrays of (compile-time) available sizes.
  - The first two prototypes return, respectively, `obj.begin()` and `obj.end()` of (possibly `const`) references to `obj`
  - Prototypes three and four return (possibly `const`) pointers to, respectively, the first and beyond the last element of the `array` argument, which must be an array of (compile-time) known size.
  - The lastt two prototypes return, respectively, `obj.begin()` and `obj.end()` of `const` references to `obj`
- Example:

          #include <iterator>
          #include <iostream>
          #include <string>
          using namespace std;

          int main()
          {
              string sarr[] =
                  { "Alpha", "Bravo", "Charley", "Delta", "Echo" };

              // since sarr == begin(sarr), begin(...) is not used here
              auto next = end(sarr);

              cout << "sarr has " << size(sarr) <<
                      " (== " << (next - sarr) << ") elements\n"
                      "the last char. of the first element is " <<
                      *(end(sarr[0]) - 1) << '\n';
          }
          //  Displays:
          //    sarr has 5 (== 5) elements
          //    the last char. of the first element is a

### 19.1.7: binary_search

- Header file: `<algorithm>`
- Function prototypes:
  - `bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value);`
  - `bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value, Comparator comp);`
- Description:
  - The first prototype: `value` is searched for using binary search in the elements reached from the iterator range `[first, last)`. The elements must have been sorted by the `Type::operator<` function. `True` is returned if the element was found, `false` otherwise.
  - The second prototype: `value` is searched for using binary search in the elements reached from the iterator range `[first, last)`. The elements in the range must have been sorted by the `Comparator` function object. `True` is returned if the element was found, `false` otherwise. As illustrated by the following example, the function object function's first parameter refers to an element in the iterator range, while the function object's second parameter refers to `value`.
- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <functional>
          using namespace std;

          int main()
          {
              string sarr[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel"
                  };
              auto past = end(sarr);
              bool result = binary_search(sarr, past, "foxtrot");
              cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';

              reverse(sarr, past);                // reverse the order of elements
                                                  // binary search now fails:
              result = binary_search(sarr, past, "foxtrot");
              cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
                                                  // ok when using appropriate
                                                  // comparator:
              result = binary_search(sarr, past, "foxtrot", greater<string>());
              cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';

              // alternatively, using a lambda expression showing the used 'sarr'
              // indices and the value of the second parameter:

              result = binary_search(sarr, past, "foxtrot",
                  [&](string const &sarrEl, string const &value)
                  {
                      cout << "comparing element " << (&sarrEl - sarr) <<
                              " (" << sarrEl << ") to " << value << '\n';
                      return sarrEl > value;
                  }
              );
              cout << "found it: " << result << '\n';
          }
          //  Displays:
          //      found foxtrot
          //      didn't find foxtrot
          //      found foxtrot
          //      comparing element 4 (delta) to foxtrot
          //      comparing element 2 (foxtrot) to foxtrot
          //      comparing element 1 (golf) to foxtrot
          //      comparing element -3 (foxtrot) to foxtrot
          //      found it: 1

If `value` is in fact present in the range of values, then this generic algorithm doesn't answer the question where `value` is located. If that question must be answered the generic algorithms lower_bound and upper_bound can be used. Refer to sections 19.1.30 and 19.1.61 for examples illustrating the use of these latter two algorithms.

### 19.1.8: copy / copy_if

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator destination);`
  - `OutputIterator copy_if([ExecPol,] InputIterator first, InputIterator last, OutputIterator destination, Predicate pred);`
- Description:
  - First prototype: the elements reached from the iterator range `[first, last)` are copied (assigned) to the `destination` output range. The return value is the OutputIterator pointing just beyond the last element that was copied to the destination range (so, `last' in the destination range is returned).
  - Second prototype: same as the first prototype but the function ends after copying `n` elements, returning an iterator pointing just beyond the last element that was copied to the destination range.
- Example:
  Note the second call to `copy`. It uses an `ostream_iterator` for `string` objects. This iterator writes the `string` values to the specified `ostream` (i.e., `cout`), separating the values by the specified separation string (i.e., `" "`).

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <iterator>
          using namespace std;

          bool pred(std::string const &str)
          {
              return "aceg"s.find(str.front()) == string::npos;
          }

          int main()
          {
              string sarr[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel"
                  };
              auto last = end(sarr);

              copy(sarr + 2, last, sarr); // move all elements two positions left

                           // copy to cout using an ostream_iterator for strings
              copy(sarr, last, ostream_iterator<string>(cout, " "));
              cout << '\n';

                          // using copy_if:
              copy_if(sarr, sarr + size(sarr), sarr, pred);
              copy(sarr, sarr + size(sarr), ostream_iterator<string>(cout, " "));
              cout << '\n';

          }
          //  Displays:
          //  charley delta echo foxtrot golf hotel golf hotel
          //  delta foxtrot hotel hotel golf hotel golf hotel

- See also: `unique_copy`

### 19.1.9: copy_backward

- Header file: `<algorithm>`
- Function prototype:
  - `BidirectionalIterator copy_backward(InputIterator first, InputIterator last, BidirectionalIterator last2);`
- Description:
  - The series of elements reached from the iterator range `[first, last)` are copied from the element at position `last - 1` until (and including) the element at position `first` to the element range, ending at position `last2 - 1` using the assignment operator of the underlying data type. The destination range is therefore `[last2 - (last - first), last2)`.

    Note that this algorithm does not reverse the order of the elements when copying them to the destination range.

    The return value is the BidirectionalIterator pointing to the last element that was copied to the destination range (so, `first' in the destination range, pointed to by `last2 - (last - first)`, is returned).

- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <iterator>
          using namespace std;

          int main()
          {
              string sarr[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel"
                  };
              auto past = end(sarr);

              copy
              (
                  copy_backward(sarr + 3, past, past - 3),
                  past,
                  ostream_iterator<string>(cout, " ")
              );
              cout << '\n';
          }
          // Displays:    golf hotel foxtrot golf hotel foxtrot golf hotel

### 19.1.10: count / count_if

- Header file: `<algorithm>`
- Function prototypes:
  - `size_t count([ExecPol,] InputIterator first, InputIterator last, Type const &value);`
  - `size_t count_if([ExecPol,] InputIterator first, InputIterator last, Predicate predicate);`

- Description:
  - The first prototype: returns the number of times `value` occurs in the elements reached from the iterator range `[first, last)`. Uses `Type::operator==` to determine whether `value` is equal to an element in the iterator range.
  - The second prototype: returns the number of times unary predicate ``predicate`' returns `true` when applied to the elements reached from the iterator range `[first, last)`.
- Example:

          #include <algorithm>
          #include <iostream>
          using namespace std;

          bool pred(int value)
          {
              return value & 1;
          }

          int main()
          {
              int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};

              cout << "Number of times the value 3 is available: " <<
                      count(ia, ia + size(ia), 3) << "\n"
                      "Number of odd values in the array is: " <<
                      count_if(ia, ia + size(ia), pred) << '\n';

          }
          // Displays:    Number of times the value 3 is available: 3
          //              Number of odd values in the array is: 5

### 19.1.11: equal

- Header file: `<algorithm>`
- Function prototypes:
  - `bool equal([ExecPol,] InputIterator first, InputIterator last, InputIterator otherFirst);`
  - `bool equal([ExecPol,] InputIterator first, InputIterator last, InputIterator otherFirst, BinaryPredicate pred);`
- Description:
  - The first prototype: the elements in the range `[first, last)` are compared to a range of equal length starting at `otherFirst`. The function returns `true` if the visited elements in both ranges are equal pairwise. The ranges need not be of equal length, only the elements in the indicated range are considered (and must be available).
  - The second prototype: the elements in the range `[first, last)` are compared to a range of equal length starting at `otherFirst`. The function returns `true` if the binary predicate, applied to all corresponding elements in both ranges returns `true` for every pair of corresponding elements. The ranges need not be of equal length, only the elements in the indicated range are considered (and must be available).
- Example:

          #include <algorithm>
          #include <string>
          #include <cstring>
          #include <iostream>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) == 0;
          }

          int main()
          {
              string first[] =
                  {
                      "Alpha", "bravo", "Charley", "delta", "Echo",
                      "foxtrot", "Golf", "hotel"
                  };
              string second[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel"
                  };
              auto past = end(first);

              cout << "The elements of `first' and `second' are pairwise " <<
                  (equal(first, past, second) ? "equal" : "not equal") <<
                  '\n' <<
                  "compared case-insensitively, they are " <<
                  (
                      equal(first, past, second, caseString) ?
                          "equal" : "not equal"
                  ) << '\n';
          }
          //  Displays:
          //      The elements of `first' and `second' are pairwise not equal
          //      compared case-insensitively, they are equal

### 19.1.12: equal_range

- Header file: `<algorithm>`
- Function prototypes:
  - `pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value);`
  - `pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value, Compare comp);`
- Description (see also identically named member functions of, e.g., the `map` (section 12.3.7) and `multimap` (section 12.3.8)):
  - The first prototype: starting from a sorted sequence (where the `operator<` of the data type to which the iterators point was used to sort the elements in the provided range), a pair of iterators is returned representing the return value of, respectively, `lower_bound` (returning the first element that is not smaller than the provided reference value, see section 19.1.30) and `upper_bound` (returning the first element beyond the provided reference value, see section 19.1.61).
  - The second prototype: starting from a sorted sequence (where the `comp` function object was used to sort the elements in the provided range), a pair of iterators is returned representing the return values of, respectively, the functions `lower_bound` (section 19.1.30) and `upper_bound` (section 19.1.61).
- Example:

          #include <algorithm>
          #include <functional>
          #include <iterator>
          #include <iostream>
          using namespace std;

          int main()
          {
              int    range[] = {1, 3, 5, 7, 7, 9, 9, 9};
              auto past = end(range);

              pair<int *, int *>  pi;

              pi = equal_range(range, past, 6);

              cout << "Lower bound for 6: " << *pi.first << "\n"
                      "Upper bound for 6: " << *pi.second << '\n';

              pi = equal_range(range, past, 7);

              cout << "Lower bound for 7: ";
              copy(pi.first, past, ostream_iterator<int>(cout, " "));
              cout << '\n';

              cout << "Upper bound for 7: ";
              copy(pi.second, past, ostream_iterator<int>(cout, " "));
              cout << '\n';

              sort(range, past, greater<int>());

              cout << "Sorted in descending order\n";

              copy(range, past, ostream_iterator<int>(cout, " "));
              cout << '\n';

              pi = equal_range(range, past, 7, greater<int>());

              cout << "Lower bound for 7: ";
              copy(pi.first, past, ostream_iterator<int>(cout, " "));
              cout << '\n';

              cout << "Upper bound for 7: ";
              copy(pi.second, past, ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      Lower bound for 6: 7
          //      Upper bound for 6: 7
          //      Lower bound for 7: 7 7 9 9 9
          //      Upper bound for 7: 9 9 9
          //      Sorted in descending order
          //      9 9 9 7 7 5 3 1
          //      Lower bound for 7: 7 7 5 3 1
          //      Upper bound for 7: 5 3 1

### 19.1.13: exchange

- Header file: `<utility>`
- Function prototype:
  - `Type exchange(Type &object1, ValueType &&newValue);`
- Description:
  - `newValue` is assigned to `object1`, and `object1's` previous value is returned.
- Example:

          #include <utility>
          #include <iostream>
          using namespace std;

          int main(int argc, char **argv)
          {
              bool more = argc > 5;

              cout << "more than 5: " << exchange(more, argc > 2) <<
                      ", more than 2: " << more << '\n';
          }
          //  With `a.out one two three' displays:
          //
          //  more than 5: 0, more than 2: 1

### 19.1.14: fill / fill_n

- Header file: `<algorithm>`
- Function prototypes:
  - `void fill([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &value);`
  - `void fill_n([ExecPol,] ForwardIterator first, Size n, Type const &value);`
- Description:
  - The first prototype: all elements reached from the iterator range `[first, last)` are initialized to `value`, overwriting previously stored values.
  - The second prototype: `n` elements starting at the element pointed to by `first` are initialized to `value`, overwriting previously stored values.
- Example:

          #include <algorithm>
          #include <vector>
          #include <iterator>
          #include <iostream>
          using namespace std;

          int main()
          {
              vector<int> iv(8);

              fill(iv.begin(), iv.end(), 8);
              copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
              cout << '\n';

              fill_n(iv.begin() + 2, 4, 4);
              copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
              cout << '\n';
           }
          // Displays:    8 8 8 8 8 8 8 8
          //              8 8 4 4 4 4 8 8

### 19.1.15: find / find_if / find_if_not

- Header file: `<algorithm>`
- Function prototypes:
  - `InputIterator find([ExecPol,] InputIterator first, InputIterator last, Type const &value);`
  - `InputIterator find_if([ExecPol,] InputIterator first, InputIterator last, Predicate pred);`
  - `InputIterator find_if_not([ExecPol,] InputIterator first, InputIterator last, Predicate pred);`
- Description:
  - The first prototype: element `value` is searched for in the elements reached from the iterator range `[first, last)`. An iterator pointing to the first element found is returned. If the element was not found, `last` is returned. The `operator==` of the underlying data type is used to compare the elements.
  - The second prototype returns an iterator pointing to the first element reached from the iterator range `[first, last)` for which the (unary) predicate `pred` returns `true`. If the element was not found, `last` is returned.
  - The third prototype returns an iterator pointing to the first element reached from the iterator range `[first, last)` for which the (unary) predicate `pred` returns `false`. If the element was not found, `last` is returned. Thus, `pred` defines what is considered acceptable, in which case `find_if_not` returns an iterator to the first element that isn't.
- Example:

          #include <algorithm>
          #include <string>
          #include <cstring>
          #include <iterator>
          #include <iostream>
          using namespace std;

          class CaseName
          {
              std::string  d_string;

              public:
                  CaseName(char const *str): d_string(str)
                  {}
                  bool operator()(std::string const &element) const
                  {
                      return strcasecmp(element.c_str(), d_string.c_str()) == 0;
                  }
          };

          void show(string const *begin, string const *end)
          {
              if (begin == end)
                  cout << "No elements were found";
              else
                  copy(begin, end, ostream_iterator<string>{ cout, " " });
              cout << '\n';
          }

          int main()
          {
              string sarr[] =
                  {
                      "Alpha", "Bravo", "Charley", "Delta", "Echo"
                  };
              auto past = end(sarr);

              show(find(sarr, past, "Delta"), past);
              show(find(sarr, past, "India"), past);

              show(find_if(sarr, sarr + size(sarr), CaseName{ "charley" }), past);

              if (find_if(sarr, sarr + size(sarr), CaseName{ "india" }) == past)
                  cout << "`india' was not found in the range\n";

              show(find_if_not(sarr, sarr + size(sarr), CaseName{ "alpha" }), past);
          }
          //  Displays:
          //      Delta Echo
          //      No elements were found
          //      Charley Delta Echo
          //      `india' was not found in the range
          //      Bravo Charley Delta Echo

### 19.1.16: find_end

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator1 find_end([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)`
  - `ForwardIterator1 find_end([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)`
- Description:
  - The first prototype: the sequence of elements in the range `[first1, last1)` is searched for the last occurrence of the sequence of elements in the range `[first2, last2)`. If the sequence `[first2, last2)` is not found, `last1` is returned, otherwise an iterator pointing to the first element of the matching sequence is returned. The `operator==` of the underlying data type is used to compare the elements in the two sequences.
  - The second prototype: the sequence of elements in the range `[first1, last1)` is searched for the last occurrence of the sequence of elements in the range `[first2, last2)`. If the sequence `[first2, last2)` is not found, `last1` is returned, otherwise an iterator pointing to the first element of the matching sequence is returned. The provided binary predicate is used to compare the elements in the two sequences.
- Example:

          #include <algorithm>
          #include <string>
          #include <iterator>
          #include <iostream>
          using namespace std;

          bool twice(size_t first, size_t second)
          {
              return first == (second << 1);
          }

          int main()
          {
              string sarr[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel",
                      "foxtrot", "golf", "hotel",
                      "india", "juliet", "kilo"
                  };
              string search[] =
                  {
                      "foxtrot",
                      "golf",
                      "hotel"
                  };
              auto past = end(sarr);

              copy
              (
                  find_end(sarr, past, search, search + 3),   // sequence starting
                  past, ostream_iterator<string>{ cout, " " } // at 2nd 'foxtrot'
              );
              cout << '\n';

              size_t range[] = { 2, 4, 6, 8, 10, 4, 6, 8, 10 };
              size_t nrs[]   = { 2, 3, 4 };

              copy                // sequence of values starting at last sequence
              (                   // of range[] that are twice the values in nrs[]
                  find_end(range, range + 9, nrs, nrs + 3, twice),
                  range + 9, ostream_iterator<size_t>{ cout, " " }
              );
              cout << '\n';
          }
          //  Displays:
          //      foxtrot golf hotel india juliet kilo
          //      4 6 8 10

### 19.1.17: find_first_of

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator1 find_first_of([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)`
  - `ForwardIterator1 find_first_of([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)`
- Description:
  - The first prototype: the sequence of elements in the range `[first1, last1)` is searched for the first occurrence of an element in the sequence of elements in the range `[first2, last2)`. If no element in the sequence `[first2, last2)` is found, `last1` is returned, otherwise an iterator pointing to the first element in `[first1, last1)` that is equal to an element in `[first2, last2)` is returned. The `operator==` of the underlying data type is used to compare the elements in the two sequences.
  - The second prototype: the sequence of elements in the range `[first1, last1)` is searched for the first occurrence of an element in the sequence of elements in the range `[first2, last2)`. Each element in the range `[first1, last1)` is compared to each element in the range `[first2, last2)`, and an iterator to the first element in `[first1, last1)` for which the binary predicate `pred` (receiving an the element out of the range `[first1, last1)` and an element from the range `[first2, last2)`) returns `true` is returned. Otherwise, `last1` is returned.
- Example:

          #include <algorithm>
          #include <string>
          #include <iterator>
          #include <iostream>
          using namespace std;

          bool twice(size_t first, size_t second)
          {
              return first == (second << 1);
          }
          int main()
          {
              string sarr[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel",
                      "foxtrot", "golf", "hotel",
                      "india", "juliet", "kilo"
                  };
              string search[] =
                  {
                      "foxtrot",
                      "golf",
                      "hotel"
                  };
              auto past = end(sarr);

              copy
              (                                                 // sequence starting
                  find_first_of(sarr, past, search, search + 3),// at 1st 'foxtrot'
                  past, ostream_iterator<string>{ cout, " " }
              );
              cout << '\n';

              size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};
              size_t nrs[]   = {2, 3, 4};

                  // copy the sequence of values in 'range', starting at the
                  // first element in 'range' that is equal to twice one of the
                  // values in 'nrs', and ending at the past element of 'range'
              copy
              (
                  find_first_of(range, range + 9, nrs, nrs + 3, twice),
                  range + 9, ostream_iterator<size_t>{ cout, " " }
              );
              cout << '\n';
          }
          //  Displays:
          //      foxtrot golf hotel foxtrot golf hotel india juliet kilo
          //      4 6 8 10 4 6 8 10

### 19.1.18: for_each

- Header file: `<algorithm>`
- Function prototype:
  - `Function for_each([ExecPol,] ForwardIterator first, ForwardIterator last, Function func);`
- Description:
  - The elements reached from the iterator range `[first, last)` are passed in sequence as a reference to the function (or function object) `func`. The function may modify the elements it receives (as the used iterator is a forward iterator). Alternatively, if the elements should be transformed, `transform` (see section 19.1.56) can be used. The function itself or a copy of the provided function object is returned: see the example below, in which an extra argument list is added to the `for_each` call, which argument is eventually also passed to the function given to `for_each`. Within `for_each` the return value of the function that is passed to it is ignored. The `for_each` generic algorithm looks a lot like the range-based for loop, but different from the range-based for-loop the `for_each` algorithm can also be used with sub-ranges and with reverse-iterators.
- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <cctype>
          using namespace std;

          void lowerCase(char &ch)                     // `ch' *is* modified
          {
              ch = tolower(static_cast<unsigned char>(ch));
          }

          void capitalizedOutput(string const &str)   // `str' is *not* modified
          {
              char *tmp = new char[str.size() + 1]();
              str.copy(tmp, str.size());

              for_each(tmp + 1, tmp + str.size(), lowerCase);

              tmp[0] = toupper(*tmp);
              cout << tmp << ' ';
              delete[] tmp;
          }

          int main()
          {
              string sarr[] =
                  {
                      "alpha", "BRAVO", "charley", "DELTA",  "echo",
                      "FOXTROT", "golf", "HOTEL"
                  };

              for_each(sarr, end(sarr), capitalizedOutput)("that's all, folks");
              cout << '\n';
          }
          // Displays:
          // Alpha Bravo Charley Delta Echo Foxtrot Golf Hotel That's all, folks

- Here is another example using a function object:

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <cctype>
          using namespace std;

          void lowerCase(char &c)
          {
              c = tolower(static_cast<unsigned char>(c));
          }
          class Show
          {
              int d_count;

              public:
                  Show()
                  :
                      d_count(0)
                  {}
                  void operator()(std::string &str)
                  {
                      std::for_each(str.begin(), str.end(), lowerCase);
                      str[0] = toupper(str[0]);   // assuming str is not empty
                      std::cout << ++d_count << " " << str << "; ";
                  }
                  int count() const
                  {
                      return d_count;
                  }
          };
          int main()
          {
              string sarr[] =
                  {
                      "alpha", "BRAVO", "charley", "DELTA", "echo",
                      "FOXTROT", "golf", "HOTEL"
                  };
              string *last = sarr + sizeof(sarr) / sizeof(string);

              cout << for_each(sarr, last, Show{}).count() << '\n';
          }
          /*
          Displays (all on one line):

          1 Alpha; 2 Bravo; 3 Charley; 4 Delta; 5 Echo; 6 Foxtrot;
                                                    7 Golf; 8 Hotel; 8
          */

The example also shows that the `for_each` algorithm may be used with functions defining `const` and non-`const` parameters. Also, see section 19.1.56 for differences between the `for_each` and `transform` generic algorithms.

The `for_each` algorithm cannot directly be used (i.e., by passing `*this` as the function object argument) inside a member function to modify its own object as the `for_each` algorithm first creates its own copy of the passed function object. A lambda function or a wrapper class whose constructor accepts a pointer or reference to the current object and possibly to one of its member functions solves this problem.

### 19.1.19: generate / generate_n

- Header file: `<algorithm>`
- Function prototype:
  - `void generate([ExecPol,] ForwardIterator first, ForwardIterator last, Generator generator);`
  - `void generate_n([ExecPol,] ForwardIterator first, Size n, Generator generator);`
- Description:
  - The first prototype: all elements reached from the iterator range `[first, last)` are initialized by the return value of `generator`, which can be a function or function object. `Generator::operator()` does not receive any arguments. The example uses a well-known fact from algebra: in order to obtain the square of `n + 1`, add `1 + 2 * n` to `n * n`.
  - The second prototype: `n` elements starting at the element pointed to by iterator `first` are initialized by the return value of `generator`.
- Example:

          #include <algorithm>
          #include <vector>
          #include <iterator>
          #include <iostream>
          using namespace std;

          class NaturalSquares
          {
              size_t d_newsqr;
              size_t d_last;

              public:
                  NaturalSquares(): d_newsqr(0), d_last(0)
                  {}
                  size_t operator()()
                  {                   // using: (a + 1)^2 == a^2 + 2*a + 1
                      return d_newsqr += (d_last++ << 1) + 1;
                  }
          };
          int main()
          {
              vector<size_t> uv(10);

              generate(uv.begin(), uv.end(), NaturalSquares{});

              copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
              cout << '\n';

              uv = vector<size_t>(10);
              generate_n(uv.begin(), 5, NaturalSquares{});

              copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
              cout << '\n';

          }
          // Displays:   1 4 9 16 25 36 49 64 81 100
          //             1 4 9 16 25 0 0 0 0 0

### 19.1.20: includes

- Header file: `<algorithm>`
- Function prototypes:
  - `bool includes([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);`
  - `bool includes([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);`
- Description:
  - The first prototype: both sequences of elements in the ranges `[first1, last1)` and `[first2, last2)` should have been sorted using the `operator<` of the data type to which the iterators point. The function returns `true` if every element in the second sequence `[first2, last2)` is contained in the first sequence `[first1, last1)` (the second range is a subset of the first range).
  - The second prototype: both sequences of elements in the ranges `[first1, last1)` and `[first2, last2)` should have been sorted using the `comp` function object. The function returns `true` if every element in the second sequence `[first2, last2)` is contained in the first sequence `[first1, last1)` (the second range is a subset of the first range).
- Example:

          #include <algorithm>
          #include <string>
          #include <cstring>
          #include <iostream>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) == 0;
          }

          int main()
          {
              string first1[] =
                  {
                      "alpha", "bravo", "charley", "delta",  "echo",
                      "foxtrot", "golf", "hotel"
                  };
              auto past1 = end(first1);

              string first2[] =
                  {
                      "Alpha", "bravo", "Charley", "delta",  "Echo",
                      "foxtrot", "Golf", "hotel"
                  };
              auto past2 = end(first2);

              string second[] = { "charley", "foxtrot", "hotel" };

              cout << "The elements of `second' are " <<
                  (includes(first1, past1, second, second + 3) ? "" : "not") <<
                     " contained in the first sequence:\n"
                     "second is a subset of first1\n"

                  "The elements of `first1' are " <<
                  (includes(second, second + 3, first1, past1) ? "" : "not") <<
                  " contained in the second sequence\n"

                  "The elements of `second' are " <<
                  (includes(first2, past2, second, second + 3) ? "" : "not") <<
                  " contained in the first2 sequence\n"

                  "Using case-insensitive comparison,\n"
                  "the elements of `second' are " <<
                  (includes(first2, past2, second, second + 3, caseString) ?
                                                                 "" : "not") <<
                  " contained in the first2 sequence\n";
          }
          //  Displays:
          //     The elements of `second' are  contained in the first sequence:
          //     second is a subset of first1
          //     The elements of `first1' are not contained in the second sequence
          //     The elements of `second' are not contained in the first2 sequence
          //     Using case-insensitive comparison,
          //     the elements of `second' are  contained in the first2 sequence

### 19.1.21: inner_product

- Header file: `<numeric>`
- Function prototypes:
  - `Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init);`
  - `Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init, BinaryOperator1 op1, BinaryOperator2 op2);`
- Description:
  - The first prototype: the sum of all pairwise products of the elements in the range `[first1, last1)` and the same number of elements starting at the element pointed to by `first2` are added to `init`, and this sum is returned. The function uses the `operator+` and `operator*` of the data type to which the iterators point.
  - The second prototype: binary operator `op1` instead of the default addition operator, and binary operator `op2` instead of the default multiplication operator are applied to all pairwise elements in the range `[first1, last1)` and the same number of elements starting at the element pointed to by `first2`. The results of the binary operator calls are added to `init` and `init`'s final value is returned.
  (See also section 19.1.57.)
- Example:

          #include <numeric>
          #include <algorithm>
          #include <iterator>
          #include <iostream>
          #include <string>
          using namespace std;

          class Cat
          {
              std::string  d_sep;
              public:
                  Cat(string const &sep)
                  :
                      d_sep(sep)
                  {}
                  string operator()
                      (string const &s1, string const &s2) const
                  {
                      return s1 + d_sep + s2;
                  }
          };
          int main()
          {
              size_t ia1[] = { 1, 2, 3, 4, 5, 6, 7 };

              cout << "The sum of all squares in ";
              copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
              cout << "is " << inner_product(ia1, ia1 + 7, ia1, 0) << '\n';

              size_t ia2[] = { 7, 6, 5, 4, 3, 2, 1 };

              cout << "The sum of all cross-products in ";
              copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
              cout << "and ";
              copy(ia2, ia2 + 7, ostream_iterator<size_t>{ cout, " " });
              cout << "is " << inner_product(ia1, ia1 + 7, ia2, 0) << '\n';

              string names1[] = { "Frank", "Karel", "Piet" };
              string names2[] = { "Brokken", "Kubat", "Plomp"};

              cout << "All combined names of ";
              copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });
              cout << "and\n";
              copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });
              cout << "are:" <<
                  inner_product(names1, names1 + 3, names2, string{ "\t" },
                      Cat{ "\n\t"}, Cat{ " " }) << '\n';
          }
          // Displays:
          //  The sum of all squares in 1 2 3 4 5 6 7 is 140
          //  The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84
          //  All combined names of Frank Karel Piet and Brokken Kubat Plomp are:
          //          Frank Brokken
          //          Karel Kubat
          //          Piet Plomp

### 19.1.22: inplace_merge

- Header file: `<algorithm>`
- Function prototypes:
  - `void inplace_merge([ExecPol,] BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);`
  - `void inplace_merge([ExecPol,] BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);`
- Description:
  - The first prototype: the two (sorted) ranges `[first, middle)` and `[middle, last)` are merged, keeping a sorted list (using the `operator<` of the data type to which the iterators point). The final series is stored in the range `[first, last)`.
  - The second prototype: the two (sorted) ranges `[first, middle)` and `[middle, last)` are merged, keeping a sorted list (using the boolean result of the binary comparison operator `comp`). The final series is stored in the range `[first, last)`.
- Example:

          #include <algorithm>
          #include <string>
          #include <cstring>
          #include <iterator>
          #include <iostream>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) == 0;
          }

          int main()
          {
              string range[] =
                  {
                      "alpha", "charley", "echo", "golf",
                      "bravo", "delta", "foxtrot",
                  };

              inplace_merge(range, range + 4, range + 7);
              copy(range, range + 7, ostream_iterator<string>{ cout, " " });
              cout << '\n';

              string range2[] =
                  {
                      "ALPHA", "CHARLEY", "DELTA", "foxtrot", "hotel",
                      "bravo", "ECHO", "GOLF"
                  };

              inplace_merge(range2, range2 + 5, range2 + 8, caseString);
              copy(range2, range2 + 8, ostream_iterator<string>{ cout, " " });
              cout << '\n';
          }
          //  Displays:
          //      alpha bravo charley delta echo foxtrot golf
          //      ALPHA bravo CHARLEY DELTA ECHO foxtrot GOLF hotel

### 19.1.23: iota

- Header file: `<numeric>`
- Function prototype:
  - `void iota(ForwardIterator first, ForwardIterator last, Type value);`
- Description:
  - All elements reached from the iterator range `[first, last)` are assigned the values of the incremented sequence of values starting at `value`. `*first` receives `value`, `*(first + 1)` receives `++value`, etc.
- Example:

          #include <numeric>
          #include <algorithm>
          #include <vector>
          #include <iostream>
          #include <iterator>

          using namespace std;

          int main()
          {
              vector<size_t> uv(10);

              iota(uv.begin(), uv.end(), 0);

              copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
              cout << '\n';
          }
          // Displays:   0 1 2 3 4 5 6 7 8 9

### 19.1.24: is_partitioned

- Header file: `<algorithm>`
- Function prototype:
  - `bool is_partitioned([ExecPol,] InputIterator first, InputIterator last, UnaryPred pred);`
- Description:
  - Returns `true` if `pred`, receiving all elements reached from the iterator range `[first, last)`, returns `true` until it returns `false`, and if `pred`, receiving the remaining elements, returns `false`. It also returns `true` if the range is empty.
- Example:

          #include <algorithm>
          #include <iterator>
          #include <vector>
          #include <iostream>
          using namespace std;

          bool pCheck(int value)
          {
              return value < 3;
          }

          int main()
          {
              vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};

              cout << "partitioned before: " <<
                      is_partitioned(uv.begin(), uv.end(), pCheck) << "\n"

                      "first value returning 'false' when partitioning: " <<
                      *partition(uv.begin(), uv.end(), pCheck) << '\n';

              copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
              cout << '\n';

              cout << "partitioned after: " <<
                      is_partitioned(uv.begin(), uv.end(), pCheck) <<'\n';

          }
          // Displays:   1 4 9 16 25 36 49 64 81 100
          //             1 4 9 16 25 0 0 0 0 0

### 19.1.25: is_permutation

- Header file: `<algorithm>`
- Function prototypes:
  - `bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2);`
  - `bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2);`
  - `bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator firs2, BinaryPred pred);`
  - `bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPred pred);`
- Description:
  - The first prototype: returns `true` if the elements in the iterator range `[first1, last1)`, are a permutation of the elements in the identically sized range starting at `first2`.
  - The second prototype: like the first prototype but the ending iterator of the second range is provided as the fourth argument.
  - The third prototype: like the first prototype but using the result of `pred` to determine whether two elements are equal.
  - The fourth prototype: like the second prototype but using the result of `pred` to determine whether two elements are equal.
- Example:

          #include <algorithm>
          #include <iostream>
          using namespace std;

          int main()
          {
              int one[] = { 1, -2, 3, -4, 5, -6, 7, -8, 9};
              int two[] = { -8, -2, -4, -6, 3, 1, 5, 9, 7};
              int three[] = { -8, -8, -4, -6, 3, 1, 5, 9, 7};

              cout << "one is a permutation of two: " <<
                  is_permutation(one, end(one), two) << "\n"

                  "one is a permutation of three: " <<
                  is_permutation(one, end(one), three, end(three)) << '\n';
          }
          // Displays: one is a permutation of two: 1
          //           one is a permutation of three: 0

### 19.1.26: is_sorted

- Header file: `<algorithm>`
- Function prototypes:
  - `bool is_sorted([ExecPol,] ForwardIterator first, ForwardIterator last);`
  - `bool is_sorted([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);`
- Description:
  - The first prototype: returns `true` if the elements in the iterator range `[first, last)`, are sorted using the elements' `operator<` comparison operator.
  - The second prototype: returns `true` if the elements in the iterator range `[first, last)`, are sorted using the binary predicate `pred`.
- Example:

          #include <algorithm>
          #include <vector>
          #include <iostream>
          using namespace std;

          int main()
          {
              vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};

              cout << "sorted before: " <<
                      is_sorted(uv.begin(), uv.end()) << '\n';

              sort(uv.begin(), uv.end());

              cout << "sorted after " <<
                      is_sorted(uv.begin(), uv.end()) << '\n';
          }
          // Displays:
          //    sorted before: 0
          //    sorted after 1

### 19.1.27: is_sorted_until

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator is_sorted_until([ExecPol,] ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator is_sorted_until([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);`
- Description:
  - The first prototype: returns an iterator to the end of range, starting at `first` whose elements are sorted using the elements' `operator<` comparison operator.
  - The second prototype: returns an iterator to the end of range, starting at `first` whose elements using the binary predicate `pred`.
  The functions return at least `first + 1`.
- Example:

          #include <algorithm>
          #include <vector>
          #include <iostream>
          using namespace std;

          int main()
          {
              vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};

              cout << "sorted before: " <<
                      is_sorted(uv.begin(), uv.end()) << '\n';

              sort(uv.begin(), uv.end());

              cout << "sorted after " <<
                      is_sorted(uv.begin(), uv.end()) << '\n';
          }
          // Displays:
          //    sorted before: 0
          //    sorted after 1

### 19.1.28: iter_swap

- Header file: `<algorithm>`
- Function prototype:
  - `void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2);`
- Description:
  - The elements pointed to by `iter1` and `iter2` are swapped.
- Example:

          #include <algorithm>
          #include <iterator>
          #include <iostream>
          #include <string>
          using namespace std;

          int main()
          {
              string first[] = { "alpha", "bravo", "charley" };
              string second[] = { "echo", "foxtrot", "golf" };

              cout << "Before:\n";
              copy(first, first + 3, ostream_iterator<string>(cout, " "));
              cout << '\n';
              copy(second, second + 3, ostream_iterator<string>(cout, " "));
              cout << '\n';

              for (size_t idx = 0; idx != 3; ++idx)
                  iter_swap(first + idx, second + idx);

              cout << "After:\n";
              copy(first, first + 3, ostream_iterator<string>(cout, " "));
              cout << '\n';
              copy(second, second + 3, ostream_iterator<string>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      Before:
          //      alpha bravo charley
          //      echo foxtrot golf
          //      After:
          //      echo foxtrot golf
          //      alpha bravo charley

### 19.1.29: lexicographical_compare

- Header file: `<algorithm>`
- Function prototypes:
  - `bool lexicographical_compare([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);`
  - `bool lexicographical_compare([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);`
- Description:
  - The first prototype: the corresponding pairs of elements in the ranges pointed to by the ranges `[first1, last1)` and `[first2, last2)` are compared. The function returns `true`
    - at the first element in the first range which is less than the corresponding element in the second range (using `operator<` of the underlying data type),
    - if `last1` is reached, but `last2` isn't reached yet.
    False is returned in the other cases, which indicates that the first sequence is not lexicographically less than the second sequence. So, `false` is returned:
    - at the first element in the first range which is greater than the corresponding element in the second range (using `operator<` of the data type to which the iterators point, reversing the operands),
    - if `last2` is reached, but `last1` isn't reached yet,
    - if `last1` and `last2` are reached.
  - The second prototype: with this function the binary comparison operation as defined by `comp` is used instead of `operator<` of the data type to which the iterators point.
- Example:

          #include <algorithm>
          #include <iterator>
          #include <iostream>
          #include <string>
          #include <cstring>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) < 0;
          }

          void compare(string const &word1, string const &word2)
          {
              cout << '`' << word1 << "' is " <<
                  (
                      lexicographical_compare(word1.begin(), word1.end(),
                                              word2.begin(), word2.end()) ?
                          "before `" : "beyond or at `"
                  ) <<
                  word2 << "' in the alphabet\n";
          }

          int main()
          {
              string word1 = "hello";
              string word2 = "help";

              compare(word1, word2);
              compare(word1, word1);
              compare(word2, word1);

              string one[] = {"alpha", "bravo", "charley"};
              string two[] = {"ALPHA", "BRAVO", "DELTA"};

              copy(one, one + 3, ostream_iterator<string>{ cout, " " });
              cout << " is ordered " <<
                  (
                      lexicographical_compare(one, one + 3,
                                              two, two + 3, caseString) ?
                          "before " : "beyond or at "
                  );
              copy(two, two + 3, ostream_iterator<string>{ cout, " " });
              cout << "\n"
                  "using case-insensitive comparisons.\n";
          }
          //   Displays:
          //      `hello' is before `help' in the alphabet
          //      `hello' is beyond or at `hello' in the alphabet
          //      `help' is beyond or at `hello' in the alphabet
          //      alpha bravo charley  is ordered before ALPHA BRAVO DELTA
          //      using case-insensitive comparisons.

### 19.1.30: lower_bound

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value);`
  - `ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value, BinaryPredicate pred);`
- Description:
  - The first prototype: the sorted elements (using ascending sort) reached from the iterator range `[first, last)` are searched for the first element that is not less than (i.e., greater than or equal to) `value`. The returned iterator marks the location in the sequence where `value` can be inserted without breaking the sorted order of the elements. The `operator<` of the data type to which the iterators point is used. If no such element is found, `last` is returned.
  - The second prototype: the elements reached from the iterator range `[first, last)` must have been sorted using the `comp` function (-object). Each element in the range is compared to `value` using the `comp` function, receiving an element from the iterator range as its first argument and `type` as its second argument. An iterator to the first element for which the binary predicate `comp`, applied to the elements of the range and `value`, returns `false` is returned. If no such element is found, `last` is returned.

    As illustrated by the following example, the function object function's first parameter refers to an element in the iterator range, while the function object's second parameter refers to `value`.

- Example:

          #include <algorithm>
          #include <iostream>
          #include <iterator>
          #include <vector>
          #include <functional>
          using namespace std;

          int main()
          {
              int     ia[] = { 10, 20, 30 };

              cout << "Sequence: ";
              copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
              cout << "\n"
                      "15 can be inserted before " <<
                      *lower_bound(ia, ia + 3, 15) << "\n"
                      "35 can be inserted after " <<
                      (lower_bound(ia, ia + 3, 35) == ia + 3 ?
                                          "the last element" : "???") << '\n';

              cout << "Sequence: ";
              copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
              cout << "\n"
                      "15 can be inserted before " <<
                      *lower_bound(ia, ia + 3, 15, less<int>()) << "\n"
                      "35 can be inserted before " <<
                      (lower_bound(ia, ia + 3, 35, less<int>()) == ia ?
                                          "the first element " : "???") << '\n';

              vector<int> array{ 5, 10, 20, 20, 20, 30 };
              auto iter = lower_bound(array.begin(), array.end(), 20,
                              [&](int &arrayEl, int value)
                              {
                                  cout << "Comparing " << arrayEl <<
                                      " (index: " << (&arrayEl - &array[0]) << ")"
                                      " to " << value << '\n';
                                  return arrayEl < value;
                              }
                          );
              cout << "New 20 to insert at idx " << (iter - array.begin()) << '\n';
          }
          //  Displays:
          //      Sequence: 10 20 30
          //      15 can be inserted before 20
          //      35 can be inserted after the last element
          //      Sequence: 10 20 30
          //      15 can be inserted before 20
          //      35 can be inserted before ???
          //      Comparing 20 (index: 3) to 20
          //      Comparing 10 (index: 1) to 20
          //      Comparing 20 (index: 2) to 20
          //      New 20 to insert at idx 2

The `binary_search` generic algorithm (cf. section 19.1.7)can be used to determine whether or not `value` is present in the iterator range. The `upper_bound` algorithm can be used to find the last element of a series of values equal to `value`. The `upper_bound` section (19.1.61) also contains an extensive example illustrating the use of `lower_bound` and as `upper_bound`.

### 19.1.31: max / min

- Header file: `<algorithm>`
- Function prototypes:
  - `Type const &max(Type const &one, Type const &two);`
  - `Type const &max(Type const &one, Type const &two, Comparator comp);`
  - `Type const &min(Type const &one, Type const &two);`
  - `Type const &min(Type const &one, Type const &two, Comparator comp);`
- Description:
  - The first prototype: the larger of the two elements `one` and `two` is returned, using the `operator>` of the data type to which the iterators point to determine which element is the larger one.
  - The second prototype: `one` is returned if the binary predicate `comp(one, two)` returns `true`, otherwise `two` is returned.
  - Prototypes three and four act identically to, respectively, prototypes one and two, using `std::min` instead of `std::max`, returning the smaller of the two arguments.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cstring>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) <= 0;
          }

          string const &call(bool first, string const &lhs, string const &rhs)
          {
              return first? max(lhs, rhs) : min(lhs, rhs);
          }

          string const &call(bool first, string const &lhs, string const &rhs,
                      bool (*cmp)(string const &, string const &))
          {
              return first? max(lhs, rhs, cmp) : min(lhs, rhs, cmp);
          }

          int main(int argc, char **argv) // no args: use max, else min
          {
              bool fun = argc == 1;
              char const *where = fun ? "last\n" : "first\n";

              cout << "Word '" << call(fun, "first", "second") <<
                                  "' is lexicographically " << where <<

                      "Word '" << call(fun, "first", "SECOND") <<
                                  "' is lexicographically " << where <<

                      "Word '" << call(fun, "first", "SECOND", caseString) <<
                                  "' is lexicographically " << where;
          }
          //  Displays when calling without args:
          //      Word 'second' is lexicographically last
          //      Word 'first' is lexicographically last
          //      Word 'SECOND' is lexicographically last
          //  and with an argument:
          //      Word 'first' is lexicographically first
          //      Word 'SECOND' is lexicographically first
          //      Word 'first' is lexicographically first

### 19.1.32: max_element / min_element / minmax_element

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator max_element([ExecPol,] ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator max_element([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);`
  - `ForwardIterator min_element([ExecPol,] ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator min_element([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);`

  - `pair<ForwardIterator, ForwardIterator> max_element([ExecPol,] ForwardIterator first,ForwardIterator last);`
  - `pair<ForwardIterator, ForwardIterator> max_element([ExecPol,] ForwardIterator first,ForwardIterator last, BinaryPredicate pred);`
- Description:
  - The first prototype: an iterator pointing to the largest element reached from the iterator range `[first, last)` is returned. The `operator<` of the data type to which the iterators point is used to decide which of the elements is the largest.
  - The second prototype: rather than using `operator<`, the binary predicate `pred` is used to make the comparisons between the elements reached from the iterator range `[first, last)`. The element for which `pred` returns most often `true`, compared with other elements, is returned.
  - Prototypes three and four act identically to, respectively, prototypes one and two, using `std::min_element` instead of `std::max_element`, returning iterators to the smallest elements in the iterator ranges `[first, last)`.
  - The final two prototypes act identically to, respectively, prototypes one and two, but return `std::pair` objects whose `first` members contain the iterators returned by the `min` generic algorithms and whose `second` members contain the iterators returned by the `max` generic algorithms.
- Example:

          #include <algorithm>
          #include <iostream>
          using namespace std;

          bool absCompare(int first, int second)
          {
              return abs(first) < abs(second);
          };

          int *maxMin(bool high, int *begin, int *end)
          {
              return high ? max_element(begin, end) : min_element(begin, end);
          }

          int *maxMin(bool high, int *begin, int *end, bool (*comp)(int, int))
          {
              return high ? max_element(begin, end, comp)
                          : min_element(begin, end, comp);
          }

                      // no args: calls max_element, else min_element
          int main(int argc, char **argv)
          {
              bool max = argc == 1;
              char const *type = max? "max" : "min";

              int     ia[] = {-4, 7, -2, 10, -12};

              cout << "The " << type << ". int value is " <<
                      *maxMin(max, ia, ia + 5) << "\n"
                      "The max. absolute int value is " <<
                      *maxMin(max, ia, ia + 5, absCompare) << '\n';
          }
          //  Displays, when called without arguments:
          //      The max. int value is 10
          //      The max. absolute int value is -12
          //  otherwise:
          //      The minimum int value is -12
          //      The minimum absolute int value is -2

### 19.1.33: merge

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator merge([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator merge([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: the two (sorted) ranges `[first1, last1)` and `[first2, last2)` are merged, keeping a sorted list (using the `operator<` of the data type to which the iterators point). The final series is stored in the range starting at `result` and ending just before the `OutputIterator` returned by the function.
  - The second prototype: the two (sorted) ranges `[first1, last1)` and `[first2, last2)` are merged, keeping a sorted list (using the boolean result of the binary comparison operator `comp`). The final series is stored in the range starting at `result` and ending just before the `OutputIterator` returned by the function.
- Example:

          #include <algorithm>
          #include <string>
          #include <cstring>
          #include <iterator>
          #include <iostream>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) < 0;
          }

          int main()
          {
              string range1[] =                           // 5 elements
                      { "alpha", "bravo", "foxtrot", "hotel", "zulu" };
              string range2[] =                           // 4 elements
                      { "delta", "echo", "golf", "romeo" };
              string result[5 + 4];

              copy(result,
                  merge(range1, range1 + 5, range2, range2 + 4, result),
                  ostream_iterator<string>{ cout, " " });
              cout << '\n';

              string range3[] =
                      { "ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU" };
              string range4[] = { "delta", "ECHO", "GOLF", "romeo" };

              copy(result,
                  merge(range3, range3 + 5, range4, range4 + 4, result,
                                                          caseString),
                  ostream_iterator<string>{ cout, " " });
              cout << '\n';
          }
          //  Displays:
          //      alpha bravo delta echo foxtrot golf hotel romeo zulu
          //      ALPHA bravo delta ECHO foxtrot GOLF HOTEL romeo ZULU

### 19.1.34: minmax

- Header file: `<algorithm>`
- Function prototypes:
  - `pair<Type const &, Type const &> minmax( Type const &t1, Type const &t2);`
  - `pair<Type const &, Type const &> minmax(Type const &t1, Type const &t2, BinaryPred pred);`
  - `pair<Type const &, Type const &> minmax( std:initializer<list<Type> values);`
  - `pair<Type const &, Type const &> minmax( std:initializer<list<Type> values, BinaryPred pred);`
- Description:
  - The first prototype: return a `std::pair` whose `first` and `second` members contain, respectively, the smaller and the larger value of the function's arguments, using `Type's operator<` to compare the two values.
  - The second prototype: identical to the first prototype, but deciding that `t1` is the smaller element if `pred(t1, t2)` returns `true`.
  - Prototypes three and four act identically to, respectively, prototypes one and two, but return, the smallest and largest values found in the provided `iterator_range` objects.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <functional>

          using namespace std;

          int main()
          {
              vector<size_t> uv(10);

              auto values = minmax(5, 2, less<int>{});
              cout << values.first << " is smaler than " << values.second << '\n';
          }
          // Displays:   2 is smaler than 5

### 19.1.35: mismatch

- Header file: `<algorithm>`
- Function prototypes:
  - `pair<InputIterator1, InputIterator2> mismatch([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);`
  - `pair<InputIterator1, InputIterator2> mismatch([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Compare comp);`
- Description:
  - The first prototype: the two sequences of elements starting at `first1` and `first2` are compared using the equality operator of the data type to which the iterators point. Comparison stops if the compared elements differ (i.e., `operator==` returns false) or `last1` is reached. A `pair` containing iterators pointing to the final positions is returned. The second sequence may contain more elements than the first sequence. The behavior of the algorithm is undefined if the second sequence contains fewer elements than the first sequence.
  - The second prototype: the two sequences of elements starting at `first1` and `first2` are compared using the binary comparison operation as defined by `comp`, instead of `operator==`. Comparison stops if the `comp` function returns `false` or `last1` is reached. A `pair` containing iterators pointing to the final positions is returned. The second sequence may contain more elements than the first sequence. The behavior of the algorithm is undefined if the second sequence contains fewer elements than the first sequence.
- Example:

          #include <algorithm>
          #include <string>
          #include <cstring>
          #include <iostream>
          #include <utility>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) == 0;
          }

          int main()
          {
              string range1[] = { "alpha", "bravo", "foxtrot", "hotel", "zulu" };
              string range2[] = { "alpha", "bravo", "foxtrot", "Hotel", "zulu" };
              pair<string *, string *> pss = mismatch(range1, range1 + 5, range2);

              cout << "The elements " << *pss.first << " and " << *pss.second <<
                      " differ at index " << (pss.first - range1) << '\n';
              if
              (
                  mismatch(range1, range1 + 5, range2, caseString).first
                  ==
                  range1 + 5
              )
                  cout << "When compared case-insensitively they match\n";
          }
          /*
              Displays:
                  The elements hotel and Hotel at offset 3 differ
                  When compared case-insensitively they match
          */

### 19.1.36: move / move_backward

- Header file: `<algorithm>`
- Function prototype:
  - `OutputIter move([ExecPol,] InputIter first, InputIter last, OutputIter dest);`
  - `BidirIter move_backward(BidirIter first, BidirIter last, BidirIter lastDest);`
- Description:
  - The first prototype: all elements reached from the iterator range `[first, last)` are moved to the range starting at `dest`, returning the iterator pointing just past the last element in the range starting at `dest`.
  - The Second prototype: all elements reached from the iterator range `[first, last)` are moved in reverse order to the range starting, iterating backward, at `lastDest`, returning the iterator pointing to the beginning of the range ending at `lastDest`. The destination iterator `lastDest` may not point to elements within the range `[first, last)`.
  Following `move(_backward)` the elements in the iterator range `[first, last)` are still valid, but may have changed.

  See also `shift_left` and `shift_right`: (cppreference).

- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <iterator>
          using namespace std;

          void show(string const *begin, string const *end)
          {
              copy(begin, end, ostream_iterator<string>(cout, ", "));
              cout << '\n';
          }

          int main()
          {
              string sarr[] = { "alpha", "bravo", "charley", "delta" };
              string dest[4] = { "", };

              auto last = end(sarr);

              auto lastDest = move(sarr, last, dest); // move all elements to dest

              cout << "sarr after move:\n";
              show(sarr, last);

              cout << "dest after move:\n";
              show(dest, lastDest);

              move_backward(dest, lastDest, last); // move_backward to sarr
              cout << "sarr after move_backward:\n";
              show(sarr, last);

              cout << "dest after move_backward:\n";
              show(dest, lastDest);
          }
          //  Displays:
          //    sarr after move:
          //    , , , ,
          //    dest after move:
          //    alpha, bravo, charley, delta,

### 19.1.37: next_permutation / prev_permutation

- Header file: `<algorithm>`
- Function prototypes:
  - `bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);`
  - `bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);`
  - `bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);`
  - `bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);`
- Description:
  - The first prototype: the next permutation, given the sequence of elements in the range `[first, last)`, is determined. For example, if the elements `1, 2` and `3` are the range for which `next_permutation` is called, then subsequent calls of `next_permutation` reorders the following series:

                1 2 3
                1 3 2
                2 1 3
                2 3 1
                3 1 2
                3 2 1

    This example shows that the elements are reordered such that each new permutation represents the next bigger value (132 is bigger than 123, 213 is bigger than 132, etc.) using `operator<` of the data type to which the iterators point. The value `true` is returned if a reordering took place, the value `false` is returned if no reordering took place, which is the case if the sequence represents the last (biggest) value. In that case, the sequence is also sorted using `operator<`.

  - The second prototype: the next permutation given the sequence of elements in the range `[first, last)` is determined, using the binary predicate `comp` to compare elements. The elements in the range are reordered. The value `true` is returned if a reordering took place, the value `false` is returned if no reordering took place, which is the case if the resulting sequence would haven been ordered using the binary predicate `comp` to compare elements.
  - The final two prototypes act identically to the first two prototypes, but instead of determining the next permutation the previous permutation is computed.
- Example:

          #include <algorithm>
          #include <iterator>
          #include <iostream>
          #include <string>
          #include <cstring>
          using namespace std;

          bool caseString(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) < 0;
          }

          // to obtain previous permutations change 'next_' to 'prev_'

          int main()
          {
              string saints[] = {"Oh", "when", "the", "saints"};

              cout << "All permutations of 'Oh when the saints':\n"
                      "Sequences:\n";
              do
              {
                  copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });
                  cout << '\n';
              }
              while (next_permutation(saints, saints + 4, caseString));

              cout << "After first sorting the sequence:\n";
              sort(saints, saints + 4, caseString);
              cout << "Sequences:\n";
              do
              {
                  copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });
                  cout << '\n';
              }
              while (next_permutation(saints, saints + 4, caseString));
          }
          //  Displays (partially):
          //      All permutations of 'Oh when the saints':
          //      Sequences:
          //      Oh when the saints
          //      saints Oh the when
          //      saints Oh when the
          //      saints the Oh when
          //      ...
          //      After first sorting the sequence:
          //      Sequences:
          //      Oh saints the when
          //      Oh saints when the
          //      Oh the saints when
          //      Oh the when saints
          //      ...

### 19.1.38: nth_element

- Header file: `<algorithm>`
- Function prototypes:
  - `void nth_element([ExecPol,] RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);`
  - `void nth_element([ExecPol,] RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: all elements in the range `[first, last)` are sorted relative to the element pointed to by `nth`: all elements in the range `[left, nth)` are smaller than the element pointed to by `nth`, and alle elements in the range `[nth + 1, last)` are greater than the element pointed to by `nth`. The two subsets themselves are not sorted. The `operator<` of the data type to which the iterators point is used to compare the elements.
  - The second prototype: all elements in the range `[first, last)` are sorted relative to the element pointed to by `nth`: all elements in the range `[left, nth)` are smaller than the element pointed to by `nth`, and alle elements in the range `[nth + 1, last)` are greater than the element pointed to by `nth`. The two subsets themselves are not sorted. The `comp` function object is used to compare the elements.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <iterator>
          #include <functional>
          using namespace std;

          int main()
          {
              int ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

              nth_element(ia, ia + 3, ia + 10);

              cout << "sorting with respect to " << ia[3] << '\n';
              copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
              cout << '\n';

              nth_element(ia, ia + 5, ia + 10, greater<int>());

              cout << "sorting with respect to " << ia[5] << '\n';
              copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      sorting with respect to 4
          //      1 2 3 4 9 7 5 6 8 10
          //      sorting with respect to 5
          //      10 8 7 9 6 5 3 4 2 1

### 19.1.39: partial_sort / partial_sort_copy

- Header file: `<algorithm>`
- Function prototypes:
  - `void partial_sort([ExecPol,] RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end);`
  - `void partial_sort([ExecPol,] RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, BinaryPredicate pred);`

  - `void partial_sort_copy([ExecPol,] InputIterator begin, InputIterator end, RandomAccessIterator dest_begin, RandomAccessIterator dest_end);`
  - `void partial_sort_copy([ExecPol,] InputIterator begin, InputIterator end, RandomAccessIterator dest_begin, RandomAccessIterator dest_end, BinaryPredicate pred);`
- Description:
  - The first prototype: the (`middle - begin`) smallest elements are sorted and stored in the range `[begin, middle)` using the `operator<` of the data type to which the iterators point to compare elements. The remaining elements of the series remain unsorted, and are stored in the range `[middle, end)`.
  - The second prototype: the (`middle - begin`) smallest elements (according to the provided binary predicate `pred`) are sorted and stored in the range `[begin, middle)`. The remaining elements of the series remain unsorted.
  - The last two prototypes act like, respectively, the first two prototypes, but instead of reordering the elements in the source iterator range the selected elements are copied to the destination iterator range. The number of elements that are copies is the smaller of the number of source-iterators and the number of destination iterators.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <functional>
          #include <iterator>
          using namespace std;

          int main()
          {
              int ia[] = { 1, 9, 5, 3, 7, 2, 4, 6, 8, 10 };
              int ia2[6];

              partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);
              cout << "the 6 smallest elements: ";
              copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
              cout << '\n';

              partial_sort(ia, ia + 3, ia + 10);

              cout << "find the 3 smallest elements:\n";
              copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
              cout << '\n';

              cout << "find the 5 largest elements:\n";
              partial_sort(ia, ia + 5, ia + 10, greater<int>());
              copy(ia, ia + 5, ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      the 6 smallest elements: 1 2 3 4 5 6
          //      find the 3 smallest elements:
          //      1 2 3
          //      find the 5 biggest elements:
          //      10 9 8 7 6

### 19.1.40: partial_sum

- Header file: `<numeric>`
- Function prototypes:
  - `OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);`
- Description:
  - The first prototype: each element in the range `[result, <returned OutputIterator>)` receives a value which is obtained by adding the elements in the corresponding range of the range `[first, last)`. The first element in the resulting range will be equal to the element pointed to by `first`.
  - The second prototype: the value of each element in the range `[result, <returned OutputIterator>)` is obtained by applying the binary operator `op` to the previous element in the resulting range and the corresponding element in the range `[first, last)`. The first element in the resulting range will be equal to the element pointed to by `first`.
  See also `inclusive_scan` and `exclusive_scan`, supporting execution policies: (cppreference).
- Example:

          #include <numeric>
          #include <algorithm>
          #include <iostream>
          #include <functional>
          #include <iterator>
          using namespace std;

          int main()
          {
              int ia[] = {1, 2, 3, 4, 5};
              int ia2[5];

              copy(ia2,
                  partial_sum(ia, ia + 5, ia2),
                  ostream_iterator<int>(cout, " "));
              cout << '\n';

              copy(ia2,
                  partial_sum(ia, ia + 5, ia2, multiplies<int>()),
                  ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          /*
              Displays:
                  1 3 6 10 15
                  1 2 6 24 120
          */

### 19.1.41: partition / partition_point / stable_partition

- Header file: `<algorithm>`
- Function prototype:
  - `BidirectionalIterator partition([ExecPol,] BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);`
  - `BidirectionalIterator stable_partition([ExecPol,] BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);`
  - `ForwardIterator partition_point( ForwardIterator first, ForwardIterator last, UnaryPredicate pred );`
- Description:
  - The first prototype: all elements in the range `[first, last)` for which the unary predicate `pred` evaluates as `true` are placed before the elements which evaluate as `false`.
  - The second prototype: identical to the first prototype, but the relative order of all elements for which the predicate evaluates to `false` and the relative order of all elements for which the predicate evaluates to `true` is kept.
  - The third prototype: does not reorder the elements in the `[first, last)` range, but returns an iterator to the first element for which `pred` returns `false`. If `pred` returns `true` for all elements then `last` is returned.
  The return value points just beyond the last element in the partitioned range for which `pred` evaluates as `true`.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <iterator>
          using namespace std;

          void show(int *begin, int *end)
          {
              copy(begin, end, ostream_iterator<int>{ cout, " " });
              cout << '\n';
          }

          int main()
          {
              int org[] = { 1, 3, 5, 7, 9, 10, 2, 8, 6, 4 };
              int ia[10];

              copy(org, org + 10, ia);

              auto lessThan4 = [=](int value)
                              {
                                  return value <= 4;
                              };

              int *split = partition(ia, ia + 10, lessThan4);

              cout << "Last ia[]- element <= 4 is ia[" << split - ia - 1 << "]\n";
              show(ia, end(ia));

              copy(org, org + 10, ia);
              split = stable_partition(ia, ia + 10, lessThan4);
              cout << "Last org[]-element <= 4 is ia[" << split - ia - 1 << "]\n";
              show(ia, end(ia));

              cout << "org[]-elements up to the partition point 4 are:\n";
              show(org, partition_point(org, org + 10, lessThan4));
          }
          //  Displays:
          //    Last ia[]- element <= 4 is ia[3]
          //    1 3 4 2 9 10 7 8 6 5
          //    Last org[]-element <= 4 is ia[3]
          //    1 3 2 4 5 7 9 10 8 6
          //    org[]-elements up to the partition point 4 are:
          //    1 3

### 19.1.42: partition_copy

- Header file: `<algorithm>`
- Function prototype:
  - `std::pair<ForwardIter2, ForwardIter3> partition_copy([ExecPol,] ForwardIter1 first, ForwardIter1 last, ForwardIter2 trueDest, ForwardIter3 falseDest, UnaryPredicate pred );`
- Description:
  - All elements reached from the iterator range `[first, last)` for which `pred` returns `true` are copied to the range starting at `trueDest`, while the remaining elements are copied to the range starting at `falseDest`. the range `[first, last)` may not overlap with the ranges starting at `trueDest` or `falseDest`.
- Example:

          #include <algorithm>
          #include <string>
          #include <iostream>
          #include <iterator>
          using namespace std;

          bool pred(std::string const &str)
          {
              return "aeiou"s.find(str.front()) != string::npos;
          }

          void show(string const *begin, string const *end)
          {
              copy(begin, end, ostream_iterator<string>(cout, ", "));
              cout << '\n';
          }

          int main()
          {
              string sarr[] =
                  {
                      "alpha", "bravo", "charley", "delta", "echo",
                      "foxtrot", "golf", "hotel"
                  };
              string trueDest[size(sarr)];
              string falseDest[size(sarr)];

              pair<string *, string *> lastTF =   // lastTrue, lastFalse
                  partition_copy(sarr, end(sarr), trueDest, falseDest, pred);

              cout << "pred() == true elements:\n";
              show(trueDest, lastTF.first);

              cout << "pred() == false elements:\n";
              show(falseDest, lastTF.second);

          }
          //  Displays:
          //    pred() == true elements:
          //    alpha, echo,
          //    pred() == false elements:
          //    bravo, charley, delta, foxtrot, golf, hotel,

### 19.1.43: reduce

- Header file: `<numeric>`
- Function prototypes:
  - `Type reduce([ExecPol,] InputIterator first, InputIterator last);`
  - `Type reduce([ExecPol,] InputIterator first, InputIterator last, Type init);`
  - `Type reduce([ExecPol,] InputIterator first, InputIterator last, BinaryOperation op);`
  - `Type reduce([ExecPol,] InputIterator first, InputIterator last, Type init, BinaryOperation op);`
- Description: This algorithm acts like `accumulate` (cf. accumulate), but the algorithm requires that the used operator is both associative and commutative: regrouping and rearranging the elements in any order may not affect the final outcome. E.g., the numeric addition operator satisfies both requirements.
  - The first prototype: `operator+` is applied to the elements in the range `[first, last)`, returning the resulting sum.
  - The second prototype: the binary operator `op` is applied to the initial value `init` (lhs argument) and, respectively, the elements from the iterator range `[first, last)`. The resulting sum value is returned.
  - The last two prototypes act like, respectively, the first two prototypes but instead of using `operator+` the binary operator `op` is used, receiving the variable that's eventually returned from the function as its lhs argument and the elements in the iterator range as its rhs argument, assigning the operator's returned values to the variable that's eventually returned.
- Example:

          // compile as: g++ -O2 reduce.cc -ltbb
          #include <numeric>
          #include <vector>
          #include <execution>
          #include <iostream>
          using namespace std;

          int main()
          {
              int         ia[] = {1, 2, 3, 4};
              vector<int> iv(ia, ia + 4);

                                  // for demonstration purpose: it's unlikely that
              cout <<             // for 4 values parallel execution is used
                  "Sum: " << reduce(execution::par,
                              iv.begin(), iv.end(), int()) << "\n"
                  "Product: " << reduce(iv.begin(), iv.end(), int(1),
                                                  multiplies<int>{}) << '\n';
          }
          //  Displays:
          //      Sum: 10
          //      Product: 24

### 19.1.44: remove / remove_if / remove_copy / remove_copy_if

- Header file: `<algorithm>`
- Function prototype:
  - `ForwardIterator remove([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &value);`

  - `OutputIterator remove_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator dest, Type const &value);`

  - `OutputIterator remove_copy_if([ExecPol,] InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred);`

  - `ForwardIterator remove_if([ExecPol,] ForwardIterator first, ForwardIterator last, UnaryPredicate pred);`
- Description:
  - The first prototype: elements in the range pointed to by `[first, last)` are reordered such that all values unequal to `value` are placed at the beginning of the range. The returned forward iterator points to the first element that can be removed after reordering. The range `[returnvalue, last)` is called the leftover of the algorithm. Note that the leftover may contain elements different from `value`, but these elements can be removed safely, as such elements are also present in the range `[first, returnvalue)`. The function uses `operator==` of the data type to which the iterators point to determine which elements to remove.
  - The second prototype: elements in the range pointed to by `[first, last)` not matching `value` are copied to the range `[dest, returnvalue)`, where `returnvalue` is the value returned by the function. The range `[first, last)` is not modified. The function uses `operator==` of the data type to which the iterators point to determine which elements not to copy.
  - The third prototype: the elements in the range pointed to by `[first, last)` for which the unary predicate `pred` returns `true` are not inserted into the `result` iterator. All other elements are copied to the range `[dest, returnvalue)`, where `returnvalue` is the value returned by the function. The range `[first, last)` is not modified.
  - The fourth prototype: the elements in the range pointed to by `[first, last)` are reordered such that all values for which the unary predicate `pred` returns `false` are placed at the beginning of the range, keeping their relative order. The returned forward iterator points to the first element, after reordering, for which `pred` returned `true`. The range `[returnvalue, last)` is called the leftover of the algorithm. The leftover may contain elements for which the predicate `pred` returns `false`, but these can safely be removed, as such elements are also present in the range `[first, returnvalue)`. Such duplication is the result of the fact that the algorithm copies, rather than moves elements into new locations.
  Note that the `copy`-overloads expect output iterators. If the kept elements are to be stored in, e.g., a vector `kept` then `kept.begin()` could be passed as the function's `dest` argument. However, that requires that `size(kept)` is large enough to contain all the kept elements, which must therefore be known before the function is called. Alternatively, `back_insert_iterator` could be used ensuring that `kept` merely contains the kept elements once the function has returned. This approach is used in the example program.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <iterator>
          #include <vector>
          using namespace std;
          using StrVect = vector<string>;

          bool judge(string const &word)
          {
              return count(word.begin(), word.end(), 'a') > 1;
          }

          void show(auto const &begin, auto const &end)
          {
              copy(begin, end, ostream_iterator<string>(cout, ", "));
              cout << "\n";
          }

          int main()
          {
              StrVect words =
                  {
                      "kilo", "alpha", "lima", "mike", "alpha", "november",
                      "alpha", "alpha", "alpha", "papa", "quebec"
                  };

              auto src{ words };

              cout << "Removing all \"alpha\"s:\n";
              auto end = remove(src.begin(), src.end(), "alpha");
              show(src.begin(), end);
              cout << "Leftover elements are:\n";
              show(end, src.end());

              src = words;
              cout << "Remove_copy_if removes words having > 1 'a' chars:\n";
              StrVect kept;
              remove_copy_if(src.begin(), src.end(), back_inserter(kept), judge);
              show(kept.begin(), kept.end());

          }
          //  Displays:
          //    Removing all "alpha"s:
          //    kilo, lima, mike, november, papa, quebec,
          //    Leftover elements are:
          //    alpha, alpha, alpha, , ,
          //    Remove_copy_if removes words having > 1 'a' chars:
          //    kilo, lima, mike, november, quebec,

### 19.1.45: replace / replace_if / replace_copy / replace_copy_if

- Header file: `<algorithm>`
- Function prototype:
  - `void replace([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &oldvalue, Type const &newvalue);`
  - `ForwardIterator replace_if([ExecPol,] ForwardIterator first, ForwardIterator last, UnaryPredicate pred, Type const &value);`
  - `OutputIterator replace_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, Type const &oldvalue, Type const &newvalue);`
  - `OutputIterator replace_copy_if([ExecPol,] ForwardIterator first, ForwardIterator last, OutputIterator result, UnaryPredicate pred, Type const &value);`
- Description:
  - The first predicate: all elements equal to `oldvalue` in the range pointed to by `[first, last)` are replaced by a copy of `newvalue`. The algorithm uses `operator==` of the data type to which the iterators point.
  - The second prototype: elements in the range pointed to by `[first, last)` for which the unary predicate `pred` evaluates as `true` are replaced by `value`.
  - The third prototype: all elements equal to `oldvalue` in the range pointed to by `[first, last)` are sent to the `result` output iterator, replacing elements equal to `oldValue` by `newValue`, using `operator==` of the data type to which the iterators point.
  - The fourth prototype: the elements in the range pointed to by `[first, last)` for which the unary predicate `pred` returns `false` are sent to the `result` output iterator, and `value` is sent to `result` if `pred` returns `true`. The range `[first, last)` is not modified.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <vector>
          #include <iterator>
          using namespace std;
          using StrVect = vector<string>;

          void show(StrVect const &vect)
          {
              copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));
              cout.put('\n');
          }

          bool isAlpha(string const &str)
          {
              return str == "alpha";
          }

          int main()
          {
              StrVect words =
                  {
                      "kilo", "alpha", "lima", "mike", "alpha", "november",
                      "alpha", "oscar", "alpha", "alpha", "papa"
                  };

              // replace(words.begin(), words.end(), "alpha"s, "ALPHA"s);
              // show(words);

              // or, using replace_if:
              //
              // replace_if(words.begin(), words.end(), isAlpha, "ALPHA"s);
              // show(words);

              // or, using replace_copy:
              //
              // StrVect result;
              // replace_copy(words.begin(), words.end(), result.begin(),
              //              "alpha"s, "ALPHA"s);
              // show(result);

              // or, using replace_copy_if:
              //
              //StrVect result;
              replace_copy_if(words.begin(), words.end(), back_inserter(result),
                           isAlpha, "ALPHA"s);
               show(result);
          }
          /*
              Displays
                  kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
          */

### 19.1.46: reverse / reverse_copy

- Header file: `<algorithm>`
- Function prototype:
  - `void reverse([ExecPol,] BidirectionalIterator first, BidirectionalIterator last);`
  - `OutputIterator reverse_copy([ExecPol,] BidirectionalIterator first, BidirectionalIterator last, OutputIterator dest);`
- Description:
  - The first prototype: the order of the elements in the range pointed to by `[first, last)` are reversed.
  - The second prototype: elements in the range pointed to by `[first, last)` are inserted in reversed order into `dest`, returning the output iterator following the last insertion.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <vector>
          #include <iterator>
          using namespace std;
          using StrVect = vector<string>;

          void show(StrVect const &vect)
          {
              copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));
              cout.put('\n');
          }

          int main(int argc, char **argv)
          {
              StrVect words =
                  {
                      "alpha", "kilo", "lima", "mike",
                      "november", "oscar", "papa"
                  };

              if (argc == 1)          // no args: plain reverse
              {
                  reverse(words.begin(), words.end());
                  show(words);
                  return 0;
              }

              using StrVect = vector<string>;
              StrVect dest;

              reverse_copy(words.begin(), words.end(),
                           back_inserter(dest));
              show(dest);
          }
          // Displays:
          //    papa oscar november mike lima kilo alpha

### 19.1.47: rotate / rotate_copy

- Header file: `<algorithm>`
- Function prototype:
  - `void rotate([ExecPol,] ForwardIterator first, ForwardIterator middle, ForwardIterator last);`
  - `OutputIterator rotate_copy([ExecPol,] ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);`
- Description:
  - The first prototype: elements in the range `[first, middle)` are moved to the end of the container, the elements in the range `[middle, last)` are moved to the beginning of the container, keeping the order of the elements in the two sub-ranges intact.
  - The elements in the range `[middle, last)` and then the elements in the range `[first, middle)` are inserted into `result`, returning the output iterator following the last insertion. The order of the elements in the source ranges is not altered.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <iterator>
          #include <vector>
          using namespace std;
          using StrVect = vector<string>;

          void show(StrVect const &vect)
          {
              copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));
              cout.put('\n');
          }

          int main(int argc, char **argv)
          {
              StrVect words =
                  {
                      "kilo", "lima", "mike", "november", "oscar",
                      "foxtrot", "golf", "hotel", "india", "juliet"
                  };

              if (argc == 1)          // no args: plain rotate
              {
                  rotate(words.begin(), words.begin() + words.size() / 2,
                         words.end());
                  show(words);
                  return 0;
              }

              using StrVect = vector<string>;
              StrVect dest;

              rotate_copy(words.begin(), words.begin() + words.size() / 2,
                          words.end(), back_inserter(dest));
              show(dest);
          }
          //  Displays:
          //      foxtrot golf hotel india juliet kilo lima mike november oscar

### 19.1.48: sample

- Header file: `<algorithm>`
- Function prototype:
  - `OutputIterator sample(InputIterator first, InputIterator last, OutputIterator out, size_t sampleSize, Generator &&generator);`
- Description:
  - `sampleSize` elements are randomly selected (without replacement) from the input range `[first, last)`, and copied to the destination range starting at `out` and ending at the function's return value. If `sampleSize >= (last - first)` all elements are selected. The `generator` is a (uniform) random number generator, like the `mt19937` mercenne twister.
  See also `shuffle`: (cppreference).

- Example:

          #include <algorithm>
          #include <iostream>
          #include <random>
          #include <string>

          using namespace std;

          int main()
          {
              string src{ "abcdefghijklmnopqrstuvwxyz" };
              string dest;

              sample(src.begin(), src.end(), back_inserter(dest), 7, mt19937{});

              std::cout << "Seven random letters out of " << src << " : " <<
                                                             dest << '\n';
          }
          //  Could display:
          //    Seven random letters out of abcdefghijklmnopqrstuvwxyz : bciorux

### 19.1.49: search / search_n

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator search([ExecPol,] ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2);`
  - `ForwardIterator1 search([ExecPol,] ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred);`
  - `constexpr ForwardIterator1 search([ExecPol,] ForwardIterator first, ForwardIterator last, Searcher const &searcher);`

  - `ForwardIterator search_n([ExecPol,] ForwardIterator first, ForwardIterator last, Size count, Type const &value);`
  - `ForwardIterator search_n([ExecPol,] ForwardIterator first1, ForwardIterator last1, Size count, Type const &value, BinaryPredicate pred);`

- Description:
  - The first prototype: an iterator into the first range `[first1, last1)` is returned where the elements in the range `[first2, last2)` are found using `operator==` of the data type to which the iterators point. If no such location exists, `last1` is returned.
  - The second prototype: an iterator into the first range `[first1, last1)` is returned where the elements in the range `[first2, last2)` are found using the provided binary predicate `pred` to compare the elements in the two ranges. If no such location exists, `last1` is returned.
  - The third prototype: returns `searcher(first, last).first`: `searcher` receives the range of elements, and returns an iterator into this range (or `last` if `searcher` found no match) as `searcher(first, last).first`.
  - The final two prototypes inspect the elements in the range `[first, last)` for the first series of `count` elements equal to `value`, returning the first iterator to those `count` elements. If no such series exists then `last` is returned. The last protottype calls `pred` to determine whether an element is equal to `value`.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <iterator>
          using namespace std;

          bool absEq(int i1, int i2)
          {
              return abs(i1) == abs(i2);
          }

          int main()
          {
              int range1[] =  {-2, -4, -6, -8, 2, 4, 4, 6, 8};
              int range2[] =  {6, 8};

              copy
              (
                  search(range1, end(range1), range2, range2 + 2),
                  end(range1), ostream_iterator<int>(cout, " ")
              );
              cout << '\n';

              copy
              (
                  search(range1, end(range1), range2, range2 + 2, absEq),
                  end(range1), ostream_iterator<int>(cout, " ")
              );
              cout << '\n';

              copy
              (
                  search_n(range1, end(range1), 2, 4, absEq),
                  end(range1), ostream_iterator<int>(cout, " ")
              );
              cout << '\n';
          }
          //  Displays:
          //      6 8
          //      -6 -8 2 4 4 6 8
          //      4 4 6 8

### 19.1.50: set_difference

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator set_difference([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_difference([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using `operator<` of the data type to which the iterators point.
  - The second prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cstring>
          #include <iterator>
          using namespace std;

          bool caseless(string const &left, string const &right)
          {
              return strcasecmp(left.c_str(), right.c_str()) < 0;
          }
          int main()
          {
              string set1[] = { "kilo", "lima", "mike", "november",
                                "oscar", "papa", "quebec" };
              string set2[] = { "papa", "quebec", "romeo"};
              string result[7];

              copy(result,
                  set_difference(set1, set1 + 7, set2, set2 + 3, result),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';

              string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

              copy(result,
                  set_difference(set1, set1 + 7, set3, set3 + 3, result,
                  caseless),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      kilo lima mike november oscar
          //      kilo lima mike november oscar

### 19.1.51: set_intersection

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator set_intersection([ExecPol,] InputIterator1 first1, InputIterator1) linebreak() tt(last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_intersection([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are also present in the range `[first2, last2)` is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using `operator<` of the data type to which the iterators point.
  - The second prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are also present in the range `[first2, last2)` is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cstring>
          #include <iterator>
          using namespace std;

          bool caseless(string const &left, string const &right)
          {
              return strcasecmp(left.c_str(), right.c_str()) < 0;
          }
          int main()
          {
              string set1[] = { "kilo", "lima", "mike", "november",
                                "oscar", "papa", "quebec" };
              string set2[] = { "papa", "quebec", "romeo"};
              string result[7];

              copy(result,
                  set_intersection(set1, set1 + 7, set2, set2 + 3, result),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';

              string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

              copy(result,
                  set_intersection(set1, set1 + 7, set3, set3 + 3, result,
                                                                   caseless),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      papa quebec
          //      papa quebec

### 19.1.52: set_symmetric_difference

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator set_symmetric_difference([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_symmetric_difference([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` and those in the range `[first2, last2)` that are not present in the range `[first1, last1)` is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using `operator<` of the data type to which the iterators point.
  - The second prototype: a sorted sequence of the elements pointed to by the range `[first1, last1)` that are not present in the range `[first2, last2)` and those in the range `[first2, last2)` that are not present in the range `[first1, last1)` is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using the `comp` function object.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cstring>
          #include <iterator>
          using namespace std;

          bool caseless(string const &left, string const &right)
          {
              return strcasecmp(left.c_str(), right.c_str()) < 0;
          }
          int main()
          {
              string set1[] = { "kilo", "lima", "mike", "november",
                                "oscar", "papa", "quebec" };
              string set2[] = { "papa", "quebec", "romeo"};
              string result[7];

              copy(result,
                  set_symmetric_difference(set1, set1 + 7, set2, set2 + 3,
                                                                 result),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';

              string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

              copy(result,
                  set_symmetric_difference(set1, set1 + 7, set3, set3 + 3,
                                                           result, caseless),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      kilo lima mike november oscar romeo
          //      kilo lima mike november oscar ROMEO

### 19.1.53: set_union

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator set_union([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);`
  - `OutputIterator set_union([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);`
- Description:
  - The first prototype: a sorted sequence of the elements that are present in either the range `[first1, last1)` or the range `[first2, last2)` or in both ranges is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using `operator<` of the data type to which the iterators point;
  - The second prototype: a sorted sequence of the elements that are present in either the range `[first1, last1)` or the range `[first2, last2)` or in both ranges is returned, starting at `result`, and ending at the `OutputIterator` returned by the function. The elements in the two ranges must have been sorted using `comp` function object.
  Note that in the final range each element appears only once, unless there are already duplicate elements in the sources, in which case they will also appear multiple times in the result;
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cstring>
          #include <iterator>
          #include <vector>
          using namespace std;

          bool caseless(string const &left, string const &right)
          {
              return strcasecmp(left.c_str(), right.c_str()) < 0;
          }

          int main()
          {
              string set1[] =
                  {
                      "kilo", "lima", "mike", "november",
                      "oscar", "papa", "quebec"
                  };
              string set2[] = { "papa", "quebec", "romeo"};
              string result[8];

              copy(result,
                  set_union(set1, set1 + 7, set2, set2 + 3, result),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';

              string set3[] = { "PAPA", "QUEBEC", "ROMEO"};

              copy(result,
                  set_union(set1, set1 + 7, set3, set3 + 3, result, caseless),
                  ostream_iterator<string>(cout, " "));
              cout << '\n';

              std::vector<int> v1 = {1, 2, 3,        4, 5, 5, 5};
              std::vector<int> v2 = {      3, 3, 3,  4, 5,       6, 7};

              set_union(v1.begin(), v1.end(), v2.begin(), v2.end(),
                         ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          //  Displays:
          //      kilo lima mike november oscar papa quebec romeo
          //      kilo lima mike november oscar papa quebec ROMEO
          //      1 2 3 3 3 4 5 5 5 6 7

### 19.1.54: sort / stable_sort

- Header file: `<algorithm>`
- Function prototypes:
  - `void sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last);`
  - `void sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
  - `void stable_sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last);`
  - `void stable_sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: the elements in the range `[first, last)` are sorted in ascending order using `operator<` of the data type to which the iterators point.
  - The second prototype: the elements in the range `[first, last)` are sorted in ascending order using the `comp` function object to compare the elements. The binary predicate `comp` should return `true` if its first argument should be placed earlier in the sorted sequence than its second argument.
  - The last two prototypes are used identically to the first two prototypes, but use stable-sorting, keeping the initial order of equal elements.
- Example:

          // compile as: g++ -O2 sort.cc -ltbb
          #include <algorithm>
          #include <cstdlib>
          #include <execution>
          #include <functional>
          #include <iostream>
          #include <iterator>
          #include <string>
          using namespace std;

          int main()
          {
              string words[] =
                      {
                          "november", "kilo", "mike", "lima",
                          "oscar", "quebec", "papa"
                      };

              sort(words, words + 7);
              copy(words, words + 7, ostream_iterator<string>(cout, " "));
              cout << '\n';

              sort(words, words + 7, greater<string>());
              copy(words, words + 7, ostream_iterator<string>(cout, " "));
              cout << '\n';

              int *vect = new int[10'000];
              generate(execution::par, vect, vect + 10'000, random);
              cout << "sorted: " << is_sorted(vect, vect + 10'000) << '\n';

              sort(execution::par, vect, vect + 10'000);
              cout << "sorted: " << is_sorted(vect, vect + 10'000) << '\n';

              delete[] vect;

              // stable-sorting:

              using Pair = pair<size_t, string>;  // days & nrs of the months
              vector<Pair> months =
              {
                  { 31, "Jan." }, { 28, "Feb." }, { 31, "Mar." }, { 30, "Apr." },
                  { 31, "May." }, { 30, "Jun." }, { 31, "Jul." }, { 31, "Aug." },
                  { 30, "Sep." }, { 31, "Oct." }, { 30, "Nov." }, { 31, "Dec." },
              };

              stable_sort(months.begin(), months.end(),
                          [&](Pair const &lhs, Pair const &rhs)
                          {
                              return lhs.first > rhs.first;
                          }
              );

              for (size_t idx = 0; auto const &month: months)
                  cout << month.first << ": " << month.second <<
                      (++idx % 4 == 0 ? "\n" : "  ");

          }
          //  Displays:
          //      kilo lima mike november oscar papa quebec
          //      quebec papa oscar november mike lima kilo
          //      unordered sequence
          //      sorted sequence
          //      31: Jan.  31: Mar.  31: May.  31: Jul.
          //      31: Aug.  31: Oct.  31: Dec.  30: Apr.
          //      30: Jun.  30: Sep.  30: Nov.  28: Feb.

  The example also shows two generic algorithms using the `execution::par` execution policy: first `generate` is used to fill an array with randomly determined `int`-values, then `sort` is used to sort those values.

### 19.1.55: swap / swap_ranges

- Header file: `<algorithm>`
- Function prototypes:
  - `void swap(Type &object1, Type &object2) noexcept;`
  - `void swap(Type (&object1)[N], Type (&object2))[N] noexcept;`
  - `ForwardIterator2 swap_ranges([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result);`
- Description:
  - The first prototype: the elements `object1` and `object2` exchange their values. They do so by either cyclic copy assignment or cyclic move assignment (if available).
  - The second prototype: the elements of the (compile-time) known sizes of the `object1` and `object2` arrays exchange their values.
  - The third prototype: elements in the range pointed to by `[first1, last1)` are swapped with that number of elements in the range `[result, returnvalue)`, where `returnvalue` is the value returned by the function. The two ranges must be disjoint.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <iterator>
          using namespace std;

          void show(string const *begin, string const *end)
          {
              copy(begin, end, ostream_iterator<string>(cout, " "));
              cout << '\n';
          }

          int main()
          {
              string first[] = { "alpha", "bravo", "charley" };
              string second[] = { "echo", "foxtrot", "golf" };

              cout << "Before:\n";
              show(first, end(first));
              show(second, end(second));

              for (size_t idx = 0; idx < size(first); ++idx)
                  swap(first[idx], second[idx]);

              cout << "After:\n";
              show(first, end(first));
              show(second, end(second));

              swap_ranges(first, end(first), second);

              cout << "After swap_ranges:\n";
              show(first, end(first));
              show(second, end(second));

          }
          //  Displays:
          //    Before:
          //    alpha bravo charley
          //    echo foxtrot golf
          //    After:
          //    echo foxtrot golf
          //    alpha bravo charley
          //    After swap_ranges:
          //    alpha bravo charley
          //    echo foxtrot golf

### 19.1.56: transform

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator transform([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, UnaryOperator op);`
  - `OutputIterator transform([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperator op);`
- Description:
  - The first prototype: the unary operator `op` is applied to each of the elements in the range `[first, last)`, and the resulting values are stored in the range starting at `result`. The return value points just beyond the last generated element.
  - The second prototype: the binary operator `op` is applied to each of the elements in the range `[first1, last1)` and the corresponding element in the second range starting at `first2`. The resulting values are stored in the range starting at `result`. The return value points just beyond the last generated element.
- Example:

          #include <functional>
          #include <vector>
          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cctype>
          #include <iterator>
          using namespace std;

          string caps(string const &src)
          {
              string tmp;
              tmp.resize(src.length());

              transform(src.begin(), src.end(), tmp.begin(), ::toupper);
              return tmp;
          }
          int main()
          {
              string words[] = {"alpha", "bravo", "charley"};

              copy(words, transform(words, words + 3, words, caps),
                                      ostream_iterator<string>(cout, " "));
              cout << '\n';

              int         values[] = {1, 2, 3, 4, 5};
              vector<int> squares;

              transform(values, values + 5, values,
                                      back_inserter(squares), multiplies<int>());

              copy(squares.begin(), squares.end(),
                                      ostream_iterator<int>(cout, " "));
              cout << '\n';
          }
          /*
              Displays:
                  ALPHA BRAVO CHARLEY
                  1 4 9 16 25
          */

the following differences between the `for_each` (section 19.1.18) and `transform` generic algorithms should be noted:

- With `transform` the return value of the function object's `operator()` member is used; the argument that is passed to the `operator()` member itself is not changed.
- With `for_each` the function object's `operator()` receives a reference to an argument, which itself may be changed by the function object's `operator()`.

Also note that the range-based for loop can often be used instead of the `transform` generic algorithm. However, but different from the range-based for-loop the `transform` algorithm can also be used width sub-ranges and with reverse-iterators.

### 19.1.57: transform_reduce

- Header file: `<numeric>`
- Function prototypes:
  - `Type transform_reduce([ExecPol,] InputIterator first1, InputIterator last1, InputIterator first2, Type value);`

  - `Type transform_reduce([ExecPol,] InputIterator first1, InputIterator last1, InputIterator first2, Type value, BinaryOperation reduce, BinaryOperation transform);`

  - `Type transform_reduce([ExecPol,] InputIterator first1, InputIterator last1, Type value, BinaryOperation reduce, UnaryOperation transform);`
- Description:
  - The first prototype: equals the second prototype using `std::plus<>` for the `reduce` binary operator and `std::mutiplies<>` for the `transform` binary operator. It's also equivalent to a parallelized version of `inner_product` (cf. section 19.1.21).
  - The second prototype: applies the `transform` binary operation to, as left-hand side operand, each element in the `[first1, end1)` range and as right-hand side operand the corresponding element of the range starting at `first2`. Each thus computed value is passed as right-hand side operand, using `value` as left-hand side operand to the `reduce` binary operation, returning the final value returned by `reduce`.
  - The third prototype: applies `transform` to each element of the range `[first1, end1)`, and then passes `value` and each of the values returned by `transform` to `reduce`, returning the final value returned by `reduce`.

- Example:

          #include <numeric>
          #include <algorithm>
          #include <iterator>
          #include <iostream>
          #include <string>
          using namespace std;

          class Cat
          {
              std::string  d_sep;
              public:
                  Cat(string const &sep)
                  :
                      d_sep(sep)
                  {}
                  string operator()
                      (string const &s1, string const &s2) const
                  {
                      return s1 + d_sep + s2;
                  }
          };
          int main()
          {
              size_t ia1[] = { 1, 2, 3, 4, 5, 6, 7 };

                          // instead of inner_product:
              cout << "The sum of all squares in ";
              copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
              cout << "is " << transform_reduce(ia1, ia1 + 7, ia1, 0) << '\n';

              size_t ia2[] = { 7, 6, 5, 4, 3, 2, 1 };

              cout << "The sum of all cross-products in ";
              copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
              cout << "and ";
              copy(ia2, ia2 + 7, ostream_iterator<size_t>{ cout, " " });
              cout << "is " << transform_reduce(ia1, ia1 + 7, ia2, 0) << '\n';

              string names1[] = { "Frank", "Karel", "Piet" };
              string names2[] = { "Brokken", "Kubat", "Plomp"};

              cout << "All combined names of ";
              copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });
              cout << "and ";
              copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });
              cout << "are:" <<
                  transform_reduce(names1, names1 + 3, names2, "\t"s,
                      Cat{ "\n\t"}, Cat{ " " }) << '\n';
          }
          // Displays:
          //  The sum of all squares in 1 2 3 4 5 6 7 is 140
          //  The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84
          //  All combined names of Frank Karel Piet and Brokken Kubat Plomp are:
          //          Frank Brokken
          //          Karel Kubat
          //          Piet Plomp

### 19.1.58: handling uninitialized memory

Section 9.1.5 covers the placement new operator. The placement new operator is used to install values or objects in 'raw memory', i.e., memory that is already available, but hasn't yet been initialized for the intended object types.

As covered before, when calling something like `auto ptr = new string{ "hello" }` the string is constructed in memory specifically allocated to contain the object, and the object type's constructor initializes the object in that memory. Likewise, when calling `delete ptr` the string's destructor is called, followed by returning the memory allocated by `new` to the common pool.

When using placement new the memory to contain the object is already available, and the construction `auto ptr = new (storageAddress) string{ "hello" }` is used to merely construct the string at the location specified by `storageAddress`. That string can then (as usual) be accessed via `ptr`, but `delete ptr` cannot be used, since the memory at `storageAddress` was already available before invoking the placement new operator. Therefore, in these cases the remarkable situation is encountered where the object's destructor must explicitly be called (using `ptr->~string()`) and using `delete ptr` is completely wrong, causing a memory error which aborts the program.

Several generic algorithms, all supporting execution policies, are available simplifying the use of `placement new`. To use these algorithm the `<memory>` header file must be included.

Facilities are available to copy, fill, initialize, and move objects to/in uninitialized (raw) memory, as well as facilities to delete the objects stored in raw memory. Here is an overvieuw of the available facilities (cf. cppreference for more details about the algorithms handling uninitialized memory):

- `uninitialized_copy([ExecPol,] ForwardIterator first, ForwardIterator last, ForwardIterator dest);`
  copies the elements in the `[first, last)` to the raw memory starting at `dest`, returning the location beyond the last copied element.
- `uninitialized_copy_n([ExecPol,] ForwardIterator first, size_t nObjects, ForwardIterator dest);`
  same as the previous algorithm, but copies `nObjects`.
- `uninitialized_default_construct([ExecPol,] ForwardIterator first, ForwardIterator last);`
  installs default constructed values at the raw memory locations reached by the iterator range `[first, last)`. The algorithm requires that the types referred to by the iterators are either trivial types (like built-in types) or define `value_type` returning their type names. When using trivial types the installed do not assume that the installed values are 0-initialized.
- `uninitialized_default_construct_n([ExecPol,] ForwardIterator first, size_t nObjects);`
  same as the previous algorithm, but installs `nObjects` in the uninitialized memory.
- `uninitialized_fill([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &value);`
  like the first algorithm, but installing copies of `value` in the uninitialized memory.
- `uninitialized_fill([ExecPol,] ForwardIterator first, size_t nObjects,Type const &value);`
  same as the previous algorithm, but copies `value` to the `nObjects` subsequent locations in the uninitialized memory.
- `uninitialized_move([ExecPol,] ForwardIterator first, ForwardIterator last, ForwardIterator dest);`
  same as the first algorithm, but the elements in the `[first, last)` are moved to the raw memory.
- `uninitialized_move_n([ExecPol,] ForwardIterator first, size_t nObjects, ForwardIterator dest);`
  same as the previous algorithm, but `nObjects` are moved.
- `uninitialized_value_construct([ExecPol,] ForwardIterator first, ForwardIterator last);`
  same as `uninitialized_default_construct`, but requires that the types referred to by the iterators define `value_type` returning their type names.
- `uninitialized_value_construct_n([ExecPol,] ForwardIterator first, size_t nObjects);`
  same as the previous algorithm, but installs `nObjects` in the uninitialized memory.

The algorithm `Type *construct_at(Type *raw, Args &&...args)` constructs an object of type `Type` in the raw memory at `raw`, passing `args...` to `Type's` constructor.

To delete the objects installed in raw memory the following facilities are available:

- `void destroy([ExecPol,] ForwardIterator first, ForwardIterator last);`
  assuming the the types to which `first` refers: it calls `iterator->~Type()` for all elements in the range `[first, last)`.
- `void destroy([ExecPol,] ForwardIterator first, size_t nObjects);`
  same as the previous algorithm, but calls the destructors of `nObjects` objects.
- `void destroy_at(Type *raw);`
  calls the destructor of the object installed at `raw` using placement new. If the `raw` pointer points to an array of placement new allocated objects then the destructors of the elements of the array are called.

Here is an example:

        #include <memory>
        #include <vector>
        #include <iostream>
        #include <string>
        using namespace std;

        int main()
        {
            char raw[4 * sizeof(string)];       // raw memory to receive strings
            string *ptr = reinterpret_cast<string *>(raw);  // pointer to strings

                                                // construct 4 strings in raw
            uninitialized_default_construct_n(ptr, 4);
            destroy(ptr, ptr + 4);              // call the strings' destructors

            vector<string> vs(4, "string");     // move 4 strings to raw memory
            uninitialized_move(vs.begin(), vs.end(), ptr);

            cout << vs.front() << ", " << vs.back() << '\n' <<
                    ptr[0] << ", " << ptr[3] << '\n';

            destroy(ptr, ptr + 4);              // call the strings' destructors
        }
        //  Displays:
        //      ,
        //      string, string

### 19.1.59: unique

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator unique([ExecPol,] ForwardIterator first, ForwardIterator last);`
  - `ForwardIterator unique([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);`
  - `OutputIterator unique_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator unique_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);`
- Description:
  The `std::unique` generic algorithm assumes that the elements in the range have previously been sorted (cf. section 19.1.54).
  - The first prototype: using `operator==` of the data type to which the iterators point, all but the first of consecutively equal elements in the range pointed to by `[first, last)` are relocated to the end of the range. The returned forward iterator marks the beginning of the leftover. All elements in the range `[first, return-value)` are unique, all elements in the range `[return-value, last)` have undetermined (but valid) values.
  - The second prototype: all but the first of consecutive elements in the range pointed to by `[first, last)` for which the binary predicate `pred` returns `true` are relocated to the end of the range. The predicate `pred` expects two arguments of the data type to which the iterators point. The returned forward iterator marks the beginning of the leftover. For all pairs of elements in the range `[first, return-value)` `pred` returns `false` (i.e., they are unique). All elements in the leftover (i.e., the range `[return-value, last)`) have undetermined (but valid) values.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <cstring>
          #include <iterator>
          using namespace std;

          bool casestring(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) == 0;
          }

          int main()
          {
              string words[] = {"alpha", "alpha", "Alpha", "papa", "quebec" };
              size_t const size = sizeof(words) / sizeof(string);

              string *removed = unique(words, words + size);
              copy(words, removed, ostream_iterator<string>(cout, " "));
              cout << '\n'
                   << "Trailing elements are:\n";
              copy(removed, words + size, ostream_iterator<string>(cout, " "));
              cout << '\n';

              removed = unique(words, words + size, casestring);
              copy(words, removed, ostream_iterator<string>(cout, " "));
              cout << '\n'
                   << "Trailing elements are:\n";
              copy(removed, words + size, ostream_iterator<string>(cout, " "));
              cout << '\n';
          }
          /*
              Displays:
                  alpha Alpha papa quebec
                  Trailing elements are:
                  quebec
                  alpha papa quebec
                  Trailing elements are:
                  quebec quebec
          */

### 19.1.60: unique_copy

- Header file: `<algorithm>`
- Function prototypes:
  - `OutputIterator unique_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator result);`
  - `OutputIterator unique_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);`
- Description:
  - The first prototype: the elements in the range `[first, last)` are copied to the resulting container, starting at `result`. Consecutively equal elements (using `operator==` of the data type to which the iterators point) are copied only once (keeping the first of a series of equal elements). The returned output iterator points just beyond the last copied element.
  - The second prototype: the elements in the range `[first, last)` are copied to the resulting container, starting at `result`. Consecutive elements in the range pointed to by `[first, last)` for which the binary predicate `pred` returns `true` are copied only once (keeping the first of a series of equal elements). The returned output iterator points just beyond the last copied element.
- Example:

          #include <algorithm>
          #include <iostream>
          #include <string>
          #include <vector>
          #include <iterator>
          #include <cstring>
          using namespace std;

          bool casestring(string const &first, string const &second)
          {
              return strcasecmp(first.c_str(), second.c_str()) == 0;
          }
          int main()
          {
              string words[] = {"oscar", "Alpha", "alpha", "alpha",
                                                              "papa", "quebec" };
              size_t const size = sizeof(words) / sizeof(string);
              vector<string> remaining;

              unique_copy(words, words + size, back_inserter(remaining));

              copy(remaining.begin(), remaining.end(),
                      ostream_iterator<string>(cout, " "));
              cout << '\n';

              vector<string> remaining2;

              unique_copy(words, words + size,
                                      back_inserter(remaining2), casestring);

              copy(remaining2.begin(), remaining2.end(),
                      ostream_iterator<string>(cout, " "));
              cout << '\n';
          }
          /*
              Displays:
                  oscar Alpha alpha papa quebec
                  oscar Alpha papa quebec
          */

### 19.1.61: upper_bound

- Header file: `<algorithm>`
- Function prototypes:
  - `ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, Type const &value);`
  - `ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, Type const &value, Compare comp);`
- Description:

  - The first prototype: the sorted elements (using ascending sort) reached from the iterator range `[first, last)` are searched for the first element that is greater than `value`. The returned iterator marks the first location in the sequence where `value` can be inserted without breaking the sorted order of the elements using `operator<` of the data type to which the iterators point. If no such element is found, `last` is returned.

  - The second prototype: the elements reached from the iterator range `[first, last)` must have been sorted using the `comp` function or function object. Each element in the range is compared to `value` using the `comp` function. An iterator is returned pointing to the first element for which the binary predicate `comp`, applied to the elements of the range and `value`, returns `true`. The `comp` function object function's first parameter refers to `value` and the function object's second parameter refers to an element in the iterator range.

    Caveat: note that the `comp` object's parameters when using `upper_bound` are swapped compared to the parameters expected by `lower_bound`.

  - When the values in the iterator range were sorted in ascending order (i.e., using `operator<`) then `upper_bound` returns an iterator pointing beyond the last of a series of values equal to `value`, while `lower_bound` returns an iterator pointing to the first of such a series of equal values.

    When the iterator range contains a series of values which are, according to `comp`, equal to `value` then `upper_bound` returns an iterator to the first element beyond that series, while `lower_bound` returns an iterator to the first element of that series.

    The following program illustrates the various possibilities. Th program illustrates both `lower_bound` and `upper_bound` and also illustrates the situation where `value' Type` is unequal to the types of the values in the iterator range. Specific comment is provided below the program's code.

- Example:

       1: #include <algorithm>
       2: #include <iostream>
       3: using namespace std;
       4:
       5: int main()
       6: {
       7:     using pic =  pair<int, char>;
       8:
       9:     pic picArr[] =
      10:         { {1, 'f'}, {5, 'r'}, {5, 'a'}, {7, 'n'}, {8, 'k'} };
      11:     pic *picArrEnd = picArr + size(picArr);
      12:
      13:     cout << "Sequence: ";
      14:     for (auto &pair: picArr)
      15:         cout << '{' << pair.first << ',' << pair.second << "}, ";
      16:     cout << '\n';
      17:
      18:     auto iter = lower_bound(picArr, picArrEnd, 5,
      19:                     [&](pic const &range, int value)
      20:                     {
      21:                         return range.first < value;
      22:                     }
      23:                 );
      24:     cout << "  lower bound, <,  {5,?} can be inserted before {" <<
      25:                 iter->first << ',' << iter->second << "}\n";
      26:
      27:     iter = upper_bound(picArr, picArrEnd, 5,
      28:                     [&](int value, pic const &range)
      29:                     {
      30:                         return value < range.first;
      31:                     }
      32:                 );
      33:     cout << "  upper_bound, <,  {5,?} can be inserted before {" <<
      34:                 iter->first << ',' << iter->second << "}\n";
      35:
      36:     iter = upper_bound(picArr, picArrEnd, 9,
      37:                     [&](int value, pic const &range)
      38:                     {
      39:                         return value < range.first;
      40:                     }
      41:                 );
      42:     cout << "  upper_bound, <,  {9,?} can be inserted " <<
      43:                 ( &*iter == picArrEnd ? "at the end" : "???") << '\n';
      44:
      45:     sort(picArr, picArrEnd,
      46:         [](pic const &lhs, pic const &rhs)
      47:         {
      48:             return lhs.first > rhs.first;
      49:         }
      50:     );
      51:
      52:     cout << "\nSequence: ";
      53:     for (auto &pair: picArr)
      54:         cout << '{' << pair.first << ',' << pair.second << "}, ";
      55:     cout << '\n';
      56:
      57:     iter = lower_bound(picArr, picArrEnd, 5,
      58:                     [&](pic const &range, int value)
      59:                     {
      60:                         return range.first > value;
      61:                     }
      62:                 );
      63:     cout << "  lower_bound, >,  {5,?} can be inserted before {" <<
      64:                 iter->first << ',' << iter->second << "}\n";
      65:
      66:     iter = upper_bound(picArr, picArrEnd, 5,
      67:                     [&](int value, pic const &range)
      68:                     {
      69:                         return value > range.first;
      70:                     }
      71:                 );
      72:     cout << "  upper_bound, >,  {5,?} can be inserted before {" <<
      73:                 iter->first << ',' << iter->second << "}\n";
      74:
      75:     iter = upper_bound(picArr, picArrEnd, 0,
      76:                     [&](int value, pic const &range)
      77:                     {
      78:                         return value > range.first;
      79:                     }
      80:                 );
      81:     cout << "  upper_bound, >,  {0,?} can be inserted " <<
      82:                 ( &*iter == picArrEnd ? "at the end" : "???") << '\n';
      83: }
      84: // Displays:
      85: // Sequence: {1,f}, {5,r}, {5,a}, {7,n}, {8,k},
      86: //   lower bound, <,  {5,?} can be inserted before {5,r}
      87: //   upper_bound, <,  {5,?} can be inserted before {7,n}
      88: //   upper_bound, <,  {9,?} can be inserted at the end
      89: //
      90: // Sequence: {8,k}, {7,n}, {5,r}, {5,a}, {1,f},
      91: //   lower_bound, >,  {5,?} can be inserted before {5,r}
      92: //   upper_bound, >,  {5,?} can be inserted before {1,f}
      93: //   upper_bound, >,  {0,?} can be inserted at the end

  - Lines 7 thru 12: the iterator range consists of a series of `pairs`, sorted by their `first` members.
  - Lines 18 thru 23: `lower_bound` is called using a lambda expression to define the `Compare` function object. Note (line 19) that a reference to a value in the iterator range is the lambda expression's first parameter, while the target value is its second parameter.
  - Lines 27 thru 32: here `upper_bound` is called, also using a lambda expression. With `upper_bound` the target value is the lambda expression's first parameter, while a reference to a value in the iterator range is its second parameter.
  - Lines 57 thru 62, 66 thru 71, and 75 thru 80: after sorting the values in the `picArr` array in descending order `lower_bound` and `upper_bound` are again used. This time instead of using the `<` operator the `>` operator should be used.

The binary_search generic algorithm can be used to simply determine whether or nog `value` is present in the iterator range. The lower_bound generic algorithm can be used to find the first element of a series of values equal to `value`.

### 19.1.62: Heap algorithms

A heap is a kind of binary tree which can be represented by an array. In the standard heap, the key of an element is not smaller than the key of its children. This kind of heap is called a max heap. A tree in which numbers are keys could be organized as shown in figure 25.

Figure 25: A binary tree representation of a heap
Such a tree may also be organized in an array:

            12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5

In the following description, keep two pointers into this array in mind: a pointer `node` indicates the location of the next node of the tree, a pointer `child` points to the next element which is a child of the `node` pointer. Initially, `node` points to the first element, and `child` points to the second element.

- `*node++ (== 12)`. 12 is the top node. its children are `*child++` (11) and `*child++` (10), both less than 12.
- The next node (`*node++ (== 11)`), in turn, has `*child++` (8) and `*child++` (9) as its children.
- The next node (`*node++ (== 10)`) has `*child++` (7) and `*child++` (6) as its children.
- The next node (`*node++ (== 8)`) has `*child++` (1) and `*child++` (2) as its children.
- Then, node (`*node++ (== 9)`) has children `*child++` (4) and `*child++` (3).
- Finally (as far as children are concerned) (`*node++ (== 7)`) has one child `*child++` (5)

Since `child` now points beyond the array, the remaining nodes have no children. So, nodes 6, 1, 2, 4, 3 and 5 don't have children.

Note that the left and right branches are not ordered: 8 is less than 9, but 7 is larger than 6.

A heap is created by traversing a binary tree level-wise, starting from the top node. The top node is 12, at the zeroth level. At the first level we find 11 and 10. At the second level 8, 9, 7 and 6 are found, etc.

Heaps can be constructed in containers supporting random access. So, a list is not an appropriate data structure for a heap. Heaps can be constructed from an (unsorted) array (using `make_heap`). The top-element can be pruned from a heap, followed by reordering the heap (using `pop_heap`), a new element can be added to the heap, followed by reordering the heap (using `push_heap`), and the elements in a heap can be sorted (using `sort_heap`, which, of course, invalidates the heap).

#### 19.1.62.1: The `make_heap' function

- Header file: `<algorithm>`
- Function prototypes:
  - `void make_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: the elements in the range `[first, last)` are reordered to form a max-heap using `operator<` of the data type to which the iterators point.
  - The second prototype: the elements in the range `[first, last)` are reordered to form a max-heap using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `make_heap`.

#### 19.1.62.2: The `pop_heap' function

- Header file: `<algorithm>`
- Function prototypes:
  - `void pop_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: the first element in the range `[first, last)` is moved to `last - 1`. Then, the elements in the range `[first, last - 1)` are reordered to form a max-heap using the `operator<` of the data type to which the iterators point.
  - The second prototype: the first element in the range `[first, last)` is moved to `last - 1`. Then, the elements in the range `[first, last - 1)` are reordered to form a max-heap using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `pop_heap`.

#### 19.1.62.3: The `push_heap' function

- Header file: `<algorithm>`
- Function prototypes:
  - `void push_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: assuming that the range `[first, last - 1)` contains a valid heap, and the element at `last - 1` contains an element to be added to the heap, the elements in the range `[first, last - 1)` are reordered to form a max-heap using the `operator<` of the data type to which the iterators point.
  - The second prototype: assuming that the range `[first, last - 1)` contains a valid heap, and the element at `last - 1` contains an element to be added to the heap, the elements in the range `[first, last - 1)` are reordered to form a max-heap using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `push_heap`.

#### 19.1.62.4: The `sort_heap' function

- Header file: `<algorithm>`
- Function prototypes:
  - `void sort_heap(RandomAccessIterator first, RandomAccessIterator last);`
  - `void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);`
- Description:
  - The first prototype: assuming the elements in the range `[first, last)` form a valid max-heap, the elements in the range `[first, last)` are sorted using `operator<` of the data type to which the iterators point.
  - The second prototype: assuming the elements in the range `[first, last)` form a valid heap, the elements in the range `[first, last)` are sorted using the binary comparison function object `comp` to compare elements.
- Follow this link for a small example of a program using `sort_heap`.

#### 19.1.62.5: An example using the heap functions

Here is an example showing the various generic algorithms manipulating heaps:

        #include <algorithm>
        #include <iostream>
        #include <functional>
        #include <iterator>
        using namespace std;

        void show(int *ia, char const *header)
        {
            cout << header << ":\n";
            copy(ia, ia + 20, ostream_iterator<int>(cout, " "));
            cout << '\n';
        }
        int main()
        {
            int ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                        11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

            make_heap(ia, ia + 20);
            show(ia, "The values 1-20 in a max-heap");

            pop_heap(ia, ia + 20);
            show(ia, "Removing the first element (now at the end)");

            push_heap(ia, ia + 20);
            show(ia, "Adding 20 (at the end) to the heap again");

            sort_heap(ia, ia + 20);
            show(ia, "Sorting the elements in the heap");

            make_heap(ia, ia + 20, greater<int>());
            show(ia, "The values 1-20 in a heap, using > (and beyond too)");

            pop_heap(ia, ia + 20, greater<int>());
            show(ia, "Removing the first element (now at the end)");

            push_heap(ia, ia + 20, greater<int>());
            show(ia, "Re-adding the removed element");

            sort_heap(ia, ia + 20, greater<int>());
            show(ia, "Sorting the elements in the heap");
        }
        /*
            Displays:
                The values 1-20 in a max-heap:
                20 19 15 18 11 13 14 17 9 10 2 12 6 3 7 16 8 4 1 5
                Removing the first element (now at the end):
                19 18 15 17 11 13 14 16 9 10 2 12 6 3 7 5 8 4 1 20
                Adding 20 (at the end) to the heap again:
                20 19 15 17 18 13 14 16 9 11 2 12 6 3 7 5 8 4 1 10
                Sorting the elements in the heap:
                1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
                The values 1-20 in a heap, using > (and beyond too):
                1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
                Removing the first element (now at the end):
                2 4 3 8 5 6 7 16 9 10 11 12 13 14 15 20 17 18 19 1
                Re-adding the removed element:
                1 2 3 8 4 6 7 16 9 5 11 12 13 14 15 20 17 18 19 10
                Sorting the elements in the heap:
                20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
        */

- Table of Contents
- Previous Chapter
- Next Chapter