Avoiding temporaries - generalizing i++ using std::exchange

This post was originally written on Codeforces; some relevant discussion can be found here.

Note: for those who don’t like using the post-increment operator (i++), hopefully this post convinces you that it is not just a convention that C programmers coaxed the world into following out of tradition. Also, all of the following discusses the increment operators in C++, and not C, where the semantics are slightly different.

Disclaimer: I use ++i much more often in code. But i++ has its own place, and I use it — and the generalization I mention — quite frequently wherever it is a sane choice.

Is ++i better than i++?

A lot of people are taught that since i++ also returns the old value of i before the increment, it needs a temporary, and hence it must be slower. Good news: almost all compilers today optimize this part away whenever this behaviour is not needed, and the difference between i++ and ++i doesn’t matter.

So what’s the difference? In C++, turns out that apart from this old/new value difference, there is another difference.

Any expression in C++ that looks like a op b= where op is a binary operator in fact “returns” a reference to the variable a after completing the operation. As a result of this, you can do things like this:

// replaces x by a * x % p
void mod_mul(int64_t& x, int a, int p) {
  (x *= a) %= p;
}

Turns out that since you only need the value after the increment for the pre-increment operator, it is possible to have similar behaviour there too, and that is precisely what C++ chose to do:

// replaces x by (x + 1) % p
void mod_inc(int64_t& x, int p) {
  ++x %= p;
}

However, the post-increment doesn’t enjoy any of these properties. Perhaps this is why the Google C++ Style Guide (which I don’t really like all that much, but will just quote here) recommends

Use the prefix form (++i) of the increment and decrement operators unless you need postfix semantics.

Another part of the language where you can see this distinction in practice is when you overload pre-increment and post-increment operators for a class:

struct Int {
  int value{};
  Int& operator++() {
    std::cout << "pre-incrementing\n";
    ++value; return *this;
  }
  Int operator++(int) {
    std::cout << "post-incrementing\n";
    Int temp = *this;
    ++value;
    return temp;
  }
};

If you notice closely, the return type of the pre-increment overload is a reference, which is not the case with the post-increment overload. Using a post-increment also makes a copy, so if you’re using a post-increment on a struct/class object that defines both, it is likely that there is a potential performance improvement lying right there.

So, is there any legitimate use-case for post-increment?

Indeed, there is. Notice how in the post-increment code in the previous example, we had to store a temporary. This gives us a hint as to where exactly post-increment is useful: when you need to avoid temporary variables! And one of the places where temporary variables are not needed is when an operation (in this case, increment) must be done after any use of a value.

An example to illustrate this point comes when you want to implement copying of a C-style, null-terminated string (without copying the null terminator so that you’re able to, let’s say, concatenate strings into a buffer). Let’s say we didn’t have post-increment in the language at all. The algorithm looks like this:

void copy_c_string(const char* input, char* output) {
  while (*input) {
    *output = *input;
    ++input;
    ++output;
  }
}

The first thing one would say is that there are too many lines of code — you need to check input, need to separately handle input and output pointers, and if someone is refactoring this code and accidentally deletes one of the increments, they will introduce a bug that is hard to find in a large codebase.

Contrast that with the following:

void copy_c_string(const char* input, char* output) {
  while (*input) {
    *output++ = *input++;
  }
}

The intent of moving the pointer forward immediately after every use (and using it exactly once, too) is perfectly conveyed, we don’t have too many lines of code, and all is well. Of course, it takes some time getting used to writing/reading this kind of code, but thinking of it in terms of “immediate operation after use” shows that it works analogously to what RAII is to a manual destructor call.

In fact, the usage of post-increment and pre-decrement (not pre-increment) was (and is) so popular (partly due to widespread use of half-open ranges), that certain architectures in the past had special functionality for them (for example, this). Thus, in some rare cases, it is imperative to use post-increment instead of pre-increment for performance.

Do we have an op= style (compound assignment) generalization for post-increment?

Yes, we do. It is called std::exchange.

What it does is this — std::exchange(a, b) returns the old value of a after setting it to b. So i++ is the same as std::exchange(i, i + 1) in terms of semantics.

Similarly, a = std::exchange(b, a) swaps the values of a and b, which shows that it is more general than std::swap, though maybe at a small performance hit for types more complicated than a simple integer. Adding a bunch of =std::move=s should fix that to some extent, though.

Why the strange name? How do I remember it?

