Overview
The standard library template based algorithms to process containers using iterators for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements.
Details
Asymptotic Notation is used to describe the represent time complexity of an algorithm where it represents time taken to execute the algorithm for a given input, n.
There are three different notations:
- Big O is used for the worst case running time.
- Big Theta (Θ) is used when the running time is the same for all cases.
- Big Omega (Ω) is used for the best case running time.
Out of the three, Big O notation is widely used. Besides Big O notation is also used to represent space complexity where it represents memory consumption.
Binary search algorithms operate on various types of containers such as sequence, associative and unordered that are sorted to perform actions such as finding upper, lower, equal bounds for a value or its existence.
The following are list of APIs
| lower_bound | upper_bound | equal_range | binary_search |
Heap Algorithms operate on various types of containers such as sequence, associative and unordered to organize the elements of a range that allows for fast retrieval of the element with the highest
value at any moment (with pop_heap), even repeatedly, while allowing for fast insertion of new elements (with push_heap).
The following are list of APIs
| is_heap | pop_heap | is_heap_until | push_heap | is_heap_until | push_heap |
Lexicographical algorithms operate on various types of containers such as sequence, associative and unordered to perform lexicographical actions such as comparing elements, generate sequences etc.
The following are list of APIs
| lexicographical_compare | next_permutation | prev_permutation |
Merge algorithms operate on various types of containers such as sequence, associative and unordered to perform actions such as merging sorted sequences, set union, intersection and differences.
The following are list of APIs
| merge | inplace_merge | includes | set_union | set_intersection | set_difference | set_symmetric_difference |
Min/Max Algorithms are template based functions that operate on various types of containers such as sequence, associative and unordered to perform actions such as finding the smallest and the largest element.
The following are list of APIs
| min | max | minmax | min_element | max_element |
Modifying Algorithms operate transparently on containers such as lists, vectors, maps, sets, arrays etc. using a pair of iterators, These are collectively known as sequences. They perform actions such as replace, remove, copy etc.
The following are list of APIs
| copy | copy_n | copy_if | copy_backward | move | move_backward | swap |
| swap_ranges | iter_swap | transform | replace | replace_if | replace_copy | fill |
| fill_n | generate | generate_n | remove | remove_if | remove_copy | remove_copy_if |
| unique | unique_copy | reverse | reverse_copy | rotate | rotate_copy | random_shuffle |
| shuffle |
Non Modifying Algorithms operate transparently on containers such as lists, vectors, maps, sets, arrays etc. using a pair of iterators, These are collectively known as sequences. They perform actions such as search, find, count etc.
The following are list of APIs
| all_of | any_of | none_of | for_each | find | find_if | find_end |
| find_first_of | adjacent_find | count | count_if | mismatch | equal | is_permutation |
| equal | search | search_n |
Numerical algorithms operate on various types of containers such as sequence, associative and unordered to perform operations on the elements of a range to return a value or a sequence.
The following are list of APIs
| accumulate | partial_sum | inner_product | iota | adjacent_difference |
Partitions are commonly used for searching and sorting. Partitioning algorithms operate on various types of containers such as sequence, associative and unordered to perform actions such as partition, sort and more.
The following are list of APIs
| partition | stable_partition | partition_copy | partition_point | is_partitioned | is_partitioned |
Sorting Algorithms operate on various types of containers such as sequence, associative and unordered to perform actions such as sorting.
The following are list of APIs
| sort | stable_sort | partial_sort | partial_sort_copy | is_sorted | is_sorted_until | nth_element |
These algorithms can be used to in place construct objects in uninitialized memory and copy ranges or fill.
The following are list of APIs
| uninitialized_copy | uninitialized_copy_n | uninitialized_fill | uninitialized_fill_n |
No comments:
Post a Comment