100+ STL Algorithms, "I Bet If You Know Even 20 Out of These..." ( C++ 17 )

So,
In the previous posts, I've been telling you about the various containers in STL and their implementation.
I left a few of them purposely such as unordered_map, unordred_set, etc. so that you also do some homework.
This post will entirely be about various functions available in STL and it would be your task to completely code & implement them.
Do tell me if you have any doubts related to it in the comment section below.

Some common Data Structures Implementation In STL :

Stack
Syntax : stack<data_type> stack_name
Example  : stack<int> st;
Built-in functions such as top(), push(), pop(), empty(), size() etc. are available in STL for Stack.

Queue
Syntax : queue<data_type> queue_name
Example  : queue<int> q;
Built-in functions such as push(), pop(), empty(), size(),front(), back() are available in STL for Queue.

List ( Doubly Linked List )
Syntax : list<data_type> list_name
Example  : list<int> l;

Built-in functions such as push_front(),push_back(), pop_front(),pop_back(), begin(), end(),erase(), rbegin(),rend() etc. are available in STL for List.

Let us Come To The Main Topic Of This Post i.e. STL Algorithms In C++ 17:-

**Mostly uncommon STL algorithms will be discussed here, about which people are generally not aware but are quite useful.

Advantages of STL :

• It makes algorithms more expressive.
• It raises levels of abstraction.

Algorithms On Heap :

• make_heap(): It is used to transform a sequence into a heap.
• push_heap(): This function is used to insert elements into a heap.
• pop_heap(): This function is used to delete the maximum element of the heap.

Algorithms On Sort

• partial_sort(): It is used for sorting not the entire range, but only a sub-part of it.
• nth_element(): It used to arrange elements such that all the elements, which precede the nth element are not greater than it, and all the elements which succeed it are not less than it.
• sort_heap(): It is an STL algorithm that sorts a heap within the range specified by start and end. Sorts the elements in the heap range [start, end) into ascending order.
• inplace_merge(): This function is used to sort two consecutively placed sorted ranges in a single container. It takes 3 arguments, an iterator to the beginning of 1st sorted range, an iterator to the beginning of 2nd sorted range, and an iterator to the last position.

Algorithms On Partitioning

• partition_point(): Returns an iterator to the first element in the partitioned range [first, last) for which predicate is not true, indicating its partition point. The elements in the range shall already be partitioned as if partition had been called with the same arguments.
• stable_partition( ): This algorithm arranges the sequence defined by start and end such that all elements for which the predicate specified by pfn (User-defined predicate function object that defines the condition to be satisfied if an element is to be classified. A predicate takes a single argument and returns true or false ) returns true come before those for which the predicate returns false. The partitioning is stable. This means that the relative ordering of the sequence is preserved.

Algorithms On Permutation

• reverse(): It reverses the order of the elements in the range [first, last) of any container.
• next_permutation(): It is used to rearrange the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographically to each other.
• prev_permutation(): Similar to next_permutation() but it rearranges the elements according to the last permutation (sorted in descending order) and returns false.

Algorithms On Search

• find(): Finds the element in the given range of numbers. Returns an iterator to the first element in the range [first, last] that compares equal to value. If no such element is found, the function returns last.
• adjacent_find(): Searches the range [first, last) for the first occurrence of two consecutive elements that match, and returns an iterator to the first of these two elements, or last if no such pair is found. Elements are compared using the given binary predicate p or using ==. 
• search(): It is used to find out the presence of a subsequence satisfying a condition (equality if no such predicate is defined) with respect to another sequence.
• search_n(): It is used to search whether a given element satisfies a predicate (equality if no such predicate is defined ) a given no. of times consecutively with the container elements.
• find_if():  Returns an iterator to the first element in the range [first, last] for which pred (Unary Function) returns true. If no such element is found, the function returns last.
• find_if_not(): Returns an iterator to the first element in the range [first, last] for which pred(Unary Function) returns false. If no such element is found, the function returns last.
• find_end(): Used to find the last occurrence of a sub-sequence inside a container. It searches the range [first1,last1) for the last occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found.

Algorithms on Sets (Not just the set container but the one used in Mathematics as a Set) :

• set_difference(): The difference between two sets is formed by the elements that are present in the first set, but not in the second one. The elements copied by the function come always from the first range, in the same order.
• set_union(): The union of two sets is formed by the elements that are present in either one of the sets, or in both. Elements from the second range that have an equivalent element in the first range are not copied to the resulting range.
• set_symmetric_difference(): The symmetric difference of two sets is formed by the elements that are present in one of the sets, but not in the other. Among the equivalent elements in each range, those discarded are those that appear before in the existent order before the call. The existing order is also preserved for the copied elements.
• includes(): This function is used to check whether one sorted container elements are including other sorted container elements or not. Returns true if 1st container includes 2nd container else returns false.
• merge(): This function merges two sorted containers and stores in new containers in sorted order (merge sort). It takes 5 arguments, first and last iterator of 1st container, first and last iterator of 2nd container and 1st iterator of the resultant container; merge(beg1, end1, beg2, end2, beg3)

