MikeMirzayanov's blog

C++20 Is Released
By MikeMirzayanov, 3 years ago, In English

Hello, Codeforces.

Please, welcome c++20 support on Codeforces. Yes, it is 64-bit. Thanks to Brecht Sanders: I used his distribution GCC-11.2.0-64 from https://winlibs.com/.

If you have installed PBOX, you can add this compiler with the line pbox install gcc11-64-winlibs. Probably, a good idea is to add C:\Programs\gcc11-64-winlibs\bin into the PATH. More about PBOX you can read here.

I use the compilation command line similar to other GCC installations: g++ -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++20 <source>. The only differences are -std=c++20 and -Wall -Wextra -Wconversion (I plan to use somehow such warnings in Polygon to suggest fixes in uploaded files).

Now you can use c++20 in your solutions. I'm not sure there are many features useful in competitive programming. Probably, I'm wrong. For example, now you can write vector v{vector{1, 2}}; instead of vector<vector<int>> v{vector<int>{1, 2}};. What else is useful? Please, if you are good with modern C++ then write.

You might be interested in looking at such a table. Before implementation, I always test every C++ distribution for the efficiency of reading and writing large amounts of data. For example, the latest GCC compiler from MSYS2 is terribly slow in some cases. I don't want to use it here. Also, it happens that some specifiers like lld or Lf work unexpectedly. In the table by reference, the second line is the added compiler. The columns correspond to different tests. The cell contains the time of the test execution. If I have time, I will someday publish scripts for testing c++ compiler installations.

Bye for now,
— Mike

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

Comments Comments (67)
| Write comment?
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Wow, yesterday I've just said this, and today I meet the release of GCC 11! That's great!!! Yay!!!

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

What is the advantages?

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Wow, latest gcc and c++20 support! Can't wait to try ;)

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Seems like C++20 doesn’t introduce a lot for CP. Most useful probably are 3-way comparison shorthand and easier struct initialization.

→ Reply
»
3 years ago, # |
  Vote: I like it +71 Vote: I do not like it

Funnily enough, you can't actually write vector v{vector{1, 2}}; instead of what you said, it's equivalent to vector<int> v{vector{1, 2}}; which is the same as vector{1, 2}

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

I'm not sure there are many features useful in competitive programming

std::midpoint for example. Now your binary search implementation will never overflow

  auto a = numeric_limits<int32_t>::min();
  auto b = numeric_limits<int32_t>::max();
  cout << midpoint(a, b) << '\n';

Oh, also there are a lot of bit manipulation functions. std::has_single_bit — whether x is power of 2, std::popcount — you know what, etc.

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

    Is binary search overflow actually an issue? The sum of lo+hi would have to be greater than int max which I'm not sure if occurs in CP problems. Also if you knew to use midpoint, then you could just rewrite the binary search to not overflow.

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

      Last spring or summer, during some workshop, we had this exact bug in our code. On the other hand, it was the only time in my experience when this mattered

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

    Or, you can also learn to use long long

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

Wow!!!That's great!!!

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

what is the function of operator <=> ? the operator can use for two values that can compare but < or == or > is return true. I can't think any uses of it.

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

    It is more useful for implementing custom types. If you implement <=>, the compiler will generate <, >, <= and >=.

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

i love codeforces be cause it is always up to date thanks mike for this update

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

1 min silence for those who still uses C++ 14

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

That's really good!

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

Does anyone know if ranges is good for competitive programming?

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it +403 Vote: I do not like it

Thanks for the update to C++20!

