Qualified's blog

By Qualified, 3 years ago, In English

With pllk introducing 100 more problems to the CSES problemset, the race for shortest code is on. Here in this blog, I talk about the many different ways of shortening code to get that shortest code.

std::any_of

This is a very useful function that returns true iff any of the elements in the range [first, last) satisfies some condition. Let's say you want to figure out if an array contains at least one 9. You could just write the naive loop and waste time in contest.

bool ok = 0;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] == 9) {
		ok = 1;
		break;
	}
}

but you could be smart and write this all in one line.

bool ok = any_of(a.begin(), a.end(), [](int x) { return x == 9; });
Time Complexity

This is linear aka $$$O(n)$$$.

std::all_of

This is another useful function that functions similar to std::any_of. The difference is that it returns true iff all the elements in the range [first, last) follow some condition.

Let's say you want to find if the array consists of all 9's.

bool ok = 1;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] != 9) {
		ok = 0;
	}
}

Now this method saves a couple of lines which means that you'll get the fastest submit time. Guaranteed or I will give you your money back. :D

bool ok = all_of(a.begin(), a.end(), [](int x) { return x == 9; });
Time Complexity

Like the function that I mentioned, this is also $$$O(n)$$$.

std::none_of

This is yet another function that is close relatives of the two mentioned above. This function returns true iff all the elements does not follow some condition.

Let's say you want to find if the array doesn't contain 9.

Noobs will do:

bool ok = 1;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] == 9) {
		ok = 0;
	}
}

Pros would do:

bool ok = none_of(a.begin(), a.end(), [](int x) { return x == 9; });

This next one is very useful and it appears quite frequently in problems on various judges.

Time Complexity

Linear, $$$O(n)$$$.

std::for_each

Thanks to Ta180m for pointing this out in the comments. This function applies a function hld to all of the elements in the range of [first, last).

Lets say that you want to increase all the elements in some vector by 5.

Naive way:

for(int i = 0; i < (int)(a).size(); ++i) {
	a[i] += 5;
}

A shorter way to write it would be:

auto change = [&](int& x) {
	x += 5;
};
for_each(a.begin(), a.end(), change);

As mentionted by purplesyringa, if you want to iterate from begin ... end it is better to use range-based for loops. std::for_each is only really useful when your iterating from something else other than begin ... end.

Time Complexity

$$$O(n \cdot X)$$$ where $$$X$$$ is the complexity of applying the function hld once.

std::count

This functions counts the number of elements in the range [first, last) that are equal to some variable val.

Noobinho:

int cnt = 0;
for(int i = 0; i < (int)(a).size(); ++i) {
	cnt += (a[i] == x);
}

Proinho:

int cnt = count(a.begin(), a.end(), x);
Time Complexity

$$$O(n)$$$.

std::find

This function returns the first iterator that compares equal to val.

Thanks to _rey for pointing this out to me. :)

NOTE: if using std::find on sets, use set::find instead. This guarantees it to be $$$O(\log n)$$$ where $$$n$$$ is the size of the set.

Nubs:

int hld = -1;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] == x) {
		hld = i;
		break;
	}
}

Prubs:

int hld = find(a.begin(), a.end(), x) - a.begin();
Time Complexity

Linear, $$$O(n)$$$.

std::accumulate

Many coders use this function but I am still going to include it just in case you don't know the uses of it. This function returns the sum of init and all the elements from [first, last).

Let's say that you want to find the sum of all the elements in the vector. Beginners would do:

int sum = 0;
for(int i = 0; i < (int)(a).size(); ++i) {
	sum += a[i];
}

Now, we can use std::accumulate to do this in 1 line.

Thanks for N8LnR2Nqf8Q4FN for pointing this out to me.

NOTE: Be mindful for overflow when using std::accumulate. If you know that the sum will overflow, use 0LL otherwise use 0. If your not sure using 0LL won't hurt that much anyways.

int sum = accumulate(all(a), 0LL);
Time Complexity

$$$O(n)$$$

std::binary_search

This function is pretty useful in finding if the element val appears in the sorted range [first, last).

Let's say that you want to find if the element val appears in the sorted array. Standard binary search looks something like this.

bool ok = 0;
int l = 0, r = (int)(a).size(), target = val;
while(l < r) {
	int mid = (l + r) / 2;
	if(a[mid] < target) {
		l = mid + 1;
	} else if(a[mid] == target) {
		ok = 1;
		break;
	} else {
		r = mid;
	}
}
bool ok = binary_search(a.begin(), a.end(), val);
Time Complexity

$$$O(\log n)$$$

std::max_element