Algorithms on Moves

• copy(): The generic copy function used to copy a range of elements from one container to another.
• copy_n(): This version of copy gives the freedom to choose how many elements have to be copied in the destination containers.
• move(): Moves the elements in the range [first, last] into the range beginning at the result. The value of the elements in the [first, last] is transferred to the elements pointed by the result. After the call, the elements in the range [first, last] are left in an unspecified but valid state.
• swap_ranges(): It is used for swapping the elements within a range.
• copy_backwward(): This function starts copying elements into the destination container from backward and keeps on copying till all numbers are not copied.
• move_backward(): Moves the elements in the range [first, last] starting from the end into the range terminating at the result. The function begins by moving *(last-1) into *(result-1), and then follows backward by the elements preceding these, until first is reached (and including it).
• copy_if():  this function copies according to the result of a “condition“.This is provided with the help of an extra argument, a function returning a boolean value.

Algorithms On Sorted Data

• binary_search(): Binary search is a widely used searching algorithm that requires the array to be sorted before a search is applied. The main idea behind this algorithm is to keep dividing the array in half (divide and conquer) until the element is found, or all the elements are exhausted.
• lower_bound(): The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns the index of the next smallest number just greater than that number.
• upper_bound(): The upper_bound() is a standard library function in C++ defined in the header . It returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.
• equal_range(): It is used to find the sub-range within a given range [first, last) that has all the elements equivalent to a given value. It returns the initial and the final bound of such a sub-range.

Algorithms On Value Modifiers

• fill(): The ‘fill’ function assigns the value ‘val’ to all the elements in the range [begin, end), where ‘begin’ is the initial position and ‘end’ is the last position.
• generate():It is used to generate numbers based upon a generator function, and then, it assigns those values to the elements in the container in the range [first, last).
• iota(): Assigns to every element in the range [first, last] successive values of val, as if incremented with ++val after each element is written.
• replace(): It replaces each element in the range [first, last) that is equal to oldValue with newValue. The function uses operator == to compare the individual elements to old_value.
• erase(): Function is used to remove elements from a container from the specified position or range.

Algorithms On Quering Property

• all_of(): This function operates on the whole range of array elements and can save time to run a loop to check each element one by one. It checks for a given property on every element and returns true when each element in range satisfies the specified property, else returns false.
• any_of(): This function checks for a given range if there’s even one element satisfying a given property mentioned in function. Returns true if at least one element satisfies the property else returns false.
• none_of(): This function returns true if none of the elements satisfies the given condition else returns false.
• equal(): It helps to compare the elements within the range [first_1,last_1) with those within range beginning at first_2.
• lexicographical_compare(): C++ STL offers many utilities to solve basic common life problems. Comparing values are always necessary, but sometimes we need to compare the strings also. Therefore, this article aims at explaining about “lexicographical_compare()” that allows comparing strings.
• mismatch(): This function helps to compare 2 containers for mismatches such as inequality or any other user-defined mismatch criteria.

Algorithms On Raw Memory

• unitialized_fill(): Copies the given value to an uninitialized memory area, defined by the range [first, last). If an exception is thrown during the initialization, the objects already constructed are destroyed in an unspecified order.
• unitialized_copy(): Constructs copies of the elements in the range [first, last) into a range beginning at the result and returns an iterator to the last element in the destination range.
  Unlike algorithm copy, uninitialized_copy constructs the objects in-place, instead of just copying them. This allows obtaining fully constructed copies of the elements into a range of uninitialized memory, such as a memory block obtained by a call to get_temporary_buffer or malloc.
• unitialized_move():  Moves elements from the range [first, last) to an uninitialized memory area.
• for_each_n(): It helps apply a common function to all the elements of an array (or any other linear data-type). It essentially batches updates a range of elements starting from a given iterator and for a fixed number of elements from that iterator. 
• destroy_n(): Destroys the objects in the range [first, last).

Algorithms On Loop

• for_each(): This loop function executes over each of the container elements. 
• transform(): The transform() function in C++ sequentially applies an operation to the elements of an array(s) and then stores the result in another output array. It is applied in two forms i.e. on Unary Operators and on Binary Operators.

Algorithms On Queries

