# Chapter 23 - Notes

The `<algorithm>` header provides a set of generic functions that help manipulate or work with the contents of a container.&#x20;

The algorithms reduce boilerplate code by helping you:

* Count, search, find, copy, and remove elements from a container&#x20;
* Set values in a range of elements to the return value of a generator function, or constant&#x20;
* Sort of partition elements in a range&#x20;
* Insert elements at the correct position in a sorted range&#x20;

{% hint style="info" %}
In computer programming, **boilerplate code** or just **boilerplate** are sections of code that are repeated in multiple places with little to no variation.&#x20;

When using languages that are considered verbose (like C++), the programmer must write a lot of code to accomplish only minor functionality. Such code is called boilerplate.
{% endhint %}

The functions in the `<algorithm>` header are generic template functions. The pervasive use of iterators ensure that the functions can be used with any containers.&#x20;

## Classification of STL Algorithms

### Non-Mutating Algorithms&#x20;

Algorithms that do not change the order or contents of a container are known as non-mutating algorithms.

* Counting algorithms
  * `count()` - Find all elements in a range matching a given value
  * `count_if()` - Find all elements in a range matching a supplied predicate&#x20;
* Search algorithms&#x20;
  * `search()` - Search for the first occurrence a subsequence
  * `search_n()` - Searches for the first occurrence of `n` number of elements of a given value, or those that match a supplied predicate.&#x20;
  * `find()` - Searches for the first element in the range that matches a given value&#x20;
  * `find_if()` - Searches for the first element in a range that matches a given predicate&#x20;
  * `find_end()` - Searches for the last occurrence of a particular subsequence&#x20;
  * `find_first_of()` - Searches for the first instance of any element in a subsequence&#x20;
  * `adjacent_find()` - Searches for two subsequent elements in a collection that are either equal, or match a supplied predicate.&#x20;
* Comparison algorithms&#x20;
  * `equal()` - Compares two elements for equality, optionally using a binary predicate&#x20;
  * `mismatch()` - Locates the position of the first difference of two ranges, optionally with a specified binary predicate&#x20;
  * `lexicographical_compare()` - Compares elements between two ranges to determine which is the lesser of the two&#x20;

### Mutating Algorithms&#x20;

Algorithms that change the contents or order of the container are known as mutating algorithms.&#x20;

* Initialisation algorithms&#x20;
  * `fill()` - Assigns a given value to every element in a given range&#x20;
  * `fill_n()` - Assigns a given value to the first `n` elements of a given range&#x20;
  * `generate()` - Assigns the return value of a given function object to each element in a given range&#x20;
  * `generate_n()` - Assigns the return value of a given function object to the first `n` values in a given range
* Modifying algorithms&#x20;
  * `for_each()` - Performs an operation on each element for a given range, optionally mutating each element
  * `transform()` - Apply a given unary function on every element in the range, stores the results in a destination range&#x20;
* Copy algorithms&#x20;
  * `copy()` - Copies the contents of one range into another destination range
  * `copy_backward()` - Copies the contents of one range into another, reversing the elements in the destination range&#x20;
* Removal algorithms&#x20;
  * `remove()` - Removes all element of a given value from the given range&#x20;
  * `remove_if()` - Removes all elements matching a given unary predicate from a given range&#x20;
  * `remove_copy()` - Copies all elements from a given range to a destination range, except those matching a given value&#x20;
  * `remove_copy_if()` - Copies all elements from a given range to a destination range, except those matching a given unary predicate
  * `unique()` - Compares adjacent elements in a range, and removes subsequent duplicates; comparison can be done with an optionally provided binary predicate.&#x20;
  * `unique_copy()` - Copies all elements from a given range to a destination range, except adjacently duplicated elements
* Replacement algorithms&#x20;
  * `replace()` - Replaces every element in a given range matching a given value with a given replacement value&#x20;
  * `replace_if()` - Replaces every element in a given range matching a given unary predicate with a given replacement value&#x20;
* Sort algorithms&#x20;
  * `sort()` - Sorts the elements in a range using a specified binary sort predicate; this may change the relative positions of elements that are equal.&#x20;
  * `stable_sort()` - Stable sort is similar to sort, but preserves the order of elements that are equal
  * `partial_sort()` - Sorts a specified number of elements in a range
  * `partial_sort_copy()` - Copies a number of elements from a specified source range to a destination range, with the destination range in a sorted order&#x20;
* Partitioning Algorithms&#x20;
  * `partition()` - Given a specified range, split the elements into two sets within it: those that satisfy the given unary predicate, and those that don't. This might not maintain the relative order of elements.&#x20;
  * `stable_partition()` - Partitions an input range into two sets just like `partition`, but maintains the relative ordering of elements
* Algorithms for sorted containers&#x20;
  * `binary_search()` - Used to determine whether an element exists in a sorted collection&#x20;
  * `lower_bound()` - Returns an iterator pointing to the first element in the range that is not less than a given value
  * `upper_bound()` - Returns an iterator pointing to the first element in the range that is greater than a given value&#x20;

## Finding Elements&#x20;

The `find()` and `find_if()` algorithms help you find an element matching a particular value or condition.&#x20;

