4 ms·
IMO any discussion of std::vector::reserve should be accompanied by warnings that it can actually make your program slower if used improperly. https://en.cppre
by vitus 4y ago
IMO any discussion of std::vector::reserve should be accompanied by warnings that it can actually make your program slower if used improperly.
https://en.cppreference.com/w/cpp/container/vector/reserve https://en.cppreference.com/w/cpp/container/vector/reserve
> Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing the capacity to grow linearly rather than exponentially) and result in increased computational complexity and decreased performance.
The cost of vector dynamic reallocation has gone down dramatically since C++11 introduced move constructors -- the example of a vector<string> actually uses std::move (which is comparable to copying 3 pointers, as opposed to the pointed-to allocation of the underlying string). Of course, that specific case relies on std::string's move constructor being defined as noexcept. So, when used properly, reserve will speed up your program, just often not as much as you might expect.
- einpoklum 4y ago> The cost of vector dynamic reallocation has gone down dramatically since C++11 introduced move constructors 1. It's gone down, but it's still very high. 2. It hasn't gone down for types types like std::string_view, for which moving and copying take about the same amount of effort.
- vitus 4y agoVector reallocations result in an average of one* move (which yes, is effectively a copy for types like string_view) per element under normal operation. If you're concerned about that single copy (primarily: if profiling has demonstrated that this is a real bottleneck), and you know the target size a priori, then yes, by all means, use reserve. Just be warned that if you do it wrong, you can literally make your program exponentially slower. And, that it's less imperative to do so now than it was 15 years ago. (I'm personally much less concerned about the cost of copying 16B from a string_view, than I am about copying 24B + arbitrary amounts of underlying storage from a string.) * Yes, I know, elements at the beginning of the vector will be moved/copied more often than elements at the end.
- jeffbee 4y ago> arbitrary amounts of underlying storage from a string The whole point of move construction is that moving a string is almost as cheap as moving a string_view. The moved-to string now owns the external storage and the moved-from string does not.
- vitus 4y agoExactly, which is why I haven't worried about it ever since I started working with C++11. It was certainly the case that reserve was critical back in the C++03 days, though.
- dataflow 4y agoI literally ran into this some 2-3 days ago. It's a subtle and awful footgun. I don't see why they couldn't mandate geometric growth and have reserve_exact or something for this.
- sagarm 4y ago> subtle and awful footgun push_back and emplace_back already give you geometric growth; reserve is supposed to circumvent this.
- dataflow 4y agoNot really. Not every problem is that simple. For example sometimes you need to know that insertion will not allocate and/or move data around at the wrong point, so you need to reserve() beforehand despite not knowing the final size.
- sagarm 4y agoIf I want pointer stability, I usually use resize() + operator[] instead of reserve, though of course this requires a cheap default constructor. reserve + push_back feels more likely to subtly rather than loudly break due to future changes.
- deleted 4y ago[deleted]
- dataflow 4y agoIs resize() guaranteed to respect geometric growth? I know it has for me in practice, but this made me question everything. And more generally, it's nice when you can do that, but it's not a substitute. From an API standpoint it seems really weird for reserve() and resize() to differ in what they set the target capacity to - the natural thing would seem to be that they should only differ in the initialization + resizing, not in the reservation.
- vitus 4y ago