Algorithms in C++
1. std::accumulate
Used to add all the values in the container and return the result. Found in the header file numeric. More implementation details in accumulate_demo.cpp. WARNING: init value should be of the same type as others. For example when using a container with type float or double, the init type should be 0f or 0.0 and not just 0.
Usage:
-
std::accumulate(v.begin(), v.end(), init), needs an overload ofoperator+for custom objects. -
std::accumulate(v.begin(), v.end(), init, custom_obj) -
std::accumulate(v.begin(), v.end(), init, custom_function), in custom_function can be a static function(signature int sum(int, type))that belongs to a class that is contained in v.
More info here
2. std::count
Used to find the number of time a value is occuring in the container. Present in the algorithm header.
Usage:
std::count(begin(v1), end(v1), val)
More info here.
3. std::count_if
Used to find the number of time a value is occuring in the container. Present in the algorithm header. For user defined data types, the operator == must be overloaded for the function to work as intended. The predicate condition can also be a lambda.
Usage:
std::count(begin(v1), end(v1), predicate)
More info here.
4. std::find
Returns an iterator to the first occurence in the range provided. If no matching element is found, the iterator to the last element is returned. Present in the algorithm header.
Usage:
std::find(begin(v1), end(v1), val)
More info here.
5. std::find_if
Returns an iterator to the first occurance in the range provided. If no matching element is found, the iterator to the last element is returned.
Present in the algorithm header. This function needs a predicate condition to evaluate.
Usage:
std::find_if(begin(v1), end(v1), predicate)
More info here.
6. std::for_each
Applied the function fn for all the elements present within the range given by the iterators. Present in the algorithm header.
Usage:
std::for_each(begin(v1), end(v1), fn)
More info here.
7. sort
Sort the content given in the range. If a comparison function is given, it is used while sorting. Present in the algorithm header. greater<type> and other comparison functors can be used as well. The elements are compared with the overloaded operator< when no compare function is provided. Performs O(N·log(N)) comparisons. This algorithm is unstable sort, in which when there are two equal elements, their positions would (but not guaranteed) be swapped or changed.
Usage:
-
std::sort(begin(v1), end(v1)) -
std::sort(begin(v1), end(v1), compare) -
std::sort(begin(v1), end(v1), class_name), in this case theclass_nameneeds an overload ofbool operator()(type& arg1, type& arg2)function.
Extras:
Most implementations of std::sort use quicksort, (or usually a hybrid algorithm like introsort, which combines quicksort, heapsort and insertion sort).
The only thing the standard requires is that std::sort somehow sort the data according to the specified ordering with a complexity of approximately O(N log(N)); it is not guaranteed to be stable. Technically, introsort better meets the complexity requirement than quicksort, because quicksort has quadratic worst-case time.
More info here.
8. std::stable_sort
Applies the function fn for all the elements present within the range given by the iterators. Present in the algorithm header. As the name suggests, the order of equal elements is preserved.
Usage:
-
std::stable_sort(begin(v1), end(v1)) -
std::stable_sort(begin(v1), end(v1), fn)
The order of equal elements is guaranteed to be preserved. Complexity: O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)).
More info here.
9. std::partial_sort
Sort the content given in the range from begin to end but making sure all the elements till middle are sorted. If a comparison function is given, it is used while sorting. Present in the algorithm header. greater<type> and other comparison functors can be used as well. The elements are compared with the overloaded operator< when no compare function is provided.
Usage:
-
std::partial_sort(begin, middle, end) -
std::partial_sort(begin, middle, end, func)
“On average, less than linearithmic in the distance between first and last: Performs approximately N*log(M) comparisons of elements (where N is this distance, and M is the distance between first and middle). It also performs up to that many element swaps (or moves).”
More info here.
10. std::partial_sort_copy
Sort the content given in the range from begin to end and copies the sorted elements into a new container. If a comparison function is given, it is used while sorting. Present in the algorithm header. greater<type> and other comparison functors can be used as well. The elements are compared with the overloaded operator< when no compare function is provided.
Usage:
-
std::partial_sort_copy(begin, middle, end) -
std::partial_sort_copy(begin, middle, end, func)
“On average, less than linearithmic in the distance between first and last: Performs approximately N*log(min(N,M)) comparisons of elements (where N is this distance, and M is the distance between result_first and result_last). It also performs up to that many element swaps (or moves) and min(N,M) assignments between ranges.”
More info here.
11. std::min_element
Returns a iterator to the first occurring smallest element in the container within the range provided. Present in the algorithm header.
Usage:
-
std::min_element(begin(v1), end(v1)) -
std::min_element(begin(v1), end(v1), comp)
Has linear complexity for searching and finding the least element.
More info here.
12. std::max_element
Returns a iterator to the first occurring largest element in the container within the range provided. Present in the algorithm header.
Usage:
-
std::max_element(begin(v1), end(v1)) -
std::max_element(begin(v1), end(v1), comp)
Has linear complexity for searching and finding the least element.
More info here.
13. std::search
This function returns the iterator to the element whose value is found in the target search list, not just the value but also the entire subsequence has to be present. Present in the algorithm header.
Usage:
-
std::search(begin(v1), end(v1), begin(v2), end(v2)) -
std::search(begin(v1), end(v1), begin(v2), end(v2), comp)
Linear complexity for searching.
More info here.
14. std::search_n
This function returns the iterator to the element whose val is found along with it’s val_count of consecutive occurances. Present in the algorithm header.
Usage:
-
std::search_n(begin(v1), end(v1), val_count, val) -
std::search_n(begin(v1), end(v1), val_count, comp)
Linear complexity for searching.
More info here.
15. binary_search
This function returns the boolean value as the result for which whose value is equal to the value specified. Present in the algorithm header. This algorithms expects the input to be sorted to work as desired.
Usage:
-
bool std::binary_search(begin(v1), end(v1), val) -
bool std::binary_search(begin(v1), end(v1), val, comp)
Performs approximately log2(N)+2 element comparisons (where N is this distance).
More info here.
16. std::copy
Performs an element wise copy from source to the destination. Returns the end of the destination where the elements have been copied. Present in the algorithm header.
Usage:
-
std::copy(begin(v1), end(v1), begin(v2)) -
std::copy(begin(v1), end(v1), back_inserter(v2))
Linear time complexity.
More info here.
17. copy_if
Performs an element wise copy from source to the destination which matches the predicate condition. Returns the end of the destination where the elements have been copied. Present in the algorithm header. Should perf be a concern, consider instead of using std::back_inserter to populate the destination with the same size as the source.
Usage:
-
std::copy_if(begin(v1), end(v1), begin(v2), pred) -
std::copy_if(begin(v1), end(v1), back_inserter(v2), pred)
Linear time complexity.
More info here.
18. std::nth_element
Rearranges elements such that nth element specified is in the right place (as it would have been in a sorted sequence). Present in the algorithm header. To compare custom objects, the class should overload operator< and operator>.
Usage:
-
std::nth_element(begin(v1), begin(v1)+n, end(v1)) -
std::nth_element(begin(v1), begin(v1)+n, end(v1), pred)
Hint: for pred use: less<T>() for sorting in ascending order and greater<T>() for sorting in descending order.
Linear (in length) time complexity, on average.
More info here.
19. std::reverse
Reverses the elements present in the container pointed by the range. Present in the algorithm header. Uses iter_swap on the elements that are being iterated.
Usage:
std::reverse(begin(v1), end(v1))
Linear (in half the length) complexity.
More info here.
20. std::reverse_copy
Reverses the elements present in the container pointed by the range. Present in the algorithm header.
Usage:
std::reverse_copy(begin(v1), end(v1), begin(dest_v))
Linear complexity.
More info here.
21. std::set_difference
Gives the set difference between two sets. In this case, the order of the containers matter. Present in the header algorithm. In order for the function to work as intended, the container should be sorted before being passed to the function.
Usage:
-
std::set_difference(begin(v1), end(v1), begin(v2), end(v2), begin(v3)) -
std::set_difference(begin(v1), end(v1), begin(v2), end(v2), back_inserter(v3))// for an empty array
Linear complexity.
More info here.
22. std::set_symmetric_difference
Gives the set difference between two sets regardless of the ordering. In other words the element present in one container but missing in the other are obtained. Present in the header algorithm. In order for the function to work as intended, the container should be sorted before being passed to the function.
Usage:
-
std::set_symmetric_difference(begin(v1), end(v1), begin(v2), end(v2), begin(v3)) -
std::set_symmetric_difference(begin(v1), end(v1), begin(v2), end(v2), back_inserter(v3))// for an empty array
Linear complexity.
More info here.
23. std::transform
Present in the algorithm header. This function can take either one or two containers and perform unary or binary operation and copy the results into another container. To elaborate it, transform can do one of the two functions:
Take a container, pass each of the element to the function given, collect the output into another container.
Take two containers, pass each of the element as a pair to the binary function given and collect the output into another container.
Usage:
-
std::transform(begin(v1), end(v1), begin(res_v), unary_op) -
std::transform(begin(v1), end(v1), begin(v2), begin(res_v), binary_op)
Linear complexity.
More info here.
24. std::iota
Present in the numeric header. This function store increasing sequence of numbers (of init, with delta as 1) in a container.
Usage:
std::iota(begin(v1), begin(v1) + 3, 100)v1 will contain {100, 101, 102}
Linear complexity.
More info here
25. std::reduce
26. std::adjacent_difference
Present in the numeric header. Assigns to every element a difference between two consecutive values. This operation leaves the first value unchanged.
Usage:
-
std::adjacent_difference(begin(v1), end(v1), begin(v_result)) -
std::adjacent_difference(begin(v1), end(v1), begin(v_result), binary_op)
Linear complexity.
More info here
27. std::inner_product
Present in the numeric header. Takes two containers and performs op1 on each of the pair and performs op2 on all the elements in the resulting container. By default, these operations are op1 = addition (reduce operation) and op2 = multiplication.
Usage:
-
std::inner_product(begin(v1), end(v1), begin(v2), init) -
std::inner_product(begin(v1), end(v1), begin(v2), init, op1, op2)
Linear complexity.
More info here
24. std::merge
25. std::set_union
26. std::set_intersection
28. std::generate
Present in the algorithm header. Calls gen for filling every element in the container.
Usage:
std::generate(begin(v1), end(v1), gen)
Linear complexity.
More info here