dendi239's blog

Micro- and macro-management for your next cpp source: General tips'n'tricks
By dendi239, history, 4 years ago, In English

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 ¯\_(ツ)_/¯).

TL;DR

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 a system directory, do it at 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 of adding 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 (which CLion is), then you could edit your CMakeLists.txt directly: 

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

Typealiases

In C++ there are a lot of strange things that came from ancient times, like signed long long int constructions. However, if you don't like such long type names, you could write using NewType = ExistingType or typedef ExistingType NewType.

A lot of programmers here, on CodeForces, use ll instead of long long and a bit less use ld instead of long double. Since C++11, we have int64_t, which is like long long but not that long. I could also suggest using the following (inspired by Rust):

using i64 = int64_t;
using f80 = long double;

using has an advantage over typedef: it supports templates, so you could shorten annoyingly long type names such as vector or unordered_set(map):

using Str = string;
template <class T> using Vec = vector<T>;
template <class K, class V> using UM = unordered_map<K, V>;

By the way, if you've noticed that sometimes map works faster than unordered_map even on big inputs, it happens because of expensive and frequent rehashing hidden in unordered_set(map). To work around it, I suggest calling um.reserve(4 * MAX_ELEMENTS_EXPECTED). It will work much faster. You can also read this article to learn more about unordered_map.

Prewritten library code

According to CodeForces' official rules, you might use some prewritten code. When it comes to some library-like code for things like fft, flows, or smth else you can find it annoying to search over your sources to copy/paste once you need it. One of the ways is to put all functionality you might need to separate files like z.hpp and simply include it [keep in mind the section about modifying header search paths].

If you don't use the include, just remove it before submission, and if you need it, you can simply jump to definition (most of IDEs can do it using ctrl + click to source and copy/paste content before submitting. 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 the following addition is performed by modulo
  cout << a + b << '\n';

  // note that because of the type of `a` bin_pow uses modular arithmetics
  cout << bin_pow(a, b) << '\n';
}

Don't forget to copy/paste the actual source (if you're using it) 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, you can find one such here.

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); cin.tie(nullptr); 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.

Interactive, custom files and other

Sometimes you don't need cin.tie for interactive problems or debugging in your IDE. Moreover, sometimes you need to work with custom files. To resolve it, I can suggest using defines INTERACTIVE and FILES:

// example of usage, don't use both in real life
#define INTERACTIVE
#define FILES "k3"

auto fast_io = [] {
#ifndef DEBUG
#  ifndef INTERACTIVE
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#  endif // INTERACTIVE
#  ifdef FILES
    freopen(FILES".in", "r", stdin);
    freopen(FILES".out", "w", stdout);
#  endif // FILES
#endif // DEBUG
  return 0;
};

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 the testing verdicts. Take a look at this submission:

➜  b cf test  
g++ -std=c++17 b.cpp -o b.exe -O2 -DLOCAL -DDEBUG
[ n ] = 4
[ n ] = 3
[ n ] = 1
[ n ] = 7
Passed #1 ... 0.001s 0B
[ n ] = 4
[ n ] = 3
[ n ] = 1
[ n ] = 7
Passed #2 ... 0.001s 0B
rm b.exe
➜  b cf submit
Submit CONTEST 1367, problem b
Current user: dendi239
Submitted
      #: 85413433
   when: 2020-06-29 03:31
   prob: B - Even Array
   lang: GNU C++17
 status: Accepted                   
   time: 61 ms
 memory: 3.71 MB

Run debug code only in debug mode

You may need to run some extra code for debugging purposes only. For example, printing a graph, performing additional checks, or comparing with the naive solution. It may affect the resulting performance and move you from the AC zone to the 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 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__) << '\n'

Where log function prints all arguments given to it. You could implement it the way I 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__) << '\n'

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 a 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 a 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__) << '\n'
#  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 the 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 a type vector<Cell> 
  // and it will be copied 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 still 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 have noticed that you often write code like return foo(lhs) < foo(rhs);. Here's the 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 only compare by .second, it's not suitable (you'll still have to define some_func which takes a few extra lines) :(. However, we could generate all necessary code on our own (thanks to viskonsin for pitching me this idea):

#define ALL(xs) begin(xs), end(xs)

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

