nor's blog

By nor, 3 weeks ago, In English

People often say C++ is much more cumbersome to write than any sane language should be, but I think that is mainly due to lack of knowledge about how to write modern C++ code. Here's how you can write code more smartly and succinctly in C++(20):

Negative indexing with end

Have you ever found yourself using a vector like a stack just because you have to also access the last few positions, or writing a sliding window code using a deque (where the size might be variable, but you want to access an element at some offset from the end)?

Chances are that you have written code like this:

while (stk.size() >= 3 && stk[stk.size() - 2] + stk[stk.size() - 1] > stk[stk.size() - 3]) {
  stk.pop_back();
}

A cleaner way of writing the same thing is this:

while (stk.size() >= 3 && end(stk)[-2] + end(stk)[-1] > end(stk)[-3]) {
  stk.pop_back();
}

This trick works not just for end, but for any iterator, provided that (roughly) there is no undefined behaviour like out of bounds accesses.

This can be done only with iterators which provide random access. For example, iterators for vectors but not for sets.

Free functions like len and str

Python's len and str come in handy a lot of times, and they're convenient to use because they're free functions (that is, not member functions).

Fortunately, C++ has its own set of free functions that are quite helpful:

  1. size(v): It returns the unsigned size of $$$v$$$, and does the same thing as v.size() That is, its numerical value is the size of $$$v$$$, and type is some unspecified unsigned type (aliased to size_t). This also works for arrays (but not raw pointers).
  2. ssize(v): It returns the signed size of $$$v$$$. This is quite useful, because it prevents bugs like a.size() - 1 on empty a. It doesn't have a member function analogue, though. This also works for arrays (but not raw pointers). If you use sz macros, you can safely remove them from your code!
  3. begin(v), end(v), rbegin(v), rend(v): They do the same thing as what their corresponding member functions do. These also work for arrays (but not raw pointers).
  4. empty(v): This checks if $$$v$$$ is empty or not. Analogous to v.empty()
  5. data(v): This returns a pointer to the block of data where it works.
  6. to_string(x): This returns the string representation of a datatype. They're only defined for things like int and double though.

Variable declaration in loops/conditions

If you have used range-based for loops, you might have noticed that there is no support for indexing by default. So people usually either just switch to index based loop, or do the following:

int i = -1;
for (auto x : a) {
  i++;
  // do something
}
// or
{
  int i = -1;
  for (auto x : a) {
    i++;
    // do something
  }
}

However, it either pollutes the parent scope with the variable i and makes things buggy, or just looks ugly. C++20 has the following feature that makes it cleaner:

for (int i = -1; auto x : a) {
  i++;
  // do something
}

Similarly, if there is an object such that you only have to inspect its properties just once and it becomes useless later on, you can construct it in the init part of the if condition, like this:

if (auto x = construct_object(); x.good() && !x.bad()) {
  // do something
}

Unpacking structs

A lot of people write code that looks like this:

std::vector<std::tuple<int, char, std::string>> a;
// populate a
for (int i = 0; i < (int)a.size(); ++i) {
  int x = std::get<0>(a[i]);
  char y = std::get<1>(a[i]);
  std::string z = std::get<2>(a[i]);
}
// or
for (auto& A : a) {
  int x = std::get<0>(A);
  char y = std::get<1>(A);
  std::string z = std::get<2>(A);
}
// or
for (auto& A : a) {
  int x; char y; std::string z;
  std::tie(x, y, z) = A;
}

A cleaner and more consistent way of writing this can be:

for (auto [x, y, z] : a) {
}
// or
for (auto& A : a) {
  auto [x, y, z] = A;
}

If you want references instead of copies stored in x, y, z, then you can do this:

for (auto& [x, y, z] : a) {
}
// or
for (auto& A : a) {
  auto& [x, y, z] = A;
}

Note that this is not limited to for loops, or even to just tuples, and you can use this sort of unpacking (structured binding) for most structs (in particular, custom structs you make, or std::pair). In fact, if you have std::array<int, 3>, then this unpacking will give you its contents in three different variables.

Some more utilities

There are some lesser known functionalities that C++20 introduced, like starts_with and ends_with on strings. Some of the more useful ones can be found here.

