[seanbax]

If the vector has to be resized in push_back, the implementation copy-constructs a new object from x. It resizes the buffer. Then it move-constructs the copy into the buffer. The cost is only a move construct per resize... So it's on the order of log2(capacity). Very efficient. But don't get used to it, because there are plenty of other C++ libraries that will break under aliasing.

[embe42]

I think the implementation in C++ does not do realloc on push_back, but allocates new memory, creates the new element and only then deallocates it.

I believe the reason f3 is safe is that the standard says that the iterators/references are invalidated after push_back – so push_back needs to be carefully written to accept aliasing pointers.

I am pretty sure if I were writing my own push_back it would do something like "reserve(size() + 1), copy element into the new place", and it would have different aliasing requirements...

(For me this is a good example of how subtle such things are)

[tialaramex]

I know this wasn't your main point here but with the C++ std::vector's reserve you must not do this because it will destroy the amortized constant time growth. Rust's Vec can Vec::reserve the extra space because it has both APIs here.

The difference is what these APIs do when we're making small incremental growth choices, Vec::reserve_exact and the std::vector reserve both grow to the exact size asked for, so if we do this for each entry inserted eight times we grow 1, 2, 3, 4, 5, 6, 7, 8 -- we're always paying to grow.

However when Vec::reserve needs to grow it either doubles, or grows to the exact size if bigger than a double. So for the same pattern we grow 1, 2, 4, no growth, 8, no growth, no growth, no growth.

There's no way to fix C++ std::vector without providing a new API, it's just a design goof in this otherwise very normal growable array type. You can somewhat hack around it, but in practice people will just advise you to never bother using reserve except once up front in C++, whereas you will get a performance win in Rust by using reserve to reserve space.

[MathMonkeyMan]

> allocates new memory, creates the new element and only then deallocates it.

Ah, I'll have to check the standard. Thanks.