Since it was asked in the post, here are some C++20 features I feel would be useful (and some making stuff merely easier to look at or type) in competitive programming in C++:

  1. Finally casting from unsigned to signed variables is defined. Contrary to popular belief, this has not always been the case (it has been implementation-defined behaviour for casting elements >= INT_MAX), and one important issue is that it might affect some implementations of custom hashes. This is because C++20 finally enforces signed integers to be represented in twos-complement.
  2. Formatted printing: You could do it using printf, but printf has severely limited functionality (more importantly, it doesn't deduce types and it doesn't work for user-defined types either). Using std::format, you can get Python-like printing, saving the formatted string to a buffer and so on.
  3. The <bit> header for bit-related operations, which eliminates most of the need for using the __builtin_* family of functions, and gives some more useful things like has_single_bit, bit_ceil, bit_floor.
  4. T::contains for T = std::map, std::set and family, which avoids pitfalls like using T::count for T = multiset.
  5. std::midpoint that will finally prevent any overflow/underflow in binary search. A related function is std::lerp which does linear interpolation between two values while minimizing errors.
  6. More attribute support for constant factor time and memory optimization.
  7. std::ranges library would help you do something like sort a vector like you would do in Python, and avoid using iterators (iterators are super-handy, but writing both iterators doesn't make sense if they're going to be begin() and end() anyway). There are quite a few use-cases of std::ranges that might help make code more concise and expressive.
  8. More stuff in the standard library/language is constexpr: If you like metaprogramming as much as (or more than) I do, this is probably the most exciting feature. Now that new is constexpr, it'll make life much easier to cheese problems by computing stuff at compile time, and you won't need to write your own constexpr allocators and stuff. This also means std::vector and std::string are constexpr, which will ease metaprogramming quite a bit too (even though there are a few limitations while using them in a constexpr context).
  9. Designated initializers: Now you can assign member variables values by name (and perhaps skip some of them if they're to be initialized as if they're initialized by an empty list. As pointed out below, the order needs to be the same as declaration order. If you're memory optimizing by changing your struct layout by moving around a member variable, you won't need to change all your struct declarations everywhere, if you only ever default initialize that variable (i.e., don't mention it anywhere in the initialization).
  10. Modules: This is not useful for competitive programming, but definitely, it looks much better IMO.
  11. Concepts: This takes a nice Rust-like (and sort of Haskell-like) approach to defining the behaviour of types in a nicer manner. No more tons of std::enable_ifs and use of SFINAE.
  12. 3-way comparison and default operator==: The first thing gets rid of having to declare multiple operators for the same order, and the second one eliminates the pesky compilation errors you get when you check for struct equality.
  13. auto parameters of functions: This is officially called abbreviated function templates (because type deduction for auto is equivalent to that for templates). Remember auto return types in C++17? You can even do something like auto add(auto x, auto y) { return x + y; } or something like this now, rather than having to write out long templates.
  14. std::ssize: Gives the signed size of a container. No more underflow errors while iterating with T::size if you replace it with T::ssize (and no more need to do typecasts either). This can also be used as ssize(container).
  15. std::span: Something analogous to std::string_view but for general types (and contiguously stored elements). Might not be useful that much in competitive programming, but this has a nice interface with std::ranges.
  16. Named constants in <numbers>: No more need to use acosl(-1.0) for pi, or exp(1) for e. They're defined (with many more constants) in this header.
  17. starts_with and ends_with: This makes prefix/suffix string matching simpler (better and faster than extracting a substring and checking for equality).
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    coroutine also looks interesting and seems to enable writing python-style generators with yield statements.

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

    init in foreach (like in c++17 if)

    for(int i=0; int x : vec)

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

      Something like

      int n; cin >> n;
vector<pair<int, int>> a(n);
for(int i = 0; auto& [x, y]: a)
    cin >> x, y = i++;

ranges::sort(a);
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    (it has been undefined behaviour for casting elements >= INT_MAX)

    I believe it was implementation-defined, not undefined, wasn't it?

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

      Yeah, I somehow swapped that out mentally while writing that out. I'll edit that in, thanks a ton for the correction!

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

    It seems that designated initializers do not allow reordering (source) and work only for normal structs aka aggregates which std::pair is not.

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

      Thanks for the correction! I had misremembered, and the correct thing that designated initializers allow that a normal aggregate initialization doesn't seem to allow is that you're allowed to skip out some variables in the initialization, and not reorder them. Fixed it now (hopefully).

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

    The fact that std::set didn't come with contains until now and I had to use find or count instead is mind-boggling to me. You would think the one operation a container modelling a mathematical set would have is checking set containment!

    https://en.cppreference.com/w/cpp/container/set/contains

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

I have done submit 132081784 and it had RE on first test. But when I have submitted same code 132085792 C++17 it got AC. So, it was because I have used non-standart allocator, without it, my code still works. I think that isn't right and I don't know how to fix it.

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

    It's looks like everything works if you remove "inline" from operators overload, but I'm not ready to guarantee it in general case :)

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -31 Vote: I do not like it

Did you add it specially before first Technocup qualification contest?)

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +47 Vote: I do not like it

When you have comparator function
auto cmp = [](const T&, const T&) -> bool { ... };,
you can now write
set<T, decltype(cmp)> s; instead of set<T, decltype(cmp)> s(cmp);

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

recently two of my solutions timed out/MLEd in C++ 17 64-bit but passed with a comfortable margin in C++17. Can anyone explain why is that the case? The difference was 100 MB for the MLE and ~0.2 sec for the TLE.