sort(ALL(pairs), 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 plenty of code out of one short macro!

dbg macro

Thanks to ramchandra for his amazing dbg macro, really nice job. There's also the dbg! macro in Rust. Let's develop the same behavior: dbg(expr) works as a simple expr in release mode and additionally prints it in debug mode. Well, the implementation for release mode is pretty straightforward:

#define dbg(...) (__VA_ARGS__)

And what about the 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 a simple lambda on the fly (note that forward is used since we need to keep lvalue if it was passed and fallback to moving value if not: for dbg(i + j) we don't need to return a reference to local object):

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

Conclusion

You might have noticed that there's a lot of complicated things involved. It took me way more than 21 days to come up with all of these tips'n'tricks. Some of them contained bugs in the first version, others not. However, anytime you use macros it's unclear what they expand to and pretty easy to make a mistake. Don't use any single macro you're not feeling ready to debug a bit if necessary. If you don't feel comfortable in understanding some of these macros, prefer not to use them.

Here's a simple way to make a mistake when dealing with READ macro:

// does not compile
for (int READ(t); t--;)

// expands to
for (int t; io::read(t); t--;)

// why there're three ";" inside for?

It took over half an hour to come up with dbg macro that worked as I wanted it to. I tried a lot of things, even stack overflow didn't give me an answer, but months of exploring STL sources gave me a simple hint (actually it was a question: "what I need to use std::forward for?").

There's plenty of code, isn't it? Note that it may be overcomplicating to use every single of macros: just choose which ones you like and add them to your template. However, you could add all of them:

#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;
using f80 = long double;

using Str = string;
template <class T> using Vec = vector<T>;
template <class K, class V> using UM = unordered_map<K, V>;

template <class T> auto &operator>>(istream &is, vector<T> &xs)
{ for (auto &x : xs) is >> x; return is; }

namespace io {
template <class ...As> auto &read(As &...as) { return (cin >> ... >> as); }
template <class ...As> auto &log(const As &...as) { return ((cerr << " " << as), ...); }
}  // namespace io

#define ALL(xs) begin(xs), end(xs)
#define BY(...) [&](auto &&lhs, auto &&rhs) { \
  auto predicate = [&](auto &&x) {            \
    return __VA_ARGS__;                       \
  };                                          \
  return predicate(lhs) < predicate(rhs);     \
}  
#define READ(...)             __VA_ARGS__; io::read(__VA_ARGS__)
#define READ_CTOR(name, ...) name(__VA_ARGS__); io::read(name)

#ifndef ONLINE_JUDGE
  int recursion_depth = 0;
#  define RUN       for (bool _flag = true; _flag; _flag = !_flag)
#  define LOG(...)  cerr << string(recursion_depth, '\t') \
                         << "[ "#__VA_ARGS__" ] =";       \
                    io::log(__VA_ARGS__) << '\n'
#  define dbg(...) [&]() -> auto && {         \
      ++recursion_depth;                      \
      auto&& value = __VA_ARGS__;             \
      --recursion_depth;                      \
      cerr << string(recursion_depth, '\t')   \
           << #__VA_ARGS__" = " << value      \
           << endl;                           \
      return forward<decltype(value)>(value); \
  }()
#else
#  define LOG(...) while (false) cerr
#  define RUN      while (false)
#  define dbg(...) (__VA_ARGS__)
#endif

auto main() -> int {
  // write code here
}

namespace {
auto fast_io = [] {
#ifndef DEBUG
#  ifndef INTERACTIVE
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#  endif // INTERACTIVE
#  ifdef FILES
    freopen(FILES".in", "r", stdin);
    freopen(FILES".out", "w", stdout);
#  endif // FILES
#endif // DEBUG
  return 0;
};
} // namespace

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 all at once. And more will come, stay tuned!

I would like to thank:

See ya!

Full text and comments »

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

Micro- and macro-management for your next cpp source: For
By dendi239, history, 4 years ago, In English

Hello, codeforces!

In this article, I would like to show you how to reduce time spent on working with for cycle. There're a few ways to do it, I'll show macro-based and expressible in pure c++.

Introduction

I love for cycle. It looks quite simple:

for (init statement; condition; increment)

But you can adapt it to do many great things. To illustrate the power of for, let's look at the simple binary search problem: we have some values l, r and a predicate p which is true on segment [l, x] and false on (x, r), and we are asked to find x. Using for we can implement the solution in basically just one line:

