Take a look at this code:
At first glance, it should output $$$3$$$ because that's what $$$f()$$$ returns, which is then assigned to $$$k_0$$$. But when executed, this code outputs $$$1$$$!
This code is very short and everything seems clear, we're simply assinging $$$k_0$$$ to the return value of $$$f()$$$ which is $$$3$$$, and the push_back in $$$f()$$$ clearly doesn't affect the result... or does it?
How an assingment operation really works
It may seem obvious at first, we just copying one value to another, but let's see how compiler actually handles this operation.
Consider this code. (Source)
This code can output any permutation from '$$$abcabc$$$' to '$$$cbacba$$$', because the evaluation order of function arguments and operands in addition is unsequenced in C++. This flexibility allows compilers to optimize performance by evaluationg arguments in any order (or even simultaneously).
And assignment is just another operation, meaning it's left and right operands can be evaluated in any order.
In our original example here's what happens:
1) Compiler evaluates the left operand (obtaining a reference to $$$k_0$$$).
2) Then, it calls $$$f()$$$.
3) Finally, it assigns the return value ($$$3$$$) to the previously obtained reference.
And if you're familiar with how vectors work, you might already see the issue.
How vectors work
A vector is a dynamic container, it's size can change, and elements can be added ('push_back') or removed ('pop_back').
Every vector has a capacity (the allocated memory space, initially empty). And when you call push_back, one of two things happens:
1) Capacity is sufficient. The new element is placed at the end, and the vector's 'end()' pointer is incremented.
2) Capacity is insufficient. A new memory block (typically $$$2x$$$ the current size) is allocated, existing elements are copied/moved to the new location, and then everything is the same as in the first case.
Vectors store elements contiguosly for fast indexing, so if reallocation occurs, the entire vector moves to a different memory location.
So what happens?
1) k.push_back(1) initializes the vector with $$$1$$$.
2) In $$$k_0 = f()$$$, the compiler:
2.1) First evaluates the left side (obtaining a reference to $$$k_0$$$).
2.2) Then calls $$$f()$$$, which performs k.push_back(3), and if reallocation occurs, reference to $$$k_0$$$ changes.
2.3) Finally, it assigns $$$3$$$ to the now invalid reference, leaving the actual $$$k_0$$$ unchanged ($$$1$$$).
Conclusion
You can avoid this bug in many different ways, such as:
1) Storing the value of $$$f()$$$ in a variable and then assigning it to $$$k_0$$$
2) Preallocate memory (do k.reserve(2) in this example) to ensure no reallocation happens during push_back.
3) Push_back to the vector before or after the function if possible.
I faced this mistake while debugging a Cartesian tree problem, and spent 2-3 hours figuring it out. Hopefully, this blog helps you avoid the same mistake or at least know how to fix it.
Have you faced a similar mistake?
