I was watching a talk by Jonathan Bocarra on “105 STL algorithms in less than an hour” and it was a very good and an informative talk. I kept notes of the talk as I was watching and though it would be useful to look back at later:

Why should you use STL algorithms?

• Your code gets more expressive, can substantially reduce the number of lines of code. I can tell this by experience as well, where I could refactor ~30 lines of code into 2-3 lines by correctly using STL algorithms.
• Avoiding having to write raw-loops, conditional checks.
• Part of C++ standard, behavior uniform across different compilers.

Heaps:
In C++, heaps are implemented as a max heap where the parent is bigger than the children.
The first algorithm mentioned in the talk is make_heap, wherein you can take a structured set of data, a convert into heap using make_heap. When you push a new element into the vector, this needs to be reordered to match the properties of the heap. This can be done by pushing the element into the heap using push_back and then using push_heap. push_heap reorders the vector according the properties of the heap. To remove the first element from the heap, you can use pop_heap. However, the value still remains in the heap, to remove it from the heap permanently, you can use pop_back.

Sorting:
As everyone would be familiar, the most common way to sort a list would be to use sort.
partial_sort can also be used to partially sort a list from the beginning to a certain index in the list and the rest of the list is left to an uncertain order. nth_element can be used to sort an individual element into a position it would belong provided that the list was sorted. The elements before the nth position would be lesser than and above the nth position would be greater than the element. However, these indices remain in an unspecified order among themselves. sort_heap sorts a heap, this can also be acheived by continuosly calling pop_heap. inplace_merge is the incremental step in a merge sort, i.e when you have a list which is sorted into two halves. inplace_merge can be used to convert the lists into a single sorted list.

Partitioning:
Partitioning of a collection can be used to partition a collection into two parts using a specific condition. partition can be used to partition a collection and partition_point can be used to get the position at which the partitioning of the collection starts.

Permutations:
Rotation basically rotates the the list, i.e the last element is moved to the first. shuffle can be used to shuffle the elements randomly. next_permutation and prev_permutation can be used to obtain the next permutation of the list and the previous permutation. reverse can be used to reverse a list.

Miscellaneous:
These can be used to combine with other algorithms to get new algorithms.
With stable_* algorithms, the lists keep the same relative order when you partition or sort a list. In some cases, the order of the list will not be present when you partition or sort a list. The relative order is kept when you use stable_sort or stable_partition. is_* can be used to check whether a certain structure follows a certain condition. For instance, is_sorted returns a boolean to check whether the given list is sorted or not. is_*_until can be used to check whether a list follows a certain condition until a certain position in the container. It returns an iterator to the position where the condition
does not start to hold. For example, is_sorted_until will return an iterator the end for a sorted collection.

Numeric algorithms:
count takes a beginning and an end an returns a value of how many times the element occurs in the list. accumulate/transform_reduce can be used to return a sum or any other custom function on the list. partial_sum sums all the element till the current point in the collection. inclusive_scan is same as the partial sum, but this one can be run in parallel. exclusive_scan does not include the current element whereas inclusive_scan can includes the current element. inner_product is similar to a dot product(multiply individual elements, followed by a sum on the result). adjacent_difference returns the difference between two neighboring position. sample returns a random sampling of the collection.

Querying:
all_of takes a condition and returns if all of the elements follow the condition. any_of, by the name returns if any of the elements follow the condition. none_of returns if none of the elements follow the condition.

Querying on two ranges:
equal returns true if all elements on the lists are individually equal and the size is the same. is_permutation returns true if one of the list is the permutation of the other. lexicographical_compare returns a boolean if the lists are lexicographically are smaller than each other. mismatch can be used to traverse over lists and return the position where the lists start to differ.

Searching a value:
For an unsorted list:
find returns an iterator to the value you are searching for in the list. If it’s not found, it returns an itertor to the end. adjacent_find returns the first position where the adjacent values are equal.

For a sorted list:
In a sorted list, equal_range returns a subrange where the values are equal. lower_bound returns indicates lower bound position in which the value is present and the upper_bound returns the upper bound index of the position in which the value is equal. Note that when there is only one element equal to the value, then the upper_bound and lower_bound are equal. binary_search return true if the values is present in the list or not.

Searching a range:
Searches a subrange of values within a bigger range. find_end searches for a subrange starting from the end. find_first_of can be used to search for any occurence of the smaller subrange in the bigger range.

Searching for a relative value:
Searching for a relative value can be done using max_element, min_element, minmax_element.

Algorithms on sets:
set_difference can be used to find the element in one set not present in the other. One thing to note is that this takes linear complexity \(O(n)\) due to the fact that set is sorted. set_intersection returns the elements common to both the sets. set_union returns elements that are in one set or another. set_symmetric_difference returns elements that are unique to both the sets. includes returns a boolean if all the elements on one set are included on the other. merge merges both the sets into one sorted set.

Moving algorithms:
copy is the simplest one that copies elements from one container to anoter.
move moves elements from one container to another.
swap_ranges swaps the elements in a given range to another range. copy_backward copies elements in the backward order, this can be used to prevent data from being lost when copying data within the container. Similarly, there is move_backwards which does a move instead of copy.

Value modifiers:
fill can be used to fill the same values inside the container. generate can be used to fill a structure using a generating function. iota can be used to put a value in the begining and that value is incremented as the rest of the structure is filled. replace can be used to replace the values in a collection.

Structure changers:
remove can be used to remove the values. However, note that the size of the container remains the same. The indices that are removed will be replaced with values in order that they were present. The values of rest of the indices that would go unfilled can be anything. erase needs to be called after remove to clear the rest of the container of the removed values. unique removes the adjacent duplicates in a correction. similary, erase has to be called to update the container and it’s size. *_copy can be used to copy elements from one container to another, leavig the original container intact.

Similarly, *_if, can be used to find/replace/copy elements that follow a certain condition.

Others algorithms that don’t fit in any “islands”:
transform can be used to transform a collection by means of a function or an operator on the element. for_each traverses through the container and calls a function on each element of the container. for_each can be used to produce “side effects” as a result of the operation on the container.

Raw memory:
fill, copy and move uses assignment operators, which means that the object should be constructed. Raw memory operators is for operating on chunks of memory. uninitialized_fill,
uninitialized_copy, uninitialized_move can be used with constructors on chunks of memory. destroy can be used to destroy the elements in a container once you are done with your operations. uninitialized_default_construct and uninitialized_value_construct can be used for calling value or default constructors.

*_N algorithms:
Instead of iterating over the entire structure, these *_n algorithms, can be used to iterate over the given position and size after the given element.

I made a single page cheat sheet for myself with the STL algorithms(shown below), since the map of islands is a bit too big for my eyes. You can find the pdf version here. The \(LaTeX\) source can be found on Github.