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
.
For the C++ experts
And sometimes it functions as an analogue, in a philosophical sense, for
std::swap
when it comes to idioms like copy-and-swap. std::exchange
is ideal for use in implementing move constructors and move assignment
operators, if you are of the opinion that std::move
should perform
cleanup as much as possible.
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!