Both functions return an iterator, which you need to compare against `.end()` or `.cend()` to verify the success of the find operation. Only if successful can you continue to use the iterator returned.&#x20;

## Counting Elements&#x20;

The `count()` and `count_if()` algorithms help you count for elements matching a particular value or condition.&#x20;

## Searching&#x20;

**Finding** is to look for one specific element matching a single value or condition. **Searching** is to look for a subsequence of values, or a pattern.&#x20;

`search()` can be used to check the presence of one range within another range.&#x20;

`search_n()` can be used to check if `n` instances of a particular value can be found consequently found in a container.&#x20;

Both functions return an iterator to the first instance of the pattern found, which needs to be checked against `.end()` or `.cend()` to verify the success of the search operation.&#x20;

## Initialising Elements&#x20;

`fill()` and `fill_n()` are algorithms that can set the contents of a given range to a particular value.&#x20;

`fill()` is used to overwrite all elements in a range with a given value, whereas `fill_n()` overwrites the first `n` elements of a given range.

## Initialising Elements at Runtime&#x20;

Similar to the above, the `generate()` and `generate_n()` algorithms can set the contents of a given range using the values returned by a unary function object.&#x20;

The main benefit in doing so is that the function object can contain state, producing a different value each time, and can also depend on runtime conditions, for example input by the user.

## Processing Elements&#x20;

The `for_each()` algorithm applies a given unary function object to each element in a given range.&#x20;

The algorithm returns the function object that was used to process every element in the supplied range, which can be useful to retrieve state information after the invocation to `for_each()` is done.&#x20;

## Performing Transformations&#x20;

The `for_each()` and `transform()` algorithms are similar in that they both invoke a function object for each element in a given range.

Though the `transform()` algorithm has two versions:

* The first accepts a range, and a unary function, and can store the results of applying the unary function for each element into a destination range&#x20;
* The second accepts two ranges, and a binary function, and can store the results of applying the binary function for each pairwise element of the two ranges into a destination range&#x20;

The first is commonly referred to as **mapping** (not to be confused with `std::map`), while the latter is commonly referred to as **zipping**.

## Copying Elements

The three main copy functions are:

* `copy()`, which copies the contents of one range into another, in the same order in the original range&#x20;
* `copy_if()`, which copies elements from the original range that match a particular predicate into a destination range&#x20;
* `copy_backward()`, which copies the contents of one range into another, in the reverse order of the original range&#x20;

## Removing Elements&#x20;

The `remove()` and `remove_if()` functions removes all elements in a container matching a given value or predicate.&#x20;

The functions return an iterator to the "new end" of the container, which we must use with the `.erase` member function of the container to resize the container accordingly.&#x20;

The reason this is not automatically done for us is that the algorithms operate simply on a range of elements specified by two iterators, meaning that they have no knowledge of the underlying container or collection.&#x20;

As a result, these functions do not actually "remove" the elements from the range - but rather they "move" all elements that are not subject to removal to the front of the range, keeping the relative order of elements.&#x20;

This action of calling `remove()` then `.erase()` immediately after is known as the [erase-remove idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom).

## Replacing Elements&#x20;

The `replace()` and `replace_if()` are functions that can replace elements in a collection matching a given value or predicate.&#x20;

`replace_if()` expects a unary predicate that returns `true` for every element that needs to be replaced.&#x20;

## Algorithms for Sorted Collections

### Sorting&#x20;

The `sort()` algorithm can be used to sort a container.

By default `sort()` uses `std::less<>` as a binary predicate, which uses `operator<` to compare between two subsequent elements. You can also supply your own predicate to control the sort order.

### Removing Duplicates&#x20;

Subsequent duplicates can be removed from a sorted array using the `unique()` algorithm.

When this is invoked on a sorted array, this guarantees that the remaining elements are strictly unique since all duplicate elements would be neighbouring elements. &#x20;

Similar to the `remove()` and `remove_if()` functions - you will need to resize the array with the `.erase()` member function after calling `unique()`. Think of the `unique()` algorithm as a fancy implementation of `remove_if()`.

### Searching&#x20;

To search within a sorted array very quickly, you can use the `binary_search()` algorithm. This algorithm should only be called for containers already sorted.&#x20;

This performs in logarithmic time, as opposed to linear time for a linear search.&#x20;

## Partitioning Elements&#x20;

The `partition()` algorithm helps partition elements by rearranging them into two subranges: one that satisfies the given unary predicate, and another that does not.&#x20;

The relative order of elements in each partition may not be preserved with `partition()`, for that behaviour you should use `stable_partition()` which does preserve the relative order of elements at a the price of performance (albeit small in most cases).&#x20;

The function returns an iterator to the first element in the second group.&#x20;

## Inserting Elements in a Sorted Collection&#x20;

Given an already-sorted collection, and an value that you wish to insert into the collection whilst maintaining the sorted order of the collection, you can use the `lower_bound()` and `upper_bound()` functions to help you determine the correct position to insert the new element.&#x20;

The functions return iterators pointing to the minimal and maximal positions in a sorted range where an element can be inserted:

* `lower_bound()` - Returns an iterator pointing to the first element in the range that is not less than a given value

  `upper_bound()` - Returns an iterator pointing to the first element in the range that is greater than a given value&#x20;