Notably, there is also support for binary searching like we do in competitive programming, and the relevant information can be found in the language specific section of this blog.

You can also print a number in binary, analogously to what you can do in Python. This can be done by constructing a bitset out of the integer and converting it to a string, or just by printing std::format("{:b}", a) (which is unfortunately not on CF yet).

emplace_back, emplace_front and emplace

Seriously, stop using a.push_back(make_pair(1, 2)) and a.push_back(make_tuple(1, 2, 3)) and even a.push_back({1, 2, 3}), and start using a.emplace_back(1, 2) instead.

The only reasonably common place this doesn't work is when you have a container that stores std::array, so emplace_back doesn't work; in that case a.push_back({1, 2, 3}) is fine.

The other variants: emplace_front and emplace do the same thing for their other counterparts (for example, in a deque, queue or priority_queue).

Lambdas

Lambdas in C++ are in fact cleaner and more intuitive (with more features) than in Python. Compared to both Python lambdas (being able to have more than 1 line of code) and local functions (having mutable states more intuitively and capturing parameters from an ancestor scope), in fact. This is because you can capture stuff more explicitly, have mutable state, can pass them as function objects, and even implement recursion using generic lambdas, though C++23 will have a feature called deducing this which will make a lot of things much simpler.

They can be passed around to almost all algorithms in the STL algorithms library, which is part of the reason why the STL is so powerful and generic.

They can also be used to make certain functions local, and avoid polluting the global namespace with function definitions. One more thing about them is that they are constexpr by default, which is not true for traditional functions.

Vector-like data structure without iterator invalidation

You probably know what we're coming to at this point: std::deque. It is essentially std::vector (without $$$O(1)$$$ move guarantees but whatever), but with no iterator invalidation on resizing/adding elements.

That is why it is ideal in a very important setting:

  • Making buffers of elements (so that we can use pointers to elements without worrying about what happens when the buffer is resized).

No more Python laughing in our face about having to worry about iterator invalidation!

Python style ranges and even more flexible range manipulation

Using temporary container in for loop

Suppose you want to do something for multiple arguments, but they aren't indices. Most people would either duplicate code, or do something like this:

vector<char> a{'L', 'R', 'D', 'U'};
for (auto x : a) { /* do something */ }

But this has a disadvantage: it needs more characters and also makes it more error-prone to use vectors. Instead of this, you can do this:

for (auto x : {'L', 'R', 'D', 'U'}) { /* do something */ }

or even

for (auto x : "LRDU"s) { /* do something */ }

Note that the s at the end makes it a string literal which is why it works, and const char* doesn't work because there is a \0 at the end of the literal. This can still allocate on the heap (not in this case, only for big strings due to SSO).

In case you explicitly want an allocation with a vector for some reason, you can use

for (auto x : std::vector{'L', 'R', 'D', 'U'})

or

for (auto x : std::vector<char>{'L', 'R', 'D', 'U'})
Ranges

C++20 has a feature called ranges, that allows you to do manipulations on, well, ranges.

Let's think about how to implement this: For integers between 1 to 5, multiply them by 2, and print the last 3 elements in reversed order.

#include <bits/stdc++.h>

int main() {
  std::vector<int> a{1, 2, 3, 4, 5};
  for (auto& x : a) x *= 2;
  for (int i = 0; i < 3; ++i) std::cout << a[(int)a.size() - i - 1] << '\n';
}

However, this is prone to having bugs (what about out of bounds errors in some other scenario?), and doesn't look intuitive at all.

Now consider this:

#include <bits/stdc++.h>

namespace R = std::ranges;
namespace V = std::ranges::views;

int main() {
    for (auto x : V::iota(1, 6) | V::transform([](int x) { return x * 2; }) | V::reverse | V::take(3))
        std::cout << x << '\n';
}

Here the intent is pretty clear. You take integers in $$$[1, 6)$$$, multiply them by 2, reverse them, and take the first 3. Now in this resulting range of numbers, you print each of them.

So let's see what happens here. The | operator is defined for ranges and an operation on ranges that returns a range. For example, V::transform(range, lambda) gives a range where every element is transformed, and doing range | V::transform(lambda) does the same thing. In fact, for a lot of cases, this isn't stored in memory at all (and operations are done while iterating on the fly), unless you have things like reversing a range.

