Micro- and macro-management for your next cpp source: General tips'n'tricks

Правка en12, от viskonsin, 2020-06-28 14:52:11

Hello, Codeforces!

In this series of articles, I would like to tell you about tips'n'tricks I use in C++ sources. Some of them require a strong C++ background, some not, but all of them are aimed to reduce the time you spend on basic things like reading input/debugging/etc, so it might be useful for your next template.

This part is dedicated to some basic tips (and probably should've been the first part but it's not ¯\_(ツ)_/¯).

bits/stdc++.h

Just add this header to your source file and you won't have to add any other STL headers. Probably the only reason why you still haven't done it (if you haven't) is that it might not work on your machine: that happens because bits/stdc++.h is a feature of GCC, not the entire cpp standard. However, there're a few ways to work around it.

How to fix bits/stdc++.h if it's not working

Content

Well, before we start putting stdc++.h to the proper location, there's one thing to determine: content to put in it. You either can determine what default headers you might need, or just google "gcc bits/stdc++.h source" and copy/paste it [if you've decided to do so, you might need to remove some gcc-specific headers: just try to compile it and remove one by one non-compiling includes].

Option 1: Add it to default location

Well, the easiest one is to find one of the include paths, like /usr/local/include (might add to /usr/include, but it's system directory, do it on your own risk) on Mac, or somewhere else for Windows. All you need to do after this is to create folder bits and file stdc++.h inside it.

Option 2: Add to user-defined header search paths

If you compile/run you code manually, there's the option to add proper location as compiler flag isystem directly:

$ g++ -std=c++2077 a.cpp -o run_a -isystem /path/to/your/custom/includes

Note that inside the folder /path/to/your/custom/includes must be the folder bits with file stdc++.h.

Option 3: Add to you build system

If you're using CMake based build system (what CLion actually does), then you could edit your CMakeLists.txt directly:

include_subdirectory(/path/to/your/custom/includes)

Prewritten code

According to CodeForces' official rules, you might use some prewritten code. But it might be annoying to search over your sources to find the code you need. Well, you could put in a separate file like z.hpp with all content you might need to use on a contest and simply include it to use all functionality you need without rewriting it.

For example with this file you could write smth like:

#include <bits/stdc++.h>
#include <z.hpp>

using namespace std;

constexpr int mod = 1000 * 1000 * 1000 + 7;
using Mint = Z<mod>;

template <class T>
T bin_pow(T base, int64_t exponent) {
  if (exponent == 0) return T(1);
  if (exponent % 2 == 1)
    return base * bin_pow(base * base, exponent / 2);
  return bin_pow(base * base, exponent / 2);
}

int main() {
  Mint a, b;
  cin >> a >> b;

  // note that following addition performed by modulo
  cout << a + b << '\n';

  // note even pure bin_pow uses modular arithmetics
  cout << bin_pow(a, b) << '\n';
}

Don't forget to copy/paste actual source (if you need those) to your file before submitting: there's no z.hpp accessible by codeforces's compiler. It may be enhanced by custom script doing it instead of you, but there's no such script yet.

stdin, stdout, stderr

Your program is using at least three streams to communicate with OS: stdin for input, stdout for output, and stderr for errors. Moreover, by default, there's sync for cin and cout which may slow down your solution on huge inputs. You could discover more here. If you don't like ios::sync_with_stdio(false) appearing in main every time, you could use the following trick: if you need some side effects to happen even before main starts, you can do it when global variables instantiate:

int main() {
  // some code
}

// empty namespace to not conflict with any other possible names
namespace {

// global variable is assigned to the result of calling the newly created lambda function.
// Since your variable cannot be void, put `int` as a result:
auto fast_io = [] {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  return 0;
}();

}  // namespace

Since any checker/grader reads only stdout, I strongly recommend using stderr for debug information (cerr instead of cout) — that way once you find a bug and solve it, you won't need to remove all the debugging stuff before submitting. However, if you output to stderr a lot, it can affect the performance.

Use some tooling

Since you're writing some code and test it against a few test cases it may be annoying to write all of them on your own every time you run the program. To get rid of copypasting them from a webpage, or trying to copy with spaces from pdf, you could've put it into files at once and get input from these files. There's an amazing tool from xalanq that does it for you. It ignores all your debug output while checking, but still prints it above testing verdicts.

Run debug code only in debug mode

You may need to run some extra code for debugging purposes only. For example, print graph, perform additional checks, or compare with the naive solution. It may affect resulting performance and put you from AC zone to TL one.

There's the straightforward solution: use #ifdef preprocessor directive:

int main() {
  int a, b;
  cin >> a >> b;
#ifdef DEBUG
  cerr << "a = " << a << " b = " << b << '\n'
#endif // DEBUG
  cout << a + b << '\n';

To run this code in debug-mode, you need to pass -DDEBUG or -D DEBUG option to your compiler. If you don't know how to do it, or simply don't wanna to do it, codeforces defines ONLINE_JUDGE for you:

int main() {
  int a, b;
  cin >> a >> b;
#ifndef ONLINE_JUDGE
  cerr << "a = " << a << " b = " << b << '\n'
#endif // ONLINE_JUDGE
  cout << a + b << '\n';

Plenty of code just to output two variables, isn't it? Let's solve two problems:

  • print all variables given to function (macro)
  • write code (block, or just function) that runs in debug mode and event doesn't evaluate arguments in release mode

Printing all variables

Ok, let's provide macro LOG(x, y, z) that works like cerr << "x = " << x << " y = " << y << " z = " << z << "\n", but works with plenty of arguments. Since we can't take x as string from function argument, let's start from simple scratch:

#define LOG(...)  cerr << "[ "#__VA_ARGS__" ] = "; log(__VA_ARGS__);

Where log function prints all arguments given to it. You could start from scratch like mentioned in my previous article:

template <class ...Args>
auto &log(const Args &...args) {
  return ((cerr << " " << as), ...) << '\n';
}

Let's put it all together:

template <class ...Args>
auto &log(const Args &...args) {
  return ((cerr << " " << as), ...) << '\n';
}

#define LOG(...)  cerr << "[ "#__VA_ARGS__" ] = "; log(__VA_ARGS__);

int main() {
  int a, b;
  cin >> a >> b;

  LOG(a, b, a + b);
  // prints: [ a, b, a + b ] = 2 2 4

  cout << a + b << '\n';
}

Well, there are plenty of things you could've improved, as mentioned in this discussion. However, it still doesn't work fine for things with comma in subexpressions like:

LOG(a, b, some_func(a, b))

Running code in debug mode only

How to run code in debug and don't evaluate arguments in release mode? Well, here's a trick you might have seen here involving if:

#ifndef DEBUG

#define CERR if (false) cerr

#endif

// somewhere in code

CERR << "a = " << a << '\n';

// expands to

if (false) cerr <<  << "a = " << a << '\n';

But there's bug here:

if (a == 0)
  CERR << "b=" << b << '\n';
else {
  CERR << "c=" << c << '\n';
  // dance like no one's watching
  // with a != 0
}

// expands to

if (a == 0)
  if (false)
    cerr << "b=" << b << '\n';
  else {
    if (false)
      cerr << "c=" << c << '\n';
    // a is still zero here :(
  }

Well, there's an alternative with while (false) which doesn't have such bugs. But what to do instead of while (false) to run any code? We may try to put nothing [don't know if there's bug], but I'd prefer one time running for. Let's put it all together:

template <class ...Args>
auto &log(const Args &...args) 
{ return ((cerr << " " << as), ...) << '\n'; }

#ifdef DEBUG
#  define LOG(...)  cerr << "[ "#__VA_ARGS__" ] = "; log(__VA_ARGS__)
#  define RUN       for (bool _flag = true; _flag; _flag = !_flag)
#else  // DEBUG
#  define LOG(...)  while (false) cerr
#  define RUN       while (false)
#endif // DEBUG

int main() {
  int n, m;
  cin >> n >> m;

  LOG(n, m);
  
  vector<vector<int>> g(n);
  for (int e = 0; e < m; ++e) {
    int u, v;
    cin >> u >> v;

    g[--u].push_back(--v);
    g[v].push_back(u);
  }
   
  RUN {
    for (int u = 0; u < n; ++i) {
      cerr << u << ":";
      for (int v : g[u]) 
        cerr << " " << v;
      cerr << "\n";
    }
  }
}

auto

There's the keyword to replace all boring types you don't need to write explicitly:

for (auto it = xs.begin(); it != xs.end(); ++it)
for (auto foo : foos)

But there's a hidden problem: unnecessary copying:

for (auto row : table) {
  // here row has type vector<Cell> 
  // which copied from table even if you don't modify it
}

To avoid it, you could've used:

for (auto &row : table)

But, it might be a temporary object, that's kind of annoying. To resolve it, you could've used universal reference everywhere:

// works just fine: no copies, 
//   reference if regular object
//   value if temporary one
for (auto &&row : table)

Ok, where to use it?

Predicates

If you're using lambdas, you might st not know about generic lambdas, let me show the use case:

vector<pair<int, int>> some_events = ...;
sort(some_events.begin(), some_events.end(), [&](auto &&lhs, auto &&rhs) {
  // compare two pair<int, int> here
});

You might notice that you often write code like return foo(lhs) < foo(rhs);. Here's way to get rid of it:

#define BY_FUNC(func) [&](auto &&lhs, auto &&rhs) { \
  return func(lhs) < func(rhs);                     \
}

sort(some_events.begin(), some_events.end(), BY_FUNC(some_func));

Much better (you can also come up with a shorter name for macro), but if you want to compare only .second, it's not suitable :(. However, we could generate all necessary code on our own (thanks to viskonsin for pitching me this idea):

#define BY(...) [&](auto &&lhs, auto &&rhs) { \
  auto predicate = [&](auto &&x) {               \
    return __VA_ARGS__;                          \
  };                                             \
  return predicate(lhs) < predicate(rhs);        \
}

sort(pairs.begin(), pairs.end(), BY(x.second));

// expands to:

sort(pairs.begin(), pairs.end(), [&](auto &&lhs, auto &&rhs) {
  auto predicate = [&](auto &&x) {
    return x.second;
  };
  return predicate(lhs) < predicate(rhs);
});

// such a plenty of code out of one short macro!

dbg macro

Thanks to ramchandra for his amazing dbg macro, really nice job. However, there's dbg! macro in Rust. Let's develop the same behavior: after expression is surrounded with dbg(expr) work as simple expr in release mode and additionally prints it in debug mode. Well, implementation for release mode is pretty straightforward:

#define dbg(...) __VA_ARGS__

And what with debug one? I'd like to work with any kind of references here, to write smth like:

auto it = dbg(order).find(dbg(x + 1));

Okay, it must be a result of expression with necessary debug output. Let's use simple lambda on fly:

int recursion_depth = 0;
#define dbg(x) [&]() -> auto&&  {          \
    ++recursion_depth;                     \
    auto &&value = x;                      \
    cerr << string(recursion_depth, '\t')  \
         << #x" = " << value << endl;      \
    --recursion_depth;                     \
    return value;                          \
}()