I consider this to be a naming disaster, and believe that if there was a better succinct name that does NOT imply bidirectional flow of data, the C++ committee would probably have tried to do it.

The way I remember it is a = std::exchange(b, f(a, b)) is (morally) equivalent to std::tie(a, b) = std::make_pair(b, f(a, b)) — that is, the assignments are done at the same time. So somewhat like storing temporaries for everything that is to be assigned, and then performing the assignments at the same time.

A more general example is a = g(a, std::exchange(b, f(a, b))) which does std::tie(a, b) = std::make_pair(g(a, b), f(a, b)) — in a mathematical sense, it allows you to do two parallel assignments in a linear chain-like syntax. I believe this is what brings about the exchange naming (if not the CMPXCHG instruction).

A more intuitive way to read A = std::exchange(B, C) is that A becomes B and B becomes C at the same time.

Some competitive programming relevant examples

Fibonacci/linear recurrences

Writing a = std::exchange(b, a + b) is much easier and less error-prone than auto tmp = a; a = b; b = tmp + b; (in fact, someone pointed out that the initial version of this code was wrong). The same goes for any other linear recurrence in 2 variables.

Iterative GCD and extended GCD

Since the Euclidean GCD algorithm is also an affine transformation (especially one where you swap after update), the implementation goes from the less readable/intuitive

std::array<T, 3> extgcd(T a, T b) {
    std::array x{T{1}, T{0}};
    while (b) {
        std::swap(x[0] -= a / b * x[1], x[1]);   // x[0] = x[1], x[1] = x[0] - a/b * x[1]
        std::swap(a %= b, b);                    // a = b, b = a % b
    }
    return {x[0], x[1], a};
}

to

std::array<T, 3> extgcd(T a, T b) {
    std::array x{T{1}, T{0}};
    while (b) {
        x[0] = std::exchange(x[1], x[0] - a / b * x[1]);
        a = std::exchange(b, a % b);
    }
    return {x[0], x[1], a};
}

Lazy updates in buffers (use-and-clear)

It is usually error-prone to clear a buffer of, let’s say, updates that you want to process, in the very end of the processing function, as follows:

void flush() {
  for (auto x : updates) {
    // do something
  }
  updates.clear(); // easy to forget
}

Sometimes this might lead to a MLE as well, if this flush function is in fact a DFS that is called in a loop after processing the updates, where the graph is built during the function itself, and the memory limit is low or the structure you store inside the buffer has quite a lot of information.

To be able to deal with the first of these issues, people used something of the following sort:

void flush() {
  std::vector<Update> updates_tmp;
  using std::swap; swap(updates_tmp, updates);
  for (auto x : updates_tmp) {
    // do something
  }
}

This faces multiple issues

• You need to create and assign a temporary, and also need to remember the type of the updates variable (can you see where we are going with this?)
• The temporary exists till the end of the function, so this doesn’t fix the second issue.
• Initializing/declaring and then modifying is a very non-functional (anti-)pattern, and making it a habit in code will almost invariably lead to state-mutation-related bugs.

Consider the following solution using std::exchange:

void flush() {
  for (auto x : std::exchange(updates, {})) {
    // do something
  }
}

Which of these two implementations mirrors the intent of the original function? And which one would you choose to write yourself?

Some software engineering relevant examples

Implementing move constructors and assignment operators

While defining move semantics for your class, it is usually a good idea to keep the moved-from object in defined state. Sometimes this might even be necessary, for instance, when you want to implement something with semantics like std::unique_ptr.

Avoiding redundancy.

It is possible to avoid having to implement post-increment when pre-increment is already available by just doing return std::exchange(*this, ++Type{*this})

Acrobatics with locks

The “immediately do after use” idea also carries over to when you’re using locks — it is clearly optimal to use locks for as short a time as possible, when comparing across the same kinds of software architecture. One way that std::exchange can be used to this effect is to use a scoped lock inside a lambda, that returns std::exchange(resource, resetted_resource).

In fact, there is a common primitive in lock-free programming that uses the exchange idiom (compare-and-swap, test-and-set, std::atomic_exchange).

Generic programming with iterators

Sometimes the only way to increment an iterator is std::next. Using std::exchange, we can implement our own version of post-increment to be able to write generic code using iterators. Since iterators are very general, you might find yourself using this trick in very unexpected places too.

Please let me know what you think about this C++ feature and if there are any mistakes in the above post. Comments are welcome!