nor's blog

[C++] Avoiding temporaries — generalizing i++ using std::exchange
By nor, 12 months ago, In English

https://nor-blog.codeberg.page/posts/2023-11-27-std-exchange-cpp/

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

»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Great blog! Thank you so much. I wish I could upvote twice.

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

    Glad that you liked the blog. I'm planning to write some more C++ blogs too.

    → Reply
»
12 months ago, # |
  Vote: I like it +32 Vote: I do not like it

I use it in non-recursive get in dsu

while(i != p[i]) i = exchange(p[i], v);

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

    Just curious, do you really need sz to be mutable? Seems like it is not necessary

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

      Yes, but i don't want to break one line of code

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

    Nice example!

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

Just want to put the function signature of std::exchange here. I think I understand better after I know its signature.

template< class T, class U = T >
constexpr T exchange( T& obj, U&& new_value );
→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Yeah, in retrospect it seems that I should have put it in the blog for people who know about templates.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think, copy_c_string should be implemented as while (*output++ = *input++); in order to terminate the copied string with '\0' in the output.

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

    Yeah, my bad, somewhere I had switched from copying arrays to C strings. The example holds for both, and this one liner shows the true power of null-terminated strings (not that I would use null-terminated strings anywhere given that std::string exists). Updated the blog, since now the algorithm can be used to concatenate multiple strings.

    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

We can also use std::tie(a, b) = std::make_pair(b, a + b) Similar to python, very readable.

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

    The only problem with this piece of code is too many copies, std::exchange is faster on larger structs. Definitely more readable though, to the extent that I had used this as an explanation for the functionality of std::exchange.

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

From this blog post, I learned that extended gcd can be implemented non-recursively (or at least with no backtracking).

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

    I found it a bit surprising that most people implement extended GCD recursively, given that recursion is not very obvious (at least to me), and each step of extended GCD is just manipulating coefficients so that the equation is true before and after the operations that replace arguments with their new values.

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

      I think it's just because it was done recursively on emaxx, and from then on we do it exactly that way.

      → Reply
»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

An important thing to keep in mind is that most things in your code aren't bottlenecking the performance, and this gets more true the more complex your code gets, so how exactly you write them (as opposed to what logic you implement) is almost irrelevant. You shouldn't overoptimise or worry about maximum performance ahead of time. Just write something that's not slow (good algorithm and follow basic patterns like processing inner array in inner loop), check if it's good enough and move on. Your writing time is more valuable than the resulting program's time.

It's useful to know these things just in case you find out that your code isn't good enough and you need hardcore optimisations, or if you're writing a performance-critical library that's going to be reused.

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it

    I'm not sure where performance comes into discussion here. That is unless it is an argument for using i++ instead of ++i, targeted towards people who use ++i because of performance claims, which have been debunked in the blog too, except for the cases where the operators are defined for a class and can have potentially different behaviour.

    Also, I believe that when writing code, readability becomes quite important as the code becomes more and more complex. So expressing intent through code properly can prevent you from having bugs in the first place as well as help you catch bugs.

    If you're referring to the topic of the blog and didn't bother reading the content, it was more about getting rid of temporaries because they make code uglier, rather than performance considerations, since the compiler will generate the same code most of the time.

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

      Yeah, I was referring to those performance claims you addressed at the start — even if they were true, it almost doesn't matter.

      Regarding readability of code, it's not all that much about exact implementation, since the definition void copy_c_string(const char* input, char* output) offers much more info about what that code is supposed to do than the function body itself. When the code is structured like this, implementation of individual building blocks will need to be read less, and the most readable code is one where you don't need to look into extra details at all.

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

        Ah, that makes more sense.

        Regarding whether it is important to implement it properly — well, if it is write-once read-never code, then it makes sense to only have good names (and short functions like this) and not care about quality of implementation so much as long as it just works. Maybe this was not a very good example given how short it was, but in both longer functions (complicated functionality) as well as code that needs to be maintained (for example, during refactoring), having a harder-to-modify-incorrectly implementation is more preferable in general — in fact this is why functional code is seen as cleaner.

        This might only be partially true for competitive programming, where we optimize for writing once and not for maintaining, but is something that should be kept in mind in general.

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

Some other examples taken from code I wrote in the past

// union-find path compression
int find(int i) {
  int j = i;
  while (j != rep[j]) j = rep[j];
  while (i != j) i = exchange(rep[i], j);
  return j;
}

// delete a linked list
void del(list* p) {
  while (p) {
    delete exchange(p, p->next);
  }
}

// print space-separated ints
void print(vector<int> v) {
  auto sep = "";
  for (int x : v) {
    cout << exchange(sep, " ") << x;
  }
→ Reply