What's next?

There're amazing articles from Golovanov399 here, and from HosseinYousefi here — check them, they cover a lot of things (like all(xs) macro) I omitted. There's also another my article about reading and declaring variables at once. And more will come, stay tuned!

I would like to thank:

See ya!

Теги tips-and-tricks, macros, c++ template, debugging

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en36 Английский dendi239 2020-07-01 12:17:16 0 Add some tags
en35 Английский dendi239 2020-06-30 15:46:48 0 Add link to copy-paste libs soft (published)
en34 Английский dendi239 2020-06-30 15:46:11 76 (saved to drafts)
en33 Английский dendi239 2020-06-29 09:50:48 0 (published)
en32 Английский viskonsin 2020-06-29 09:41:48 491
en31 Английский dendi239 2020-06-29 09:25:57 378
en30 Английский dendi239 2020-06-29 09:12:49 60 Add `ALL` macro to `BY` macro showcase
en29 Английский dendi239 2020-06-29 09:07:27 59
en28 Английский dendi239 2020-06-29 09:01:46 424
en27 Английский dendi239 2020-06-29 08:53:09 9 Tiny change: 'oiler>\n\n[cut]\n\n# `bit' -> 'oiler>\n\n# `bit'
en26 Английский dendi239 2020-06-29 08:52:39 18
en25 Английский dendi239 2020-06-29 08:52:01 11
en24 Английский dendi239 2020-06-29 08:51:03 2028
en23 Английский dendi239 2020-06-29 08:48:39 1016
en22 Английский dendi239 2020-06-29 04:32:18 164
en21 Английский dendi239 2020-06-29 04:31:51 348
en20 Английский dendi239 2020-06-29 03:45:58 22
en19 Английский dendi239 2020-06-29 03:40:12 541
en18 Английский dendi239 2020-06-29 03:28:09 1480
en17 Английский dendi239 2020-06-29 03:22:29 852
en16 Английский dendi239 2020-06-29 03:06:38 1757 Add complete template
en15 Английский dendi239 2020-06-29 02:49:11 14
en14 Английский viskonsin 2020-06-28 15:28:52 8
en13 Английский viskonsin 2020-06-28 15:27:20 421
en12 Английский viskonsin 2020-06-28 14:52:11 10
en11 Английский viskonsin 2020-06-28 14:19:52 115
en10 Английский viskonsin 2020-06-28 14:12:57 16
en9 Английский viskonsin 2020-06-28 13:48:14 14 Tiny change: '&& { \\n ' -> '&& { \t \\n '
en8 Английский viskonsin 2020-06-28 13:38:14 36
en7 Английский viskonsin 2020-06-28 13:21:53 1 Tiny change: 't's not ¯\_(ツ)_/¯).' -> 't's not ¯\\_(ツ)_/¯).'
en6 Английский viskonsin 2020-06-28 13:21:22 956
en5 Английский dendi239 2020-06-27 21:41:38 1165 Tiny change: ' ' -> ' '
en4 Английский dendi239 2020-06-27 21:08:58 2985
en3 Английский dendi239 2020-06-27 20:33:43 109
en2 Английский dendi239 2020-06-27 20:31:53 102 Tiny change: ' = 2 2 4\n~~~~\n\n' -> ' = 2 2 4\n\n cout << a + b << '\n';\n}\n~~~~\n\n'
en1 Английский dendi239 2020-06-27 20:28:28 9429 Initial revision (saved to drafts)