Golovanov399's blog

By Golovanov399, 5 months ago, In English,

Hello, codeforces.

I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.

The things below are filtered by my personal sense of non-popularity (so no __builtin functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin.


  • all(x)

This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on all(x), so I define it here. So, I talk about

#define all(x) (x).begin(), (x).end()

Now sorting a vector looks like sort(all(vec)) instead of sort(vec.begin(), vec.end()).

However, it's not all about this define. Imagine you need to build a convex hull of a set of points. Usually the code looks approximately as follows:

vector<Point> getConvexHull(vector<Point> pts) {
    int min_pos = min_element(all(pts)) - pts.begin();
    swap(pts[0], pts[min_pos]);
    sort(pts.begin() + 1, pts.end(), &cmp);
    // ...
}

And it might not come to one's mind that pts.begin() + 1 is the same as 1 + pts.begin(), and hence the code can be rewritten as

vector<Point> getConvexHull(vector<Point> pts) {
    int min_pos = min_element(all(pts)) - pts.begin();
    swap(pts[0], pts[min_pos]);
    sort(1 + all(pts), &cmp);
    // ...
}

Be, however, careful with this, because this reduces code readability significantly. Thanks to my teammates AndreySergunin and white2302 for showing me this 1 + all(...) trick.

  • std::unique

This is also well known, but not as well as I want, so I leave it here. std::unique(begin, end) goes from begin to end, removes consecutive duplicates and returns the end of the resulting iterator range. So, for example, if vec = {1, 1, 2, 2, 3, 2, 1}, then unique(all(vec)) makes it equal {1, 2, 3, 2, 1, ?, ?} (where ? is not known, but probably the last two symbols are 2 and 1) and returns vec.begin() + 5. Usually, to make a vector containing only its unique elements, one writes

sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());

or creates a function/define make_unique (which is, actually, also a name of some existing function in C++) which does so.

  • nxt()

I noticed that many Kotlin Heroes participants often have some functions in their templates like readLong(), readToken() and so on. I understand that this may be for the sake of similarity with C++ paradigm where you can just read stuff or maybe because val (n, k) = readLine()!!.split(' ').map(String::toInt) is too long and weird for writing it just to read two numbers. However, what doesn't often come to mind is that a similar function in C++ can simplify a lot of things (or maybe it's just a matter of taste). So the function may look as follows:

int nxt() {
    int x;
    cin >> x;
    return x;
}

If a usual reading a graph looks like this:

int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
}

then with your little mriemd nxt() you can write the following:

int n = nxt(), m = nxt();
for (int i = 0; i < m; ++i) {
    int u = nxt() - 1, v = nxt() - 1;
    g[u].push_back(v);
    g[v].push_back(u);
}

However, be careful! If pts is a vector of points, then it's really better to read it in the following way:

for (int i = 0; i < (int)pts.size(); ++i) {
    cin >> pts[i].x >> pts[i].y;
}

or at least in the following C++17 way:

for (auto& [x, y] : pts) {
    cin >> x >> y;
}

But don't do the following:

for (int i = 0; i < (int)pts.size(); ++i) {
    pts[i] = {nxt(), nxt()};
}

because in the last implementation the order of nxt() calls is not defined.

Also you may change the type to long long or even make the function template, but I haven't really ever felt I need the last.

Big thanks to my former teammates savinov and sokian for introducing this to me in their team template back in 2015 when I joined them. nxt() will return later in this blog.

  • std::fill and std::iota

Many of you know that if one wants to fill a piece of memory with a specific byte, they can use memset. It's quite fast and can be used to fill some (usually 1-dimensional) C-arrays by zeroes and minus ones. What if you want to fill a container by ones? The answer is as easy as pie:

fill(all(vec), 1);

And if you need to fill it by consecutive numbers, you can use std::iota. Now the constructor of a Dsu class with two optimizations may look as follows:

int n;
vector<int> parent, rank;

Dsu(int _n): n(_n), parent(_n), rank(_n) {
    iota(all(parent), 0);
}

Here 0 denotes the value of *parent.begin(), and each next value is obtained from the previous one by the pre-increment.

  • std::generate

