{"id":188,"date":"2020-06-19T09:12:48","date_gmt":"2020-06-19T08:12:48","guid":{"rendered":"http:\/\/pranavmani.com\/?p=188"},"modified":"2020-06-20T13:35:52","modified_gmt":"2020-06-20T12:35:52","slug":"stl-algorithms","status":"publish","type":"post","link":"https:\/\/pranavmani.com\/?p=188","title":{"rendered":"STL Algorithms"},"content":{"rendered":"\n<p>I was watching a talk by Jonathan Bocarra on &#8220;<a href=\"https:\/\/www.youtube.com\/watch?v=2olsGf6JIkU\">105 STL algorithms in less than an hour<\/a>&#8221; 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:<\/p>\n\n\n\n<p>Why should you use STL algorithms?<\/p>\n\n\n\n<ul><li>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.<\/li><li>Avoiding having to write raw-loops, conditional checks.<\/li><li>Part of C++ standard, behavior uniform across different compilers.<\/li><\/ul>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Heaps:<\/strong><br>In C++, heaps are implemented as a max heap where the parent is bigger than the children.<br>The first algorithm mentioned in the talk is <code>make_heap<\/code>, wherein you can take a structured set of data, a convert into heap using <code>make_heap<\/code>. 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 <code>push_back<\/code> and then using <code>push_heap<\/code>. <code>push_heap<\/code> reorders the vector according the properties of the heap. To remove the first element from the heap, you can use <code>pop_heap<\/code>. However, the value still remains in the heap, to remove it from the heap permanently, you can use <code>pop_back<\/code>.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Sorting:<\/strong><br>As everyone would be familiar, the most common way to sort a list would be to use <code>sort<\/code>.<br><code>partial_sort<\/code> 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. <code>nth_element<\/code> 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. <code>sort_heap<\/code> sorts a heap, this can also be acheived by continuosly calling <code>pop_heap<\/code>. <code>inplace_merge<\/code> is the incremental step in a merge sort, i.e when you have a list which is sorted into two halves. <code>inplace_merge<\/code> can be used to convert the lists into a single sorted list.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Partitioning:<\/strong><br>Partitioning of a collection can be used to partition a collection into two parts using a specific condition. <code>partition<\/code> can be used to partition a collection and <code>partition_point<\/code> can be used to get the position at which the partitioning of the collection starts.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Permutations:<\/strong><br>Rotation basically rotates the the list, i.e the last element is moved to the first. <code>shuffle<\/code> can be used to shuffle the elements randomly. <code>next_permutation<\/code> and <code>prev_permutation<\/code> can be used to obtain the next permutation of the list and the previous permutation. <code>reverse<\/code> can be used to reverse a list.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Miscellaneous:<\/strong><br>These can be used to combine with other algorithms to get new algorithms.<br>With <code>stable_*<\/code> 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 <code>stable_sort<\/code> or <code>stable_partition<\/code>. <code>is_*<\/code> can be used to check whether a certain structure follows a certain condition. For instance, <code>is_sorted<\/code> returns a boolean to check whether the given list is sorted or not. <code>is_*_until<\/code> 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<br>does not start to hold. For example, <code>is_sorted_until<\/code> will return an iterator the end for a sorted collection.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Numeric algorithms:<\/strong><br><code>count<\/code> takes a beginning and an end an returns a value of how many times the element occurs in the list. <code>accumulate<\/code>\/<code>transform_reduce<\/code> can be used to return a sum or any other custom function on the list. <code>partial_sum<\/code> sums all the element till the current point in the collection. <code>inclusive_scan<\/code> is same as the partial sum, but this one can be run in parallel. <code>exclusive_scan<\/code> does not include the current element whereas inclusive_scan can includes the current element. <code>inner_product<\/code> is similar to a dot product(multiply individual elements, followed by a sum on the result). <code>adjacent_difference<\/code> returns the difference between two neighboring position. <code>sample<\/code> returns a random sampling of the collection.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Querying:<\/strong><br><code>all_of<\/code> takes a condition and returns if all of the elements follow the condition. <code>any_of<\/code>, by the name returns if any of the elements follow the condition. <code>none_of<\/code> returns if none of the elements follow the condition.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Querying on two ranges:<\/strong><br><code>equal<\/code> returns true if all elements on the lists are individually equal and the size is the same. <code>is_permutation<\/code> returns true if one of the list is the permutation of the other. <code>lexicographical_compare<\/code> returns a boolean if the lists are lexicographically are smaller than each other. <code>mismatch<\/code> can be used to traverse over lists and return the position where the lists start to differ.<\/p>\n\n\n\n<p><strong>Searching a value:<\/strong><br><strong>For an unsorted list:<\/strong><br><code>find<\/code> returns an iterator to the value you are searching for in the list. If it&#8217;s not found, it returns an itertor to the end. <code>adjacent_find<\/code> returns the first position where the adjacent values are equal.<\/p>\n\n\n\n<p><strong>For a sorted list:<\/strong><br>In a sorted list, <code>equal_range<\/code> returns a subrange where the values are equal. <code>lower_bound<\/code> returns indicates lower bound position in which the value is present and the <code>upper_bound<\/code> 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 <code>upper_bound<\/code> and <code>lower_bound<\/code> are equal. <code>binary_search<\/code> return true if the values is present in the list or not.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Searching a range:<\/strong><br>Searches a subrange of values within a bigger range. <code>find_end<\/code> searches for a subrange starting from the end. <code>find_first_of<\/code> can be used to search for any occurence of the smaller subrange in the bigger range.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Searching for a relative value:<\/strong><br>Searching for a relative value can be done using <code>max_element<\/code>, <code>min_element<\/code>, <code>minmax_element<\/code>.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Algorithms on sets:<\/strong><br><code>set_difference<\/code> 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. <code>set_intersection<\/code> returns the elements common to both the sets. <code>set_union<\/code> returns elements that are in one set or another. <code>set_symmetric_difference<\/code> returns elements that are unique to both the sets. <code>includes<\/code> returns a boolean if all the elements on one set are included on the other. <code>merge<\/code> merges both the sets into one sorted set.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Moving algorithms:<\/strong><br><code>copy<\/code> is the simplest one that copies elements from one container to anoter.<br><code>move<\/code> moves elements from one container to another.<br><code>swap_ranges<\/code> swaps the elements in a given range to another range. <code>copy_backward<\/code> 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 <code>move_backwards<\/code> which does a move instead of copy.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Value modifiers:<\/strong><br><code>fill<\/code> can be used to fill the same values inside the container. <code>generate<\/code> can be used to fill a structure using a generating function. <code>iota<\/code> can be used to put a value in the begining and that value is incremented as the rest of the structure is filled. <code>replace<\/code> can be used to replace the values in a collection.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Structure changers:<\/strong><br><code>remove<\/code> 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. <code>unique<\/code> removes the adjacent duplicates in a correction. similary, <code>erase<\/code> has to be called to update the container and it&#8217;s size. <code>*_copy<\/code> can be used to copy elements from one container to another, leavig the original container intact.<\/p>\n\n\n\n<p>Similarly, <code>*_if<\/code>, can be used to find\/replace\/copy elements that follow a certain condition.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Others algorithms that don&#8217;t fit in any &#8220;islands&#8221;:<\/strong><br><code>transform<\/code> can be used to transform a collection by means of a function or an operator on the element. <code>for_each<\/code> traverses through the container and calls a function on each element of the container. <code>for_each<\/code> can be used to produce &#8220;side effects&#8221; as a result of the operation on the container.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong>Raw memory:<\/strong><br><code>fill<\/code>, <code>copy<\/code> and <code>move<\/code> uses assignment operators, which means that the object should be constructed. Raw memory operators is for operating on chunks of memory. <code>uninitialized_fill<\/code>,<br><code>uninitialized_copy<\/code>, <code>uninitialized_move<\/code> can be used with constructors on chunks of memory. <code>destroy<\/code> can be used to destroy the elements in a container once you are done with your operations. <code>uninitialized_default_construct<\/code> and <code>uninitialized_value_construct<\/code> can be used for calling value or default constructors.<\/p>\n\n\n\n<p class=\"has-normal-font-size\"><strong><code>*_N<\/code> algorithms:<\/strong><br>Instead of iterating over the entire structure, these <code>*_n<\/code> algorithms, can be used to iterate over the given position and size after the given element.<\/p>\n\n\n\n<p>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 <a href=\"http:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet.pdf\">here<\/a>. The \\(LaTeX\\) source can be found on <a href=\"https:\/\/github.com\/pranav656\/STL-Cheat-Sheet\">Github<\/a>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"791\" height=\"1024\" src=\"http:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-791x1024.png\" alt=\"\" class=\"wp-image-194\" srcset=\"https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-791x1024.png 791w, https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-232x300.png 232w, https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-768x994.png 768w, https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-1187x1536.png 1187w, https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-1583x2048.png 1583w, https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet-1568x2029.png 1568w, https:\/\/pranavmani.com\/wp-content\/uploads\/2020\/06\/STL_Cheat_Sheet.png 1700w\" sizes=\"(max-width: 791px) 100vw, 791px\" \/><\/figure>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>I was watching a talk by Jonathan Bocarra on &#8220;105 STL algorithms in less than an hour&#8221; 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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_oct_exclude_from_cache":false,"footnotes":""},"categories":[3],"tags":[],"_links":{"self":[{"href":"https:\/\/pranavmani.com\/index.php?rest_route=\/wp\/v2\/posts\/188"}],"collection":[{"href":"https:\/\/pranavmani.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pranavmani.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pranavmani.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pranavmani.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=188"}],"version-history":[{"count":6,"href":"https:\/\/pranavmani.com\/index.php?rest_route=\/wp\/v2\/posts\/188\/revisions"}],"predecessor-version":[{"id":198,"href":"https:\/\/pranavmani.com\/index.php?rest_route=\/wp\/v2\/posts\/188\/revisions\/198"}],"wp:attachment":[{"href":"https:\/\/pranavmani.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=188"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pranavmani.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=188"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pranavmani.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=188"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}