Last time, we reviewed very briefly about what is STL. In this Chapter of the series, we will be talking about the algorithms it provides, and their value in CP (speaking of "value", some functions may be almost absolutely useless in CP due to another feature or some reason). We are not going to talk about using ranges for now, they are bound for another article. In Section 1 of Chapter 1, we will be talking about Non-modifying sequence operations. (I suggest that you read this article side by side with Cppreference, I get a lot of ideas and knowledge there, and the Sections are divided for convenience in reading side by side.)

all_of, none_of, any_of

These three functions are quite straightforward, and have $$$O(n)$$$ time complexity (if the passed function has $$$O(1)$$$ time complexity). They may be useful in many situations, but I have not found a real usage example yet.

for_each, for_each_n (C++17)

These two functions apply a certain (unary) function to each element of a container. Their time complexity is, quite clearly, $$$O(n)$$$, considering the case when the function applied takes $$$O(1)$$$ time. However, the former has been useless in my case, as range-based for statements were sufficient for me. The latter, though, may be very useful, and is not replaced by the range-based for statement.

count, count_if

These two functions count the number of elements in the container that, for the former, matches a value, and for the latter, meets a condition. Their time complexity is $$$O(n)$$$, assuming the function takes $$$O(1)$$$ time. Both are useful in my opinion, but the latter is much more important in CP. This is because CP asks for the amount of values meeting a certain condition, more frequently than asking for a certain value.

mismatch

This function iterates through two ranges of iterators and then returns the first position where the values differ or the function passed returns a falsy value (which is 0). The time complexity is $$$O(n)$$$ assuming the function passed (== by default) takes $$$O(1)$$$ time. Now this function is very important, in the sense that we can compare two ranges and check if all elements in range A meets a condition relative to range B. We can even check if a range is a palindrome with this function, by passing the iterators and reverse iterators to this function, and checking if the function finished at each ends. Do note that this function returns a pair of iterators, and this in turn could give an advantage over using the equal function (which only returns a boolean value).

find, find_if, find_if_not

I am not going to talk too much about these functions in this article, their uses/time complexity/etc are too trivial and well-known. However, do note that, for the same reason stated about count_if, the latter two have relative importance over the former one.

find_end, search

In my opinion, I thought find_end would have been better named as search_end, as search does the same thing, except find_end searches for the last occurrence while search searches for the first. These functions by default searches naively, so it has an $$$O(nm)$$$ time complexity. Do use KMP when needed; naive (and Boyer-Moore in its worst case) searching methods are too slow for CP.

find_first_of

This function finds the first occurrence of any value existing in a certain set (represented with a range) in a range. For example, you can find the first occurrence of any value in {2, 4, 6, 8} in a vector. This function has an $$$O(Sn)$$$ time complexity, and therefore when looking for exact matches it can be replaced with the tree-based/hash-based containers for $$$O(log(S)n)$$$, $$$O(n)$$$ time complexity correspondingly. However these container-based methods might not do very well when in need of applying a function to compare the elements (trust me, traversing these containers are $$$O(n)$$$ but it is a pain due to cache issues), so in this case this function may be helpful.

adjacent_find

This function compares adjacent values, and returns the first position where the values are identical, or meet a condition when passed a function. This function has $$$O(n)$$$ time complexity, assuming the comparison function has $$$O(1)$$$ time complexity. I have found usage of this function in 1713B - Оптимальное уменьшение, consider the following explanation as a solution for the problem.

As shown in the explanation above, adjacent_find has great strength in comparing adjacent elements inplace, without making a difference array. For this reason, I consider this function very important in CP.

search_n

This function finds the first point where $$$n$$$ consecutive elements in a row exist, which are same with the given argument (or meets a condition compared to it). This may be useful in problems such as when you need to find $$$k$$$ consecutive positive numbers. Do remember though, that the given function takes the elements on the left argument and the argument in the right argument.

In this article, we reviewed the Non-modifying sequence operation functions in the Algorithm category of STL. In the next section, we will be reviewing the Modifying sequence operation functions.

Back to chapter 0