If you have a 0-ary function (that is, with no arguments) and want to fill a range by its calls, instead of writing a for loop you can call std::generate: filling a vector vec by random values (assume it's rand() calls) may look like

generate(all(vec), rand);

My favourite: to read $$$n$$$ followed by $$$n$$$ numbers you can write

int n = nxt();
vector<int> a(n);
generate(all(a), nxt);

or, if you don't need the value of n later, even

vector<int> a(nxt());
generate(all(a), nxt);

Bonus: the last three function have a _n analogs. Instead of the end iterator/pointer, fill_n, iota_n and generate_n take the size as the second argument. So if you want to read, say, first $$$n$$$ numbers into a vector vec of size greater than $$$n$$$, you can use

generate_n(vec.begin(), n, nxt);

instead of a longer

generate(vec.begin(), vec.begin() + n, nxt);

Thanks to fdoer for telling this.

  • std::rotate

Assume you write a profile dp. Or a 3-layer bfs. Or something else, where you need sometimes to cyclically shift a vector by $$$k$$$. If $$$k = 1$$$ then one can write a loop of swaps:

for (int i = 0; i < (int)vec.size() - 1; ++i) {
    swap(vec[i], vec[i + 1]);
}

But if $$$k > 1$$$ then the easiest way to do this manually is probably to create another vector, fill it accordingly and then set the initial vector to this. However a simple

rotate(vec.begin(), vec.begin() + k, vec.end());

can do the trick. This function works in such a way that after rotate(begin, middle, end) the element *middle becomes the first from begin to end.

  • std::merge

If you want to build a segment tree where each node contains a sorted list of values from the corresponding range then on its initialization you may need to merge two vectors several times (or if you implement your own merge sort). Some of you, probably, write some code like this:

for (int v = n - 1; v > 0; --v) {
    int i = 0, j = 0;
    while (i < (int)nodes[2 * v].size() || j < (int)nodes[2 * v + 1].size()) {
        if (j == (int)nodes[2 * v + 1].size() || (i < (int)nodes[2 * v].size() && nodes[2 * v][i] < nodes[2 * v + 1][j])) {
            nodes[v].push_back(nodes[2 * v][i++]);
        } else {
            nodes[v].push_back(nodes[2 * v + 1][j++]);
        }
    }
}

However, this code can be shortened:

for (int v = n - 1; v > 0; --v) {
    nodes[v].resize(nodes[2 * v].size() + nodes[2 * v + 1].size());
    merge(all(nodes[2 * v]), all(nodes[2 * v + 1]), nodes[v].begin());
}

Basically, std::merge takes 5 arguments: begin and end of one interval to merge, begin and end of the second interval to merge, and where to write the result. Don't forget to allocate the required memory (the purpose of .resize() in the code above)!

  • Create a set from a vector

Not many of us know, but if you want to create a std::set from a vector and find out that set doesn't have a constructor of vector, you may go write a loop with an ok face, like:

set<int> S;
for (int x : a) {
    S.insert(x);
}

However, std::set has a constructor of two iterators, so one can write

set<int> S(all(a));

This is actually very natural and one can deduce that set should have such a constructor, but I, to my shame, didn't know it until white2302 told me this recently.

  • Check if set or map have a key

This may be the most well known of above (as well as the least time-saving trick), but I still see that some experienced guys do the subj like

if (S.find(key) != S.end()) {
    // ...
}

However, set and map have a .count() method which returns 1 iff the key is in the container, otherwise 0:

if (S.count(key)) {
    // ...
}

The reason why it is called so and has an int type is that std::multiset and std::multimap also have this method, and for them the method returns the count of elements, which may exceed 1, obviously. Thanks to my former students dimas.kovas and krock21 for enlightening me about this.

Of course, if you need to do something with the element, if it is present in the set (for example, erase it), it may be useful to actually call .find() method in order to erase by iterator, not by element (thus kind of caching one tree descent).

  • Check if an element occurs in a sorted sequence

Assume that you have, say, a sorted vector, and you want to check if it contains an element, but unlike the previous case, you don't care about the element itself. In this case you don't need to implement your own binary search like

bool has(const vector<int>& vec, int key) {
    int l = 0, r = vec.size();
    while (r > l + 1) {
        int m = (l + r) / 2;
        if (vec[m] <= key) {
            l = m;
        } else {
            r = m;
        }
    }
    return l + 1 == r && vec[l] == key; // not to fall on the empty vector
}

Instead, you can just use

if (binary_search(all(vec), key)) {
    // ...
}

I think the function doesn't need any explanation (it returns bool, so there is really not much else one can extract from this). Thanks to some guy who used this method in some easy problem in an SRM.

  • std::partition_point

If we talk about binary search: assume you have a vector and a predicate p(x) so that p(x) = true for all elements of some prefix of vector vec and false on all others. To find the first place where p(x) doesn't hold one can simply use

int pos = partition_point(all(vec), p) - vec.begin();

In other words, partition_point(begin, end, p) returns the first iterator iter that p(*iter) = false, assuming that the condition above holds, that is, p is true on some prefix of [begin, end). I didn't use this in competitive programming (yet), but once wanted to use it for my job. Thanks to fdoer again for sharing his wisdom.

  • !!

Assume you want to use a function which maps 0 to 0 and every non-zero number to 1 (for example, to count non-zero numbers on all prefix subrectangles). The most observant of you may have notices that this is simply a cast to bool. The easiest bool casting operator is !! and it works like this:

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + !!a[i][j];
    }
}