for (int m = (l + r) / 2; abs(r - l) > 1; (p(m) ? l : r) = m, m = (l + r) / 2);

Pretty neat, huh?

After the cycle finishes, you'll get l = x.

Another important note, the (p(m) ? l : r) = m part works because ternary operator returns reference type. It means that (is_left ? left : right) = new_value; assigns new_value either to left or to right, depending on the value of is_left.

You've probably noticed that here I used abs(r - l) > 1 instead of simple l < r. Well, it happened for a reason: that way we can use this implementation even if l > r and the predicate it true on segment [x, l] and false on (r, x).

To make it yet more elegant (and probably less readable), you could notice that operator , evaluates operands and returns the last one, which allows us to transform two statements m = (l + r) / 2 into a single one:

for (int m; m = (l + r) / 2, abs(r - l) > 1; (p(m) ? l : r) = m);

Now, to make it work for various types of p, l, r let's create a template function:

template <class T, class P>
T bin_search(T left, T right, P pred) {
  for (T mid; mid = (left + right) / 2, mid != left && mid != right; (pred(mid) ? left : right) = mid);
  return left;
}

Changing the condition to mid != left && mid != right makes it almost work for doubles, too: you need to provide a simple class that checks if two doubles are equal with given precision:

struct Float {
  double value;

  bool operator!=(const Float &rhs) const;

  Float operator+(const Float &rhs) const;
  Float operator/(const Float &rhs) const;
};

FOR macro

Okay, in the previous section we've seen that you can do some amazing things with for. However, most of the time you'll probably also need to do something very simple, like iterating over [0, n). I've noticed that a lot of programmers use the short form of for cycle for this. Typically it looks like:

#define FOR(i, n) for (int i = 0; i < n; ++i)

Much simpler and shorter than writing raw for! Then you might also wonder how to do a similar shortcut to iterate over [a, b) and find out that you can't override macro by number of arguments. However, we can use 0 instead of O:

#define FOR(i, n)    for (int i = 0; i < n; ++i)
#define F0R(i, a, b) for (int i = a; i < b; ++i)

But what if a > b? Ok, then we need to add additional checks:

#define FOR(i, n)    for (int i = 0; i < n; ++i)
#define F0R(i, a, b) for (int i = a; i != b; (a < b) ? ++i : --i)

There's a potential bug: if you have huge a and b (not fitting into int for example), then you will get integer overflow for i. To resolve it, you could use decltype expression to get the same type as n for FOR. With F0R it's a bit more complicated. First idea is to simply get type from a or b:

#define FOR(i, n)    for (decltype(n) i = 0; i < n; ++i)
#define F0R(i, a, b) for (decltype(a) i = a; i != b; (a < b) ? ++i : --i)

But what will happen if you use F0R(i, 0, n) or F0R(i, n, 0)? The type of 0 is int, and if n is int64_t you'll probably be unhappy with the results. But there's a solution I found while exploring gcd from the standard library: 

#define F0R(i, a, b)  for (common_type_t<decltype(a), decltype(b)> i = a; i != b; (a < b) ? ++i : --i)

Okay, we managed to implement both macros, but now have a drawback of needing to write 0 in some cases. I'm not that smart — can remember only one for macro, having more than one can drive me crazy in mistyping. Can we do better? I googled this a bit and found a trick, that helps actually writing FOR in both cases:

#define GET_MACRO_3(_1, _2, _3, NAME, ...) NAME

#define FORN  ...
#define FORAB ...

#define FOR(...) GET_MACRO_3(__VA_ARGS__, FORAB, FORN)(__VA_ARGS__)

How does it work? GET_MACRO_3 simply expands to its 4th argument. If we pass three parameters to FOR, then the 4th parameter of GET_MACRO_3 will be FORAB, if we pass two, then FORN, thus parameters will be passed to the corresponding macro.

Let's get it all together:

#define GET_MACRO_3(_1, _2, _3, NAME, ...) NAME

#define FORN(i, n)     for (decltype(n) i = 0; i < n; ++i)
#define FORAB(i, a, b) for (common_type_t<decltype(a), decltype(b)> i = a; i != b; (a < b) ? ++i : --i)

#define FOR(...) GET_MACRO_3(__VA_ARGS__, FORAB, FORN)(__VA_ARGS__)