This function returns the max element in the range [first, last).

int cur = -INF;
for(int i = 0; i < (int)(a).size(); ++i) {
	cur = max(cur, a[i]);
}

Better way to do it is:

int cur = *max_element(a.begin(), a.end());
Time Complexity

$$$O(n)$$$

std::min_element

This is basically the same as std::max_element but returns the min element in the range [first, last).

int cur = INF;
for(int i = 0; i < (int)(a).size(); ++i) {
	cur = min(cur, a[i]);
}
int cur = *min_element(a.begin(), a.end());
Time Complexity

Linear in time, $$$O(n)$$$.

std::is_sorted

This function is for checking if the range [first, last) is sorted. Its pretty self-explanatory.

bool ok = 1;
for(int i = 1; i < (int)(a).begin(); ++i) {
	if(a[i] < a[i - 1]) {
		ok = 0;
	}
}
bool ok = is_sorted(a.begin(), a.end());

Alternatively, if you want to check if the range is sorted but in reverse order, you can first reverse the sequence and then check if it's sorted.

reverse(a.begin(), a.end());
bool ok = is_sorted(a.begin(), a.end());
Time Complexity

$$$O(n)$$$

std::lexicographical_compare

This function is used in many problems that compares two containers and checks which one is lexicographically first.

bool ok = lexigraphical_compare(a.begin(), a.end(), b.begin(), b.end());
Time Complexity

$$$O(n)$$$.

std::partial_sum

Thanks to Kavaliro for pointing this out to me. Imagine doing a prefix sum problem. You want to obviously compute the prefix sums. Naive way to do it would be

for(int i = 1; i < (int)(a).size(); ++i) {
	a[i] += a[i - 1];
}

Now, as Kavaliro pointed out, this could be done in 1 line.

partial_sum(a.begin(), a.end(), a.begin());

Suffix sums are much the same thing

partial_sum(a.rbegin(), a.rend(), a.rbegin());
Time Complexity

Both are linear, $$$O(n)$$$.

std::adjacent_difference

Thanks to elsantodel90 for pointing this out to me. Since I already included the std function for prefix sum, it "only natural to mention adjacent_difference too" — elsantode190. So here it is.

vector<int> hld = a;
for(int i = 1; i < si(hld); ++i) {
	hld[i] -= a[i - 1];
}

This takes 4 lines and much more characters than this:

adjacent_difference(a.begin(), a.end(), a.begin());

Saves a good amount of characters and shorter to type out.

Time Complexity

$$$O(n)$$$

std::iota

Thanks to purplesyringa for pointing this out to me! This function assigns every value from [first, last) successive values of val where val is the argument to the function. A useful scenario is when you have a DSU and you want to initialize it by setting each node's parent to itself. Now this can be done naively

for(int i = 0; i < n; ++i) {
    par[i] = i;
}

or it can be done in a much shorter way

iota(par.begin(), par.end(), 0);
Time Complexity

$$$O(n)$$$

Thats all for now, as I have school work to do. But I'll continue to update this blog with other useful functions. :D

  • Vote: I like it
  • +277
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice blog! std::for_each is also very useful.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the suggestion!

    EDIT: Added the function. A bit late I think lol.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Well done!

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

#define all(x) (x).begin(), (x).end() will save you some more time. However, most people don't spend as much time coding the solution as they do thinking about it, so I am not sure whether such shortcuts are necessary

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    I didn't want to have macros in my code as many people don't like macros when reading code. As for your second point I should've made it clear in the blog.

    Edit: Made it clear in the introduction what the purpose of this blog is for.

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

std::accumulate is another useful one.

»
3 years ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

Another one .. function to count numbers greater than or equal to x

int count_x = count_if(v.begin(), v.end(), [](int a) { return (a >= x); });

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Time complexity of all function mentioned above is O(n).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a good talk from cppcon about STL algorithms like these: https://www.youtube.com/watch?v=2olsGf6JIkU

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Mah boi has a positive contribution now! Alo nice blog.. Good job!

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

You can get all of these useful functions here --> https://en.cppreference.com/w/cpp/header/algorithm

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Just be careful with functions like std::find with sets. std::find is a linear time function, not log time. If you want to find an element in a set in log time, use set::find. Cplusplus reference

So, instead of

set<int> xs;
//some code over here
auto it = find(xs.begin(), xs.end(), x);

use

set<int> xs;
//some code over here
auto it = xs.find(x);