Afaik, a mnemonic rule to remember it (if needed) is "bang, bang, you're boolean".

  • Print a binary representation of a number

If you want to print, say, last 20 bits of a number, it's not necessary to write smth like

void show_binary(int n) {
    for (int i = 0; i < 20; ++i) {
        cout << !!(n & (1 << i));
    }
    cout << "\n";
}

Instead, one can simply write

cout << bitset<20>(n) << "\n";

However, you need to fix the number of bits to show (which is usually not a problem because in most of the cases you need it for debug purposes) and get used to the order where the lowest bit is the rightmost (which is actually a natural order for a binary representation of a number, but not so natural if you consider a mask as a sort of a boolean vector).

Also, if you want to print an octal or a hexadecimal representation of a number, you can simply write cout << oct << n << "\n" and cout << hex << n << "\n", respectively. To return back to normal decimal, use cout << dec.

  • lambda type deduction

Imagine you want to quickly write a lambda which calculates the number of ways to choose $$$2$$$ elements from $$$n$$$. You may write something like this:

auto choose2 = [&](int n) {
    if (n <= 1) {
        return 0;
    } else {
        return 1ll * n * (n - 1) / 2;
    }
};

and see that the compiler cannot deduce the type of your lambda: in one place you return int and in another place you return long long. Ok, you may think, let's show the type explicitly. without auto:

function<long long(int)> choose2 = [&](int n) {
    if (n <= 1) {
        return 0;
    } else {
        return 1ll * n * (n - 1) / 2;
    }
};

To your surprise, the error doesn't disappear. You are not very happy, you replace 0 by 0ll and move forward feeling that you could surely have done this using some language tools.

Indeed, in the very first version you could actually explicitly specify the output type by a simple arrow:

auto choose2 = [&](int n) -> long long {
    if (n <= 1) {
        return 0;
    } else {
        return 1ll * n * (n - 1) / 2;
    }
};

Big thanks to my friends and colleagues Wild_Hamster, ArtDitel and fdoer again for showing me this construction (not only in this context, however).

  • Introducing variables inside an if statement

Imagine the following: you have a function f(), which takes time to be computed, and if its value satisfies some condition, you want to somehow use it. You don't want to write

if (is_good(f())) {
    use_somehow(f());
}

since it costs two calls of f. You may write something like this:

int x = f();
if (is_good(x)) {
    use_somehow(x);
}

but this is not very clean and leaves a variable which is not used then, maybe under a potentially useful name. To avoid this, one can wrap all this into a block like this:

{
    int x = f();
    if (is_good(x)) {
        use_somehow(x);
    }
}

but a shorter version would do the following:

if (int x = f(); is_good(x)) {
    use_somehow(x);
}

This is possible since C++17.

  • The smallest element from three

I bet many, many of you at least once wrote something like

int x = min(min(a, b), c);

feeling that something you do in your life is not right (while you type this, you usually have time to think about such things). Things get worse if you want to get a minimum of four elements:

int x = min(min(min(a, b), c), d);

(the order or arguments and the way to regroup them does not matter). You may have written a variadic template in your, well, template, to call something like min(a, b, c, ...), but you may do this without any prewritten code. Just watch:

int x = min({a, b, c, d});

Credits to the Jinotega twitter for this.


I'm sure I forgot something. I also feel that this blog is like a quick start guide into stl. Still, I hope a lot of you will find something useful here. C++, as every other language (programming or natural), is evolving, after all, and we should keep our eyes on how we can use it efficiently.

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