Alternatives to macro

Yeah, having FOR(i, n) is much shorter than for (int i = 0; i < n; ++i), but is there macro-free option? It's the beginning of the section, not the end, so you can guess the answer is yes.

We already have a convenient range-based for. Can we apply it here? There's the straightforward way:

auto range(int n) {
  vector<int> is(n);
  iota(is.begin(), is.end(), 0);
  return is;
}

...

for (int i : range(n))

But there's an issue: this function allocates extra memory to simply iterate over numbers. It seems like mining raisin from pies: you put raisin to pies to extract them only because you have a convenient way to transfer pies. But can we share raisin itself? Ok, let's try to manage it:

for (int i : range(n))

// is equivalent to

auto &&r = range(n);
for (auto begin = r.begin(), end = r.end(); begin != end; ++begin) {
  int i = *begin;
  // loop body
}

So, all we need is to define some object r has methods .begin(), .end() return iterator can ++, *, !=. Ok, let's do it:

struct range_it {
  int value;
  
  int operator*() const { return value; }
  auto &operator++() { ++value; return *this; }
  bool operator!=(const range_it &rhs) const 
  { return value != rhs.value; }
};

struct range {
  int n;

  range() = default;
  explicit range(int n) : n(n) {}

  range_it begin() const { return range_it(0); }
  range_it end() const { return range_it(n); }
};

Ok, here we replaced range(n) from function to class ctor. But what with FORAB? Ok, let's modify it a bit by adding an extra field to range class:

struct range {
  int a, b;

  range() = default;
  explicit range(int n) : a(0), b(n) {}
  explicit range(int a, int b) : a(a), b(b) {}

  range_it begin() const { return range_it(a); }
  range_it end() const { return range_it(b); }
};

Looks good, doesn't it? Here's some working code:

for (int i : range(n))
  for (int j : range(i, n))
    dance_like_no_one_watching(i, j);

But here's a problem: it doesn't work with for (int i : range(n, 0)). Ok, let's check it whenever we need:

struct range_it {
  int value, step;
  
  int operator*() const { return value; }
  auto &operator++() { value += step; return *this; }
  bool operator!=(const range_it &rhs) const 
  { return value != rhs.value; }
};

struct range {
  int a, b, step = 1;

  range() = default;
  range(int n) : a(0), b(n), step(1) {}
  range(int a, int b) : a(a), b(b), step(1) {
    if (a > b) {
      step *= -1;
      swap(a, b);
    }
  }

  range(int a, int b, int step) : a(a), b(b), step(step) {}

  range_it begin() const { return range_it{a, step}; }
  range_it end() const { return range_it{b, step}; }
};

Here we can easily use range as we used to in Python. But what about overflowing? Well, we could've added a template here: 

template <class T> struct range_it {
  T value, step;
  
  T operator*() const { return value; }
  auto &operator++() { value += step; return *this; }
  bool operator!=(const range_it &rhs) const 
  { return value != rhs.value; }
};

template <class T> struct range {
  T a, b, step = 1;

  range() = default;
  range(T n) : a(0), b(n), step(1) {}
  range(T a, T b) : a(a), b(b), step(1) {
    if (a > b) {
      step *= -1;
      swap(a, b);
    }
  }

  range(T a, T b, T step) : a(a), b(b), step(step) {}

  range_it begin() const { return range_it{a, step}; }
  range_it end() const { return range_it{b, step}; }
};

But you still need to write some ugly code to simply iterate through [0, ..., n) backwards: for (int i : range(n-1, -1, -1)). That's a pretty annoying thing to deal with, isn't it? Well, you could've patched range to do it: 

template <class T> struct range_it {
  T value, step;
  
  T operator*() const { return value; }
  auto &operator++() { value += step; return *this; }
  bool operator!=(const range_it &rhs) const 
  { return value != rhs.value; }
};

template <class T> struct range {
  T a, b, step = 1;

  range() = default;
  range(T n) : a(0), b(n), step(1) {}
  range(T a, int b) : a(a), b(b), step(1) {
    if (a > b) {
      step *= -1;
      swap(--a, --b);
    }
  }

  range(T a, T b, T step) : a(a), b(b), step(step) {}

  range_it begin() const { return range_it{a, step}; }
  range_it end() const { return range_it{b, step}; }
};