One thing that you can finally do is split a string with delimiters in a nice way (which used to be a major point of ridicule directed towards C++ from a lot of Python users). This is as simple as using a split view in the ranges library. For more information, see this. Here's an example taken verbatim from the cppreference page:

#include <iomanip>
#include <iostream>
#include <ranges>
#include <string_view>
 
int main() {
    constexpr std::string_view words{"Hello^_^C++^_^20^_^!"};
    constexpr std::string_view delim{"^_^"};
    for (const auto word : std::views::split(words, delim))
        std::cout << std::quoted(std::string_view{word.begin(), word.end()}) << ' ';
}

A more common example can be like this:

#include <bits/stdc++.h>

namespace R = std::ranges;
namespace V = std::ranges::views;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::string s(1000000, '0');
    for (int i = 0; i < 1000000 / 2; ++i) s[i * 2] = '1';
    for (const auto word : V::split(s, '1'))
        std::cout << std::string_view{begin(word), end(word)} << ' ';
}

Some ranges functionality is as follows:

  • converting to and from a range: conversion to a range is implicit for most STL containers. If r is a range, then for most STL containers, like std::vector, you can do something like std::vector<int> a(r.begin(), r.end()). C++23 has a feature R::to<ContainerType>(range) that will construct a container out of a range, and you could even do range | R::to<ContainerType>().
  • iota: This works similarly to Python's range() but without the stride.
  • reverse: This works similarly to Python's reversed()
  • take: This takes the first $$$n$$$ elements of a range (unless you run out of elements by then)
  • drop: This takes everything but the first $$$n$$$ elements of a range (unless you run out of elements by then)
  • counted: This takes $$$n$$$ elements of a range starting from an iterator.
  • keys, values: keys takes a range whose elements are pair-like and returns a range of their first elements (so if we have (key, value) pairs, it will return keys), similar to .keys() in Python. Similarly, values returns a range of the values.
  • elements: if we have a range of tuple-like elements, this takes the $$$n$$$-th members of each of these tuples (where $$$N$$$ is a compile-time constant).
  • all: though type conversions from containers to ranges are usually implicit, it takes a container and takes everything in that container.
  • Some upcoming C++23 features that will make it even more convenient to use ranges: to, zip, slide, stride, repeat, adjacent, pairwise, cartesian_product.

Note that this is not the only thing you can do with ranges. In fact, with almost all possible algorithms that you can find in the algorithms library that use a begin and an end iterator (like std::sort or std::partial_sum or std::all_of), you can find a ranges version here, where you can just pass the range/container name instead of the begin and end iterators you usually pass.

By the way, if you don't want to wait for C++23, you can use some of the functionality from this code, which I used to use a couple of years ago when C++20 was not a thing.

Spoiler

Finally, I'd like to thank ToxicPie9, meooow and magnus.hegdahl for discussing certain contents of this blog, and other members of the AC server for giving their inputs too.

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

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

Thanks this is very useful.

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

Cool stuff. But don't use deque, it's slow.

I always use hull.end()[-2] in convex hull implementation. It's surprising that end(hull) works too.

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

    For most purposes, using a deque is almost as fast as a vector according to some of my submissions.

    There are only two issues that I know of that anything using a deque can face:

    1. When you need to rely on the cache a lot: even though allocations are done in blocks to avoid this problem, in some extreme cases it might lead to some noticeable slowdown (about 10-30%). This might be an issue with vectorization in the future, but usual block sizes are large enough to avoid this issue to a large extent. Usually online judges don't have very tight limits that are able to differentiate between vector and deques in this scenario.
    2. Allocating too many deques: If you do something like vector<deque<int>> a((int)1e6);, it is going to MLE (and if not MLE, TLE) because a deque allocates memory in chunks, and that chunk tends to be large. For example, using GCC on codeforces, it is 512 bytes, and it is quite bad to allocate a vector of $$$10^6$$$ empty deques in this case.

    I think the second part is the reason behind the comment that deques are slow, but feel free to correct me if this issue showed up in some other context.

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

    Some python people avoid using deque for their BFS by doing something like:

            q = [src]
            seen = [0] * N
            seen[src] = 1
            for u in q:
                for v in graph[u]:
                    if not seen[v]:
                        q.append(v)
                        seen[v] = 1
    

    which translates to the following in c++:

            vector<int> q = {src};
            vector<int> seen(N, 0);
            seen[src] = 1;
            for (int i = 0; i < q.size(); i++) {
                int u = q[i];
                for (int v : graph[u]) {
                    if (!seen[v]) {
                        q.push_back(v);
                        seen[v] = 1;
                    }
                }
            }
    
    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it -16 Vote: I do not like it

      I avoid using deque for my BFS by using something like this.

      Warning - long code

      You can either use it like a normal std::queue, or plug it right into a range-based for loop. It's kinda crude, but it works

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