»
5 months ago, # |
  Vote: I like it +44 Vote: I do not like it

I'm sure I forgot something

I forgot to add that you guys are welcome to post similar tricks in comments if you think they are also useful!

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    The nth_element(all(X), n) gives the nth element from the first in the sorted list. I believe it uses randomized quick search to achieve the linear complexity. So, there's a side effect of a part of X being randomized during the call. This, I think, can be avoided if we call the method in another function which takes X as a call-by-value argument.

»
5 months ago, # |
  Vote: I like it +93 Vote: I do not like it

About lambdas:

auto choose2 = [&](int n) {
    if (n <= 1) {
        return 0LL;  // You can also specify the 0 literal's type explicitly.
    } else {
        return 1LL * n * (n - 1) / 2;  // I also recommend LL instead of ll to avoid confusion with 11.
    }
};

About multiset::count and multimap::count: they work in $$$O(count + \log n)$$$, not $$$O(\log n)$$$ as one may expect. So do not use them at all if your container has a lot of duplicates.

»
5 months ago, # |
  Vote: I like it +36 Vote: I do not like it

About unique: instead of vec.resize(unique(all(vec)) - vec.begin()); I prefer vec.erase(unique(all(vec)), vec.end());.

»
5 months ago, # |
  Vote: I like it +272 Vote: I do not like it

1 + all(ptr) is just wild

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Very nice! my favorites:
1-

vector<int> a(nxt());
generate(all(a), nxt);

2- std::partition_point

3- !!

4- cout << bitset<20>(n) << "\n";

5-

if (int x = f(); is_good(x)) {
    use_somehow(x);
}
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