What advantages over a macro?

Since we have the proper range object, we might add any adapters we might need. For example, filter, or transform. Take a look:

bool is_prime(int p) {
  for (int d = 2; d * d <= p; ++d)
    if (p % d == 0) 
      return false;
  return true;
}

int main() {
  for (int i : range(100) 
             | filter(is_prime) 
             | transform([](int x) { return x * x; }))
    cout << i << ' ';
}

That might take some time to implement, you could check one of the possible implementations here, or even better here. However, if you don't want to do it yourself, it's done in ranges library coming with c++20.

Full text and comments »

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

Micro- and macro-management for your next cpp source: Reading
By dendi239, 4 years ago, In English

Hello, codeforces!

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.

After a few hours of working on this post, I decided to split it into several more focused articles -- it's so hard to write about everything I planned, cover all nuances, and don't make it super-big.

For simple tasks, you may need to write very little code solving the problem and the biggest part of the source will be about reading values. Thus, declaring and reading variables seem like things that need to be simplified. Is there a way to shorten the following?

int n, m, k, t, q;
cin >> n >> m >> k >> t >> q;

There're a few ways, more or less flexible, I'll show one of them, you can find another, for example, here:

int READ(n, m, k, t, q);
// here variables n, m, k, t, q are declared and read from stdin.

In the following section we will use variadic number of arguments for functions and macros. It might be a bit hard to understand, but you still can copy/paste the result and skip this section.

How to achieve this? Well, we need to do two things: declare variables and read them. Let's start from scratch:

#define READ(...) __VA_ARGS__; read(__VA_ARGS__)

int READ(x, y, z);
// expands to:
int x, y, z; read(x, y, z);

Where read is a function that reads all arguments given to it. But how to do it? We need a function that takes as many arguments as you want and reads every single one by reference from stdin. However, we can't simply iterate over them through a cycle:

for (auto &arg : args) cin >> arg;

We can't since there's no collection or smth else. But for simple and arguably short versions we could write the following:

void read() {}

template <class T> 
void read(T &value) {
  cin >> value;
}

template <class T1, class T2>
void read(T1 &x1, T2 &x2) {
  cin >> x1 >> x2;
}

// and so on

It seems a little messy, isn't it? But what if we need to read 13 arguments and have a macro that works fine with only up to 10? Let's use variadic template parameters. We can use the simple trick with recursion: if there're parameters, take one of them, read it and repeat with the rest:

template <class ...Args>
void read(Args &...args);

template <>
void read() {}

template <class Arg, class ...Args>
void read(Arg &arg, Args &...args) {
  cin >> arg;
  read(args...);
}

Since C++17 we can do it slightly shorter and prettier with parameter pack:

template <class ...Args>
void read(Args &...args) {
  (cin >> ... >> args);
}

Let's combine it all together: 

template <class ...Args>
auto &read(Args &...args) { return (cin >> ... >> args); }

#define READ(...) __VA_ARGS__; read(__VA_ARGS__)

Note return type: it will be deduced as istream & so you can read additional values:

vector<int> ws(m);
for (int e = 0; e < m; ++e) {
  int READ(u, v) >> ws[e];
  connect(--u, --v);
}

Types with no defined input operator, vector

To work with other types, you can define operator>>(istream &is, YourType &your_variable) to use it with cin or READ macro. For example, you can define operator>> for vector. Often in problems, you need to read the size of a vector, followed by its elements. I could suggest using READ_CTOR macro for this:

template <class T> istream &operator>>(istream &is, vector<T> &vec);

#define READ_CTOR(value, ...) value(__VA_ARGS__); cin >> value

// usage
int READ(n);
vector<int> READ_CTOR(xs, n);

READ_CTOR can be used to initialize a variable with a constructor and then read it.

Example

You could look at all these tips in action here.

Credits

If you have any thoughts to extend or update this code, feel free to leave a comment below. What tricks do you use for reading values?

I would like to thank:

  • viskonsin for help in editing this article
  • Golovanov399 and HosseinYousefi for inspiring me to write this article (more will come)
  • MikeMirzayanov for great Codeforces platform (haven't tried Polygon yet:)
  • Whole codeforces community for sharing their great code -- it made me try to improve my template.

Full text and comments »

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