Also, both std::find and set::find return an iterator, and you can't subtract set iterators, so xs.find(x) - xs.begin() won't compile if xs is a set.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks for the tip! I will add that note to std::find.

    EDIT: Added note.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Or better use count to check containment in set.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please correct me if I'm wrong somewhere

      the complexity of count() is $$$O(count + \log n)$$$ (not $$$O(\log n)$$$), and count() uses more iterators than find(), so I still prefer set::find() != set::end(), although in CP, the difference won't be that much

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks for this blog. Please keep adding.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would be great to have similar blogs for other languages

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I would like to say a bit about std::accumulate

if you have, say, std::accumulate(begin(C), end(C), x), then the accumulation part will have the declared type of x, so if x is int for example, and the sum is too large, this might cause overflow, so make sure x has the right type first

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

std::accumulate can not only accumulate sum to inti, but also accumulate values over any binary operation.

For example: accumulate(all(a), 1, multiplies<int>()) will return the product of every element in all(a).

In general: accumulate(all(a), init, myfun)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Using multiplies() is probably a very bad idea because it will most likely overflow but yeah, using a function, perhaps a lambda [](const int& a, const int& b){return (a*b) % MOD;} would be nice.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

woah just use kotlin for these shenanigans

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    if only they allow me to use Kotlin at onsite competitions

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Kotlin and is_sorted???

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it -6 Vote: I do not like it

      (1 until a.size).all { a[it - 1] <= a[it] }

      or even a == a.sorted() if you don't care about asymptotics.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        I don't get it

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You run over all indices of the array a except 0 and check whether for each element (a[i]) the previous one (a[i - 1]) is less or the same.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            I can understand your comment without context, but what the point of your post with?

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Guranteed or I will give you your money back. :D

Thanks <3

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You missed a very handy function partial_sum. it allows you to make prefixes and suffixes quickly

vector<int> v({1, 2, 3, 4});
partial_sum(v.begin(), v.end(), v.begin());    // v = {1, 3, 6, 10}
partial_sum(v.rbegin(), v.rend(), v.rbegin()); // v = {20, 19, 16, 10}
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Very good reference! I think you could add the time complexity of each function :)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the feedback, will add time complexity.

    UPDATE: Added time complexities for all functions

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

partial_sum could be used for a lot more, for instance, to create a suffix max.

partial_sum(v.rbegin(), v.rend(), v.rbegin(), [](int a, int b) { return max(a, b); });

(But I wish I can use the stl max function with shorter code)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Of course you can

    partial_sum(v.rbegin(), v.rend(), v.rbegin(), max<int>);
    

    Since your lambda just max function itself.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think that works because max has multiple definitions, I don't believe the compiler can deduce the template type on its own.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        That's why it's $$$max<int>$$$ instead of $$$max$$$

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OHH, it doesn't work if you include <bits/stdc++.h> !

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Got mistake(
            Due to multiple overloads it must be:

            partial_sum(v.rbegin(), v.rend(), v.rbegin(), (const int& (&)(const int&, const int&)) max<int>);
            

            And it still be incorrect with C++20 because taking address to std function there has unspecified behaviour.

»
3 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I haven't seen any of these functions until I read this blog... Is anybody here the same?
By the way, there is also a useful function in STL called std::nth_element. This function is mainly used to arrange the k-th smallest integer in the array element and place it in the array, which can be called at any time. Could poster consider adding this function?
P.S. How to use it in your code:

nth_element (a, a + k, a + n); //put the kth small integer in place 

Time Complexity: $$$\mathcal{O}(n)$$$.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

std::iota is useful too. I often use it for sorting and DSU initialization.

Compare:

vector<int> order(n);
for(int i = 0; i < n; i++) {
    order[i] = i;
}
sort(order.begin(), order.end(), [&](int i, int j) { return arr[i] < arr[j]; });

vs

vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) { return arr[i] < arr[j]; });

DSU:

p.resize(n);
for(int i = 0; i < n; i++) {
    p[i] = i;
}
rank.resize(n);

vs

p.resize(n);
iota(p.begin(), p.end(), 0);
rank.resize(n);
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Added, thanks for the suggestion!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      BTW, it's probably worth mentioning that range-based loop is often better than for_each. Compare:

      for_each(a.begin(), a.end(), [](int& x) {
          x++;
      });
      

      vs

      for(int& x: a) {
          x++;
      }
      

      for_each is still useful when you use bounds other than begin..end though.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in std::for_each what purpose does this [&] serve I didn't understand.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you for the list, it really helped to open my mind to using more functional programming in c++. I rewrote some of my code to be a decent amount shorter with these. One function I used you didn't mention is std::count_if, a generalization of count for when you want to check how many elements of an array satisfy a condition.