Professional C__ - Marc Gregoire [186]
fill() Sets all elements in the sequence to a new value.
fill_n() Sets the first n elements in the sequence to a new value.
generate() Calls a specified function to generate a new value and sets all elements in the sequence to the result of that function.
generate_n() Calls a specified function to generate a new value and sets the first n elements in the sequence to the result of that function.
remove(), remove_if() Removes elements that match a given value or that cause a predicate to return true.
remove_copy(), remove_copy_if() Removes elements that match a given value or that cause a predicate to return true, by copying results to a different sequence.
unique(), unique_copy() Removes consecutive duplicates from the sequence, either in place or by copying results to a different sequence.
reverse(), reverse_copy() Reverses the order of the elements in the sequence, either in place or by copying the results to a different sequence.
rotate(), rotate_copy() Swaps the first and second “halves” of the sequence, either in place or by copying the results to a different sequence. The two subsequences to be swapped need not be equal in size.
next_permutation(), prev_permutation() Modifies the sequence by transforming it into its “next” or “previous” permutation. Successive calls to one or the other will permute the sequence into all possible permutations of its elements. Returns false if no more permutations exist.
Sorting Algorithms
Sorting algorithms are a special category of modifying algorithms that sort the elements of a sequence. The STL provides several different sorting algorithms with varying performance guarantees.
ALGORITHM NAME ALGORITHM SYNOPSIS COMPLEXITY
sort(), stable_sort() Sorts elements in place, either preserving the order of duplicate elements or not. Linear Logarithmic
partial_sort(), partial_sort_copy() Partially sorts the sequence: The first n elements (specified by iterators) are sorted; the rest are not. They are sorted either in place or by copying them to a new sequence. Linear Logarithmic
nth_element() Relocates the nth element of the sequence such that the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Linear
merge() Merges two sorted sequences by copying them to a new sequence. Linear
inplace_merge() Merges two sorted sequences in place. Linear Logarithmic
make_heap(), is_heap(), is_heap_until() A heap is a standard data structure in which the elements of an array or sequence are ordered in a semi-sorted fashion so that finding the “top” element is quick. Six algorithms allow you to use heap-sort on sequences. is_heap() and is_heap_until() are new since C++11. Linear
push_heap(), pop_heap() See previous row. Logarithmic
sort_heap() See previous row. Linear Logarithmic
partition() Sorts the sequence such that all elements for which a predicate returns true are before all elements for which it returns false, without preserving the original order of the elements within each partition. Linear
stable_partition() Sorts the sequence such that all elements for which a predicate returns true are before all elements for which it returns false, while preserving the original order of the elements within each partition. Linear Logarithmic
random_shuffle() “Unsorts” the sequence by randomly reordering the elements. In C++11, it is possible to specify the properties of the random number generator used for this. Linear
is_sorted(), is_sorted_until() Checks if a sequence is sorted or which subsequence is sorted. Linear
Set Algorithms
Set algorithms are special modifying algorithms that perform set operations on sequences. They are most appropriate on sequences from set containers, but work on sorted sequences from most containers. All of them have a linear worst case complexity.
ALGORITHM NAME ALGORITHM SYNOPSIS
includes() Determines if every element from one sequence is in another sequence.
set_union(), set_intersection(), set_difference(), set_symmetric_difference() Performs the specified set