It is worth noting that and and or are actual keywords on C++ since C++98 or so. Also for BFS I like to use something like this. (probably meaningless rant: why do the container adapters not have emplace? this makes things a bit inconvenient compared to things that we have emplace for.)

int a,b;
queue<pair<int,int>>Q;
//push something...
while(!Q.empty()&&(tie(a,b)=Q.front(),Q.pop(),1))
{
  //do something...
}
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible to declare a,b under while?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it
      for (int a, b; !Q.empty() && (tie(a, b) = Q.front(), Q.pop(), true);) {
        // do something
      }
      
»
3 weeks ago, # |
  Vote: I like it +76 Vote: I do not like it

Hot take: You generally don't need std::pair, and you never need std::tuple. Typically, they are just std::array<T, 2> or std::array<T, 3> expressed in a verbose way. std::pair can be useful if you need to store different types or do stuff with std::map. If you want to pack more than 2 fields in a different type, you need to define structs for basic readability.

(I learned this style from Snow-Flower's code, I think it makes sense and made my code cleaner, but I'm interested to hear any downside of this approach)

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

    I agree with this, and it is definitely not a hot take in my opinion. In fact, in some competitive scenarios I've observed that using std::array helps with vectorization as well and std::pair and std::tuple have surprising inherent overheads compared to a toned down implementation like template <class T, class U> struct Pair { T first; U second; }; (so much so that some software companies ban their use in their codebases). I would recommend watching this for a good introduction to why this is the case. EDIT: just watched it again, and it seems an important reason in the competitive programming context wasn't covered. std::pair and std::tuple are not forced to be trivial types even if their members are, so this adds some non-zero overhead sometimes. Similarly, sometimes compilers aren't able to reason through all the abstraction that is provided by the suboptimal std::pair and std::tuple implementations, so that factors in sometimes too.

    However, I have seen way too many people spamming std::pair and std::tuple everywhere, and it is quite annoying to look at (even more so to write) push_back(make_pair(...)) all the time. The main idea is that if you use std::tuple, you should at least make your code not-so-ugly.

    There are still examples where you might need std::tuple: one reason to not completely abandon it in favor of simple structs is that you can't use ranges::elements_view with structs having different types, because std::get is defined only for them (and std::array and std::pair). Perhaps this can be fixed with better "accessing" functionality for structs, but I don't see how to do this.

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

    How to use std::array if you want elements to be not of the same type?

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

      You don't. (I'm not saying you "definitely can't", but you would not appreciate finding out how)

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

        It's not hard, you could use std::array<std::variant<T1, T2>, 2> (though this should not be used by any sane person who cares about performance).

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

    How do you implement a scanline then? You usually have two types of events (something started and something ended) and you need to sort events firstly by the $$$x$$$ coordinate and then by the type. A tuple of $$$x$$$, type and parameters (usually tuple<int, bool, int>) does perfectly fine from my perspective. Do you define a structure with a custom comparator here as well?

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

      I just use std::array<int, 3> for this case. In my opinion std::tuple is fine for quick and dirty operations (like sorting and so on) in cases where the data types aren't convertible or take too much memory, but for more complicated code (such as when you want to store some history on a stack and do divide and conquer on it, or even just DSU with rollbacks), I try to make things more readable and debuggable by making a different struct. As a rule of thumb, I keep my library implementations clean with meaningful variable names. Of course, your mileage may vary.

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

        But this is not very clean even in comparison to the tuple approach. The second part is semantically bool (or even some enum, but you got the point). Also, what if points are in a floating-point type? array<double, 3>? I doubt any sane person would use double as a substitute for bool. Also, the parameters are not of the same type as $$$x$$$ quite often.

        Besides that, I even think that always substituting tuple<int, int, int> with array<int, 3> is a bad idea. They are semantically different. The tuple means just the collection of three entities and the array means the collection of three entities of the same type. Just because three types happen to be the same it does not mean they are obliged to be the same.

        And even defining a separate structure is not always the best solution, because it takes off some transparency of what is happening. For example, if I had to choose between a structure with fields $$$x, y, z$$$ that should mimic the tuple behaviour and an actual tuple, I would have prefer the latter. Obviously, here we all should forget for a second that in C++ specifically you have to write ugly get<2>(tuple) to access the third element, but in other a bit more modern languages it is usually done as tuple.2 and I fail to see much of a difference from not_tuple.z. Not to mention that structured bindings to your own custom types sometimes work not in the most trivial way.

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

          About how morally incorrect using std::array is, I agree. It's just that std::array is easier to type and access. I definitely won't use this kind of a thing in "real-world" code, but I think it is convenient for competitive programming.

          Regarding custom structs, I think I still have reservations about choosing std::tuple over them. For instance, if I had to write an implementation of some flow algorithm, I personally won't store the edge as a tuple (a couple of integers to maintain vertex/edge indices, and a couple of flow variables). I don't deny that they're very interoperable, and that they make a lot of sense when you are (only) thinking about what the data does. I think it's a matter of personal preference, though.

          I didn't get your point about structured bindings not working in the most trivial way, could you elaborate? I almost always use a struct and bind variables in the order of declaration in the struct, is there any place where this fails?

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

            Using structures for edges in graphs/flows are perfectly fine, I actually think that it is more correct way of doing it. But the difference is that here field names are usually .to, .from and .capacity, i.e. they are meaningful. My example was about the exactly opposite case.

            I spent about 90 minutes trying to remember what was happening when I decided to be extra cautious with structured binding and, apparently, the point was that binding a tuple-like type and binding to data members are slightly different and you can accidentally switch from one to another. I have no clue how I did that (maybe by inheriting something?), and I failed to recreate an example.

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

      I rarely use bool whenever I can use int, so I don't have such use cases. If you want some symantical restriction, I think it's better to go with structs. In case of floating points — yes, sometimes that happen. I will define custom structs.

      Everything here are inherently hacky. If you want industry-style code, you have to not use anything except structs.

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

        I believe that even in industry-style code there are places for tuples, especially in public APIs (see examples above). In particular, STL functions love having pairs in their return types, tuples are not any worse. The reason why they are uncommon in STL is that there was no std::tuple until C++11. Another reason, obviously, is that functions that return more than two variables are uncommon in general, but it does not mean their existence inherently means bad design.

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

    How do you code Dijkstra?

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

Thanks! this is useful blog. can anyone tell me where I can download c++20 ?

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

    You should have it if your compiler is up-to-date. Make sure you don't have compiler arguments setting you to an older version (use -stdc++=20 on GCC/Clang, and /std:c++20 or /std:c++latest on MSVC).

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

These C++ code is too erotic.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Don't forget there's also reverse iterator so you can also use rbegin(a)[0] to access the last element.

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

    That's true (and it makes more sense too)! However I almost always use end(a)[-1] instead of rbegin(a)[0] because:

    1. It keeps things consistent across languages — Python and C++.
    2. It has fewer characters.
    3. I avoid using reverse iterators too much, since sometimes you can mess up by using ++ instead of -- and vice versa if you mix iterators.
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the last element please use .back(), .front() also exist for accessing the first element but [0] is shorter anyway.

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Is the AC server a discord server? If so could I get an invite ...

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

It is risky to use deque. Last time someone used 10^6 deques in NOI in China, and got MLE.

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

    Why? I think it's just a double-ended linked list

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

      You can refer to this. It explains in detail why using many deques can cause MLE.