Alas, It's time for another day of STL in CP. Last time we covered the Non-modifying sequence operations, and as you may have expected, we shall cover the Modifying ones this time. The concept is simple- they simply modify a range or a variable (or multiple of them) which you have given to the functions. But the usage? There are something deeper when we think about the details of these functions. In this article, We will cover trivial functions quickly, and then take some time in looking at the ones with more interesting usages.
copy, copy_if, copy_n, copy_backward
These are quite trivial, they do what their names suggest. copy copies, copy_n copies $$$n$$$ elements from the beginning, copy_backward does the same thing with copy but copies the last element first. Time complexity takes $$$O(n)$$$ assignments, so it's $$$O(n)$$$ assuming the types you're copying takes $$$O(1)$$$ to assign. Otherwise, it's multiplied by their time complexity, obviously. copy_if is a bit more useful, though, as functions with filtering features are always useful somewhere.
move, move_backward
Those two do the same thing with the copy ones, except this one moves the elements, meaning that it reuses the addresses of the original range. It may use less time than copy, but is only useful when you do not need the original range. beware!
fill, fill_n
If you can read, you should know what this function does. it simply "fills" a range. Time complexity is $$$O(cn)$$$ where $$$c$$$ is quite obviously the time for one assignment, which is most likely $$$1$$$ or some small constant unless if you're filling a multidimensional container, say, a vector<string>.
transform
This is when things get interesting. Basically, this function applies a function to all elements in a range (or two) and copies the results to another range (or writes it in-place if you want it to). Why is this interesting? Because it can work in all situations where you want to apply a function to a range or two, basically any function in the format of $$$y = f(x)$$$ or $$$z = f(x,y)$$$. And for this reason, this function can be used in implementing Sparse Tables. The code is as follows:
Snippetint st[K + 1][MAXN];
for (int i = 0; i < N; i++)
st[0][i] = f(array[i]);
for (int j = 1; j <= K; j++)
transform(st[j - 1] + (1 << j - 1), st[j - 1] + N, st[j - 1], st[j], f);
// base code is from https://cp-algorithms.com/data_structures/sparse-table.html#precomputation
// notice the swap on row and column
// for addition you can use std::plus as f
// for minimum, unfortunately you might need a lambda or a functor
Code getting AC on 'Static RMQ' @ Library Checker#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include<bits/stdc++.h>
using namespace std;
int st[21][505050];
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n,q;cin>>n>>q;
for(int i=0;i<n;i++)cin>>st[0][i];
for(int j=1;j<__lg(n)+1;j++)transform(st[j-1]+(1<<j-1),st[j-1]+n,st[j-1],st[j],[](int a,int b){return min(a,b);});
while(q--)
{
int l,r;cin>>l>>r;
int j=__lg(r-l);
cout<<min(st[j][l], st[j][r-(1<<j)])<<"\n";
}
}
generate, generate_n
This function is used when you want to fill a range with values generated by a function, functor, lambda, or basically any callable. This being said, this includes an RNG, meaning this function can be used for filling an array with random values. More interesting things can be done also, such as filling the range with a certain integer sequence, for example the fibonacci sequence. Just use something such as [a=0,b=1]mutable{int c=(a+b)%1000000007;a=b;b=c;return a;} as the function, and this function will be filling the range with the fibonaccci sequence. I think there should be more interesting and creative uses of this function, let me know in the comments if you know any.
remove, remove_if, remove_copy, remove_copy_if
These functions are supposed to "remove" elements from the range. However, the functions can't just "resize" the range, they do not have access to the entire container. Therefore, it is almost always used with erase (member function of the container). This is called the Erase-Remove Idiom. However on C++20 and above, the Erase-Remove Idiom is unneeded in most cases. Instead of it, you can use erase(container, value) and erase_if(container, function). While this is the case of resizable containers, the range used with this function does not have to be one of a resizable container. For example, when you want to use it with an array, you can maintain a size variable, and update it when you run this function. Like this — sz = remove(arr, arr + sz, x) - arr. The latter two do the same operation while copying the result to another range. They are usually unused in CP (we do not want to add another factor to our space complexity), but if we want to preserve the original range, then the two may be used instead.
replace, replace_if, replace_copy, replace_copy_if
Does the same thing as remove, but instead of removing from the range it replaces them to another value. These do not resize the range, so they do not need to be used with erase. Same opinion as above about the latter two, you may use them when you need to preserve the original range. I have still not seen someone actually use the latter two in CP, though.
swap, swap_ranges, iter_swap
Straightforward. swap does what it suggests, swap_ranges swaps all elements in two ranges. (like this short snippet — for(int i=0;i<n;i++)swap(a[i],b[i]);) And iter_swap is literally swap(*a,*b). Do I need to explain further? I don't think so.
reverse, reverse_copy, rotate
rotate_copy, shift_left, shift_right
The former two reverses a range, the medium two rotates a range, the last two (added in C++20) shifts elements in a range. Why did I list these three sets of functions in the same paragraph? Because they can serve a common purpose in CP (especially Codeforces) — Reducing the hassle of implementation. Usually D2A and D2B can be solved relatively quickly, but a fast mind may not be very helpful when the implementation is quite complex. This is where these functions come into action. Here is a practice problem in which one of these functions will help you, I suggest you try it if you didn't already. (Problem: 1711A - Perfect Permutation) These functions are useful in many problems with constructive algorithms in general, so it would be a good idea to use them when you can!
shuffle, sample
Oh, shuffling and sampling, the two important operations in randomized algorithms. The former shuffles elements in a range uniformly with a given RNG. "uniformly" here is important, it's the exact reason random_shuffle was deprecated and then removed in C++20! So make sure not to use random_shuffle in all cases. You can learn more about it in this blog. Now the latter function should be used with care, it samples $$$\text{min}(N,\text{size})$$$ distinct elements in a range. However sometimes you might just want to pick $$$N$$$ elements allowing duplicates, or the situation might be that $$$\frac{N}{\text{size}}$$$ is so small that getting a duplicate is quite unlikely. In this situation, it would be reasonable to just generate $$$N$$$ indexes in the range of $$$[1,N]$$$, right? However, sample has a time complexity of $$$O(\text{size})$$$. Therefore, you need to be careful when using this function, it might cause unwanted TLEs.
unique, unique_copy
These two functions (latter copying the result to another range) remove adjacent duplicates from a range. As it cannot resize the container by itself, usually it is used with erase, similar to the Erase-Remove Idiom explained above. Removing only adjacent duplicates means that this function, alone, can't remove all duplicates in any given range. Therefore, for this function to be able to remove all duplicates in the range, the range needs to be sorted. However, this does not mean that this function is only useful when the range is sorted. There are situations when we need to check adjacent groups, one example would be GCJ 2022 Round 1C — Letter Blocks. In a part of this problem's solution, we need to check if a string is "grouped" (i.e. each alphabet appearing in the string make up one contiguous group). Of course, you can do this by counting in $$$O(n)$$$, but I felt this method was very ugly and complex in terms of implementation. I have come up with a slower but elegant way to do this, which has an $$$O(n \log n)$$$ time complexity. Here is how.
How to do it — What I call the 'Double-unique method'If a string is "grouped", all duplicates will be removed, regardless of sorting or not. Therefore, if you use unique once, sort the string, and then do unique a second time, the string's length should not change on the second time if the string is "grouped". The time complexity is $$$O(n \log n)$$$ due to sorting. (You can reduce the complexity further by implementing counting sort, but this would be equivalent to the usual $$$O(n)$$$ method.) You can implement this "Double-unique method" by just using STL functions, and I really like this method for this reason.
In this section we reviewed the modifying sequence operations, and found out situations where they can be used. In the next section of Chapter 1. Algorithms, we will be reviewing a wide variety of functions, such as sorting, merging, binary search and more. See you on the next section!
Back to chapter 0