• count(): It returns the number of occurrences of an element in a given range. Returns the number of elements in the range [first, last) that compare equal to val.
• inner_product(): Returns the result of accumulating init with the inner products of the pairs formed by the elements of two ranges starting at first1 and first2.
• adjacent_difference(): It computes the adjacent difference of range, Assigns to every element in the range starting at the result the difference between its corresponding element in the range [first, last) and the one preceding it (except for *result, which is assigned *first).
• accumulate(): This function returns the sum of all the values lying in a range between [first, last) with the variable sum.
• partial_sum(): This function assigns partial sum of the corresponding elements of an array to every position of the second array.It returns the partial sum of all the set of values lying between [first, last) and stores it in another array b.
• transform_inclusive_scan(): Its functionality is to transform each and every element between first and last with unary_op then computes an inclusive prefix sum operation by the help of binary_op with a specific range. An inclusive defined the i-th input element is included in the i-th sum operation.
• transform_exclusive_scan(): Transforms each element in the range [first, last) with unary_op, then computes an exclusive prefix sum operation using binary_op over the resulting range, with init as the initial value, and writes the results to the range beginning at d_first. "exclusive" means that the i-th input element is not included in the i-th sum.

Algorithms On Structure Changes & Secret Runes 

*_copy()

• remove_copy(): It copies the elements in the range [first, last) to the range beginning at result, except those elements that compare equal to given elements.
• unique_copy(): Copies the elements in the range [first, last) to the range beginning at result, except consecutive duplicates (elements that compare equal to the element preceding). Only the first element from every consecutive group of equivalent elements in the range [first,last) is copied. The comparison between elements is performed by either applying operator==, or the template parameter pred (for the second version) between them. 
• reverse_copy(): It is a function that copies the elements from the given range but in reverse order. 
• rotate_copy(): It is used to make a rotated copy of the elements in the range [first, last).
• replace_copy(): It copies the elements in the range [first, last) to the range beginning at result, replacing the appearances of old_value by new_value.
• partition_copy(): It is used to copy the elements for which a condition is true to one destination, and false to another. The elements must belong to a specified range. 
• partial_sort_copy(): It is used if we want to keep the original container intact and just copy the sorted sub-part of the container into another one.

*_if()

• find_if(): Returns an iterator to the first element in the range [first, last] for which pred(Unary Function) returns true. If no such element is found, the function returns last.
• count_if(): Count_if() function returns the number of elements in a range that satisfy the condition.
• remove_if(): It is used to eliminate all the elements that satisfy a predicate from a given range [first, last) without disturbing the order of the remaining elements.
• remove_copy_if(): It copies the elements in the range [first, last) to the range beginning at the result, except those elements that meet to a given condition (like an odd number, even number, prime number, non-prime number, etc ).
• replace_if(): It is used to assign new_value to all the elements in the range [first, last) for which pred predicate returns true. This function examines each element in a range and replaces it if it satisfies a specified predicate.
• copy_if(): It copies a range of elements to a new location if the predicate returns true for value.

is_*()

• is_sorted(): It checks if the elements in the range [first, last] are sorted in ascending order. Elements are compared using < operator.
• is_heap(): This function is used to check whether the elements in the range [first, last) form a heap. It returns true if the elements in the specified range form a heap.

is_*_unitl()

• is_sorted_until(): It is used to find out the first unsorted element in the range [first, last). It returns an iterator to the first unsorted element in the range, so all the elements in between first and the iterator returned are sorted.
  It can also be used to count the total no. of sorted elements in the range. It is defined inside the header file. In case, the whole range is sorted, it will return an iterator pointing to last.
• is_heap_until(): It finds the first element from the sequence which violates the max heap condition. 
• is_partitioned_until():The algorithm tests to see if a sequence is partitioned according to a predicate; in other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence.

Boost Algorithms

• sort_subrange(): It rearranges the elements of the collection so that those in a certain subrange are at the positions they would be in if the whole range had been sorted. This algorithm takes 4 iterators: two to indicate the whole range, and two to indicate the subrange inside of the whole range:
• is_palindrome(): The algorithm tests the sequence and returns true if the sequence is a palindrome; i.e, it is identical when traversed either backwards or frontwards.
• boyer_moore(): The naive approach of finding a pattern in a string is O(nm) (where n is the length of the whole string, m is the length of the pattern). There are much better alternatives. For instance Boyer-Moore with the linear complexity this function is its implementation.
• one_of():  It tests the elements of a sequence and returns true if exactly one of the element share the property given. It takes a sequence and a predicate, and returns true if the predicate returns true for exactly one given element in the sequence.
• gather(): This function takes a sequence of elements defined by a pair of iterators and moves the ones satisfying the predicate to a position called as pivot within the sequence. The algorithm is stable i.e. elements returning true for the predicate will be arranged in same sequence as in old sequence.

Try To Implement These Algorithms...