to master std::rotate you can use this video (if I didn't mixed it with some other from Sean)

»
5 months ago, # |
  Vote: I like it +42 Vote: I do not like it
  • std::nth_element (I don't remember from where I got this function but I guess CP3 book.)
    • which rearranges the list in such a way such that the element at the nth position is the one which should be at that position if we sort the list.
template
Where can use?
  • equal_range (thanks to pllk in his book)
    • returns both the lower_bound and upper_bound pointers
Where can use?
»
5 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Can I ask a dump question ?

In this code

if (int x = f(); is_good(x)) {
    use_somehow(x);
}

Why is there only one ';' for the for-loops ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we don't have any for-loops there, only if

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :v sorry, I dont know why but I thought that was a for-loops

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cppreference/if helps a lot.

    If Statements with Initializer

    If init-statement is used, the if statement is equivalent to

    {
        init_statement
        if constexpr(optional) ( condition )
            statement-true
    }
    
»
5 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Well C++20 is coming soon, and the new features include a way to not use all() macro.

»
5 months ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

About std::merge

    nodes[v].resize(nodes[2 * v].size() + nodes[2 * v + 1].size());
    merge(all(nodes[2 * v]), all(nodes[2 * v + 1]), nodes[v].begin());

This code can be shortened further:

    // nodes[v].clear();
    merge(all(nodes[2 * v]), all(nodes[2 * v + 1]), back_inserter(nodes[v]));
  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    You'd better nodes[v].reserve(nodes[2 * v].size() + nodes[2 * v + 1].size()) as well before using back_inserter to avoid reallocations.

»
5 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

Thanks for the nice blog !!

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thx for the nice blog, especially the last one T-T(*me thinking about hours of writing min(min(min(min(min . . .*).

»
5 months ago, # |
  Vote: I like it +34 Vote: I do not like it

That's a lot of aliases for trivial loops.

»
5 months ago, # |
  Vote: I like it +232 Vote: I do not like it

That's a nice collection of little things to make life easier, thanks.

But I don't like the idea of such blogs because of how many novices view competitive programming. All these things won't make you able to solve more problems in less time, and even spending 2 minutes less time on writing your monstrous 300-line solution to simple 30-lines problem won't help you get better places.

So, to all div2 people who thinks "That's what I needed": no, you need to train more. That is, if you want to get better.

  • »
    »
    5 months ago, # ^ |
    Rev. 8   Vote: I like it +24 Vote: I do not like it

    "That's what I needed": no, you need to train more. That is, if you want to get better.

    But sir, I see some people have become GM (red) in one year (whereas I cannot solve div 2 A and B after 10 years and solving 10000 div 3A level problems on different OJs). So there must be some secret programming trick/library/macro and code editor/test case parser that you LGMs are hiding. I urgently need to become red so that I can show off to my Google interviewer and clinch a high paying job. Um_nik sir, please teach me how to give contests so that I can become red in 6 months.

    p.s. I will treat you to Biryani and Dosa for one year if you show me the secret backdoor.

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

      LoOooOoOLoOOooOoLoOOoOoOOooOooOOLoOooOOoOOoOOL. ROFL. LMAO.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since when you guys will understand there is no short cut in this line

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See my 900 line premade function set for an example of div 2 noobs building monstrous codes rather than training! It not only includes many obscure, useless, functions, but several functions for which STD also provides implementation for!

»
5 months ago, # |
  Vote: I like it +81 Vote: I do not like it

nxt() and 1 + all hacks seem to me too dangerous, they will save you several seconds when you write code, but one case per 20 you will lose 10 minutes to find strange bug

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    What can possibly go wrong with nxt()?

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

      You even wrote it in your blog. Sure there are several more cases when order is not defined.

»
5 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Other libstd functions I use are std::accumulate, std::partial_sum and std::is_sorted.

»
5 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

I'm pretty sure that also guaranteed to work left-to-right. because there's a common trick to put everything in brace-initializer to make it ltr

for (int i = 0; i < (int)pts.size(); ++i) {
    pts[i] = {nxt(), nxt()};
}
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok, it seems that one day I've encountered the wrong order when I wrote Point p(nxt(), nxt()) or something like this and generalized this behaviour for all similar cases

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      What about make_pair(nxt(), nxt())? Is order guaranteed then?

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

        I don't think so -- make_pair is a function and eval order is not guaranteed for functions.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Only {} cases are guarantied. Moreover, there are MSVC issues with the order of arguments construction in the case of {} style constructor call, like this:

        //some_type(std::vector<int>, std::vector<int>)
        //std::vector<int> v
        some_type some{ v, std::move(v) }; //on MSVC vector(vector&&) may be called before vector(vector const&)
        

        I do not know does this problem affect expression evaluation order or not.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good to know, that's another reason for switching to using list-initialization whenever possible.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        struct point { int x; int y; };
        struct line { point p; int c; };
        line l{ 0, 0 }; //ok
        
»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Wow, this is such a helpful blog. Thanks for your work!

»
5 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

std::minmax_element

vector<int> x = {1, 2, 3, 4};
auto it = minmax_element(all(x));
cout << *it.first << ' ' << *it.second << endl;

output:
1 4

std::equal

bool is_palindrome(string s) {
    return equal(all(s) - s.size() / 2, s.rbegin());
}
»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Note that if _GLIBCXX_DEBUG is defined, then lower_bound will give an error if the invariant is not satisfied:

std::vector<int> data {1, 2, 3, 2, 1};

std::lower_bound(begin(data), end(data), 2); // error, good

However, partition_point will not:

std::partition_point(begin(data), end(data), [&] (int x) {
    return x < 2;
}); // no error

It's possible to use lower_bound instead like this (but the intention is less clear)

std::lower_bound(begin(data), end(data), std::monostate{}, [&] (int x, std::monostate) {
    return x < 2;
});

std::monostate can be replaced by anything.

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Talking about ugly functional oneliners, one can use

copy_n(istream_iterator<int>(cin), n, A.begin());

to read n integers and write it to A,

copy_n(istream_iterator<int>(cin), n, back_inserter(B));

to read n integers and push them to B and

copy(B.begin(), B.end(), ostream_iterator<int>(cout, " "));

to write them to cout. Never actually used it, though.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We can use rall as well using the reverse iterator to do things like order a vector in descending order.

#define rall(x) (x).rbegin(), (x).rend()

And then sort(rall(vec)) instead of sort(all(vec)) and reverse(all(vec))

»
5 months ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

One day I wrote a code for problem during a contest where I should know a number of capitals on prefix, something like this:

std::string s; std::cin >> s;
std::vector<int> cap{0};
for (auto it : s) cap.push_back(cap.back() + std::isupper(it));

Of course, it was incorrect, because this function returns any non-zero value if 'A' <= it && it <= 'Z' and zero if not. It was a small part of program, so I debugged a 20 mins correct solution. Now I always use !!std::isupper(it) and !! with any function like this.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, calling isupper and similar standard functions on values outside of [0;127) is undefined behavior, IIRC.

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

    Not using "using namespace std;" in competitive programming is shooting yourself in a foot and getting absolutely nothing in return. Have you ever used abs on long longs :)? This is just evil what happens then.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://en.cppreference.com/w/cpp/numeric/math/abs

      Why do you think abs on long long is a problem? It seems to me that there is an overload for long long in C++, not in C though.

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

        Of course, if you use it with std then everything is fine. But if you don't preced it with std:: then it will compile as well and very likely work on samples and give very hard to find WA, because there is abs outside of std:: as well which works on ints only. Of course if you remember you should preced it with std:: then it is fine, but it is particularly evil trap and you can't really be sure you know all of them and how to prevent them. And again, absolutely no profit for not using std.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I prefer to use next tips and tricks when nobody sees:

      using namespace std;
      using namespace boost;
      using namespace experimental;
      using namespace pmr;
      using namespace __gnu_pbds;
      using namespace tr1;
      
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is scary!! (O∆O)

»
5 months ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it
std::function<long long(int)> choose2 = [&](int n) {
    if (n <= 1) {
        return 0;
    } else {
        return 1ll * n * (n - 1) / 2;
    }
};

To your suprise this kind of code may work painfully slow (link) and it misuses the std::function type. The rule for competitive programming is: you never need std::function.

The right version of the snippet is:

const auto choose = [&] (int n) {
    return n <= 1 ? 0 : 1ll * n * (n - 1) / 2;
};
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, your suggested code mustn't compile because of the same reason, that is: the results of ternary operator must have the same type, while 0 and 1ll * ... are of different types.

    Could you please elaborate why we should never use std::functions? They are very convenient sometimes, and i don't remember many cases when they were a bottleneck

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The code of course compiles, because ternary detect common type for both expressions.

      I don't remember any case where it would significantly help but you can't easily replace with actual lambda type (except for recursion where slowdown may be quite significant and where it's still straightforward to avoid)

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      In competitive programming you have the entire program in one TU (.cpp file) and you like never need to use TypeErasure classes (e.g. std::function or std::any) as you can preserve the entire type information with templates (mainly auto lambdas; see also: recursion). TypeErasure classes are very convenient when you need to pass the TU (or project) boundary (e.g. when you need to read open world input), but you will never do this on Codeforces.

      tl;dr version: std uses std::function only for std::thread (system API requires function type to be erased).

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I often use function<void(int)> dfs in competitive programming. It is very convenient if I want to modify local variables (such as vector<int> color, for example). If I want to do this using an auto lambda, I have to pass the lambda reference into itself, which I find ugly. Usually I prefer the std::function, because usually it's only negligibly slower (otherwise I'd not use it).

        That being said, I don't agree with your statement "it was created only for this, so you competitive guys don't ever need it, because it's not for you".

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          I've made the right recursive lambda example for you. "I have to pass the lambda reference into itself, which I find ugly" is just a mistake made by intuition and passing self is the right way to do the recursion.

          There are differences between language basics and C++ version is: you must provide compiler with as much information as possible (not to be confused with Java version: declare variables with interface types). This basic affects not only performance but also the ability of compiler to check your code and generate errors.

          Just look at this example:

          std::function<void()> lambda = [&] () { return lambda;  }; //OK!!!!
          
          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            To me seems that we talk about different things. You say that "passing self is the right way to do the recursion" while I only say about usability (maybe you mean something related to fixed point combinators in typed languages, but I can only guess). I may not understand completely what you mean by "the right way", but during the contest I will not waste time on using a longer and less convenient implementation, while I know another one just for my needs which works, no matter how passing the lambda into itself is "right".

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So you will prefer the implementation with the same code length that is twenty times slower, uses like three times more stack and contains much more potential errors am I right?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                What do you mean the same code length? I don't need your combinator class

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months ago, # ^ |
                  Rev. 2   Vote: I like it -10 Vote: I do not like it

                  Well ok I surely should not waste 1 more minute in the case I can not use prewrittens. This will surely never help me to avoid sudden TLs when the real std::function worst case happens, CPU branch prediction will fail and I will capture 5 references and overflow small object optimization so memory allocation and extra cache miss happen.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I get your point, but personally I have never encountered any problems connected with its slowness. Again, that's because when I need to write something that will work fast, I don't use std::function for that purposes (neither use I auto lambdas, I prefer ordinary functions).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months ago, # ^ |
                    Vote: I like it -10 Vote: I do not like it

                  Lambda body is an ordinary member function and lambda without capture is an ordinary function.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

std::basic_string is rarely used but it's super cool. I wrote a blog post about it some time ago. Also std::valarray for implementing Gaussian elimination.

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I don't know how is it called but there is something like anonymous function in g++, here is code using anonymous function as a check function inside if:

int l = 0, r = k;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (({
        // check function implementation with result in ok
        ok;
    })) {
        l = m;
    } else {
        r = m;
    }
}

The result of the last expression is the result of function itself.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using tuples to implement less operator in struct:

    struct day {
    	int p, a, i;
    	day(int p, int a, int i) : p(p), a(a), i(i) {}
    	bool operator < (day x) const {
    		return make_tuple(p, a, i) < make_tuple(x.p, x.a, x.i);
    	}
    };
    
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When we store -1 as uncalculated marker in our memoisation table, we can use ~ operator to check whether value calculated:

    int f(int x, int y) {
        if (~d[x][y]) return d[x][y];
        int &res = d[x][y];
        // do something with res
        return res;
    }
    
    memset(d, 255, sizeof d);
    f(n,m);
    
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you provide a full, compilable example? I'm very interested.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it
      int n = 100;
      vector<int> v(({
          int x = 0;
          for (int i = 1; i <= n; ++i) {
              x += i;
          }
          x;
      }));
      assert(static_cast<int>(v.size()) == n * (n + 1) / 2);
      

      It works on both gcc and clang.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Inlining comparator, usually you need comparator only once in sort function in your code:

    struct MyStr {
        int a, b, c;
    };
    
    vector<MyStr> v;
    
    // fill v
    
    sort(all(v), [](MyStr &a, MyStr &b) { return tie(a.a, a.b, a.c) < tie(b.a, b.b, b.c); });
    
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's actually called statement expressions. If someone is interested, more info is available here.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this is such a beautiful post and helpful also. Thank you :)

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Some time ago I didn't know about the last trick (finding the smallest element from three). I horribly bashed the problem 1283E. Here is my solution: https://codeforces.com/contest/1283/submission/71453985

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

it was helpful

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

mymap.count(key). Is awesome.... I didn't know so many of the tricks.. thanks for sharing . Awesome blog..

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it
template <class... Args>
void input(Args&&... args) { (cin >> ... >> args); }

int main() {
  int a, b;
  string s;
  input(a, b, s);
}

or as lambda:

auto input = [](auto&&... args) { (cin >> ... >> args); };
»
6 weeks ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it
  1. Instead of templates, we can use auto in arguments of functions. Something like auto f(auto x, auto y, auto z). Example; Assembly

  2. If function that returns pair or own struct, we can use auto [x,y,z] = f();. It can be used in cycles for too. Example

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    (1) is a C++20 feature. auto function parameters only work in GCC because it has experimental support for it.

    I don't think it is a good idea to use an experimental feature.

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

      Yes, it can be used in GCC compiler with version $$$\ge 6.1$$$. I think, that using experimental GCC features during a contest is a good idea if you are confident in them.

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

        dmkozyrev Can you please tell me. Why people use -

        Spoiler

        in main function. Why do we use this.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          It is effective way to make a local for main function (lambda function) and capture all local variables in main above its implementation.

          Example
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the nxt() function that you’ve mentioned has any cons? Like increasing the runtime or something? I personally like this style of writing, but I’ve refrained from using it to be safe.

Followup: Can we also define a readArray() to be used as vector<int> A = readArray()? I believe that the reading done in our function has to be copied to A, so an additional $$$O(n)$$$. (Or am I wrong? I’m not very clear about how returning a local vector works in memory point of view.)

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    std::vector got move assignment operator so it's fine, nothing will be copied in this case

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

      In statements like vector<int> A = readArray(); it does not matter (it is not assignment).

      BTW, I would redefine all(x) macro as begin(x), end(x) to sort arrays as well.

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Fair enough, but if you have a global array with MAXN elements, and you read the first n elements, then you probably don't want to sort the whole array, neither intentionally, nor accidentally, so I think that begin(x), end(x) is more a potential danger than a shortcut

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Blog. Very Helpful.