So why is 64 bit sometimes badder?

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

    There might be many reasons for that: generally speaking, 64 bit arithmetic is slower for obvious reasons (and was much slower in the past because processors were designed to handle 32 bits efficiently but it's not as problematic now), the memory allocations are larger, cache will have higher miss rate (objects are simply bigger), and so on.

    The performance depends on many factors and it might not be easy to predict: sometimes the 64 bit programs will realize variables only use 32 bits of space and downgrade some operations, sometimes 32 bit programs can pack two ops into 64 bits which is not possible when compiled with 64 bits and so on. The idea here is thar there are numerous compiler optimizations and it's virtually impossible to predict all the effects of these optimizations for a given program in advance even for very experienced compiler engineers. Finally, it depends on the processor a lot.

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

(I plan to use somehow such warnings in Polygon to suggest fixes in uploaded files)

This looks like a great idea! I would suggest to also include -Wshadow (mentioned here). At least for me, this is one of the most useful warnings.

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

    I've seen some holy wars on -Wshadow because of constructors, e.g.:

    struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
}
    → Reply
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Nice I need to keep switching between 4 versions xD

Codeforces - 20
Atcoder - 17
Codechef - 14
Topcoder - 11
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

Btw, MikeMirzayanov, would you please consider adding Clang not just for diagnostics?

  • Many enterprises have already made the switch to it, especially big tech companies such as Google and Apple, so there are a lot of C/C++ coders who use it as the primary compiler, along with the rest of the LLVM ecosystem.
  • It receives more attention from compiler engineering people, because its internals are much better organized compared to GCC, and also because it has more corporate-friendly license, allowing hardware companies such as Intel and AMD to maintain their own downstream versions and contribute hardware-specific optimizations.
  • For this reason, LLVM is becoming the default in compiler engineering courses in universities and preferred in other programming courses (not in Russia though, but I believe most US universities have already switched).
  • In my experience, it frequently beats GCC in terms of performance for algorithmic programming.

I'm working on a book about performance engineering with a lot of compiler-specific C/C++ examples, and the only reason I haven't ditched GCC for Clang/LLVM is that it isn't widely available in the competitive programming environment. Adding it to CodeForces will greatly catalyze the change.

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

    One small downside to using clang is that you won't have __gnu_pbds for order statistics tree.

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

      Not really. GNU C++'s "Policy-Based Data Structures" is just a library, meaning there is a bunch of C++ headers in the system when GNU C++ toolchain is installed. They can be included with Clang just like any other header/library.

      Moreover, using Clang does not imply or require using libc++. By default, Clang will use libstdc++ on Linux unless told otherwise.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it
  • What else is useful?

You can now not implement a binary search for problems with binary search over a function f, if for whatever reason you don't want to do it, like so:

namespace r = std::ranges;
namespace v = std::views;
auto rng = v::iota(min,max+1) | v::transform([f](auto a) {return make_pair(f(a),a);});
auto it = r::lower_bound(rng,make_pair(true,min));

edit: this can also be reduced to this:

auto it = r::lower_bound(v::iota(min,max+1),true,{},f);
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You need partition_point, not lower_bound

    → Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it 
for (auto i : views::iota(0, n))
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    You can almost make it look like python now:

    const auto &range = views::iota;
const auto &reversed = views::reverse;
auto print = [](const auto &seq) {
  ranges::copy(seq, ostream_iterator<int>(cout, " "));
  cout << '\n';
};

int N = 10;
print(range(0, N));
print(reversed(range(0, N)));
    → Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Thanks for this!

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Please, add common lisp

→ Reply
»
3 years ago, # |
  Vote: I like it +80 Vote: I do not like it

It is very convenient to use projection functions when sorting structures. For example sorting edges by weight:

struct edge{ int v, u, w; };
vector<edge> e;
//input
ranges::sort(e, {}, &edge::w);
→ Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

How about -Wshadow? Is it included in those?

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

When will release C++20 32-bit?

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

    Is there a specific reason behind asking for a 32-bit version? The 64-bit version is almost always faster than the 32-bit version, so I'm just curious about some use-case that's not so rare but makes 32-bit strictly necessary.

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

      Pointers take two times less space. May result in better ML fit (especially for pointer-heavy data structures like self-balancing trees) and better cache fit, hence faster execution.

      → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It seems that we can use chinese characters as variable names,is it?

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

my code in c++20 gives me TLE.

whereas the same code in c++17 gets accepted in 140ms.

can someone please tell the reason behind this.

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

    Compiling your code with -fsanitize=undefined -fsanitize=address options and running it with the first testcase input data results in the following error: test.cpp:28:5: runtime error: execution reached the end of a value-returning function without returning a value

    Your pre() function needs to return void instead of int. Fixing this source of undefined behaviour makes your solution run fine at least in https://codeforces.net/problemset/customtest

    → Reply
»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

I have different answers too

problem: https://codeforces.net/contest/459/submission/193205657

TLE 17 using GNU C++ 20 64: https://codeforces.net/contest/459/submission/193205461 ACC using GNU C++ 14 : https://codeforces.net/contest/459/submission/193205657

can anyone explain why?

→ Reply