Chapter 23 - Notes

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

The algorithms reduce boilerplate code by helping you:

• Count, search, find, copy, and remove elements from a container

• Set values in a range of elements to the return value of a generator function, or constant

• Sort of partition elements in a range

• Insert elements at the correct position in a sorted range

In computer programming, boilerplate code or just boilerplate are sections of code that are repeated in multiple places with little to no variation.

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.

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.

Classification of STL Algorithms

Non-Mutating Algorithms

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

• Search algorithms

  • 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.

  • find() - Searches for the first element in the range that matches a given value

  • find_if() - Searches for the first element in a range that matches a given predicate

  • find_end() - Searches for the last occurrence of a particular subsequence

  • find_first_of() - Searches for the first instance of any element in a subsequence

  • adjacent_find() - Searches for two subsequent elements in a collection that are either equal, or match a supplied predicate.

• Comparison algorithms

  • equal() - Compares two elements for equality, optionally using a binary predicate

  • mismatch() - Locates the position of the first difference of two ranges, optionally with a specified binary predicate

  • lexicographical_compare() - Compares elements between two ranges to determine which is the lesser of the two

Mutating Algorithms

Algorithms that change the contents or order of the container are known as mutating algorithms.

• Initialisation algorithms

  • fill() - Assigns a given value to every element in a given range

  • fill_n() - Assigns a given value to the first n elements of a given range

  • generate() - Assigns the return value of a given function object to each element in a given range

  • generate_n() - Assigns the return value of a given function object to the first n values in a given range

• Modifying algorithms

  • 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

• Copy algorithms

  • 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

• Removal algorithms

  • remove() - Removes all element of a given value from the given range

  • remove_if() - Removes all elements matching a given unary predicate from a given range

  • remove_copy() - Copies all elements from a given range to a destination range, except those matching a given value

  • 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.

  • unique_copy() - Copies all elements from a given range to a destination range, except adjacently duplicated elements

• Replacement algorithms

  • replace() - Replaces every element in a given range matching a given value with a given replacement value

  • replace_if() - Replaces every element in a given range matching a given unary predicate with a given replacement value

• Sort algorithms

  • sort() - Sorts the elements in a range using a specified binary sort predicate; this may change the relative positions of elements that are equal.

  • 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

• Partitioning Algorithms

  • 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.

  • stable_partition() - Partitions an input range into two sets just like partition, but maintains the relative ordering of elements

• Algorithms for sorted containers

  • binary_search() - Used to determine whether an element exists in a sorted collection

  • 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

Finding Elements

The find() and find_if() algorithms help you find an element matching a particular value or condition.

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.

Counting Elements

The count() and count_if() algorithms help you count for elements matching a particular value or condition.

Searching

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.

search() can be used to check the presence of one range within another range.

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

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.

Initialising Elements

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

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

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.

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

The for_each() algorithm applies a given unary function object to each element in a given range.

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.

Performing Transformations

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

• 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

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

• copy_if(), which copies elements from the original range that match a particular predicate into a destination range

• copy_backward(), which copies the contents of one range into another, in the reverse order of the original range

Removing Elements

The remove() and remove_if() functions removes all elements in a container matching a given value or predicate.

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.

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.

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.

This action of calling remove() then .erase() immediately after is known as the erase-remove idiom.

Replacing Elements

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

replace_if() expects a unary predicate that returns true for every element that needs to be replaced.

Algorithms for Sorted Collections

Sorting

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

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.

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

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.

This performs in logarithmic time, as opposed to linear time for a linear search.

Partitioning Elements

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

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).

The function returns an iterator to the first element in the second group.

Inserting Elements in a Sorted Collection

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.

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