I just found out that std::vector<T>::resize
"doubles" its capacity even when resizing to one element above the current size:
std::vector<int> v(50); v.resize(51); std::cout << v.capacity() << std::endl;
This program outputs 100 with GCC and Clang, and 75 with Visual C++. However, when I switch from resize
to reserve
:
std::vector<int> v(50); v.reserve(51); std::cout << v.capacity() << std::endl;
The output is 51 with all three compilers.
I wonder why implementations use a different expansion strategy for resize
and reserve
. It seems inconsistent, and I would expect the same behavior here.
I am just adding a link to a motivation for my question, where the impact on performance is reported: Why are C++ STL vectors 1000x slower when doing many reserves?
Adding a quote from C++11 Standard to clarify requirements for reserve
; §23.3.6.3(2):
After
reserve()
,capacity()
is greater or equal to the argument ofreserve
if reallocation happens...
Some additional thoughts: From C++11 Standard:
Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.
Which, effectively, implies constant (amortized) complexity for inserting a single element at the end. However, this applies only for vector modifiers, such as push_back
or insert
(§23.3.6.5).
resize
is not listed among modifiers. It's listed in §23.3.6.3 vector
capacity section. And, there are no complexity requirements for resize
.
However, in the vector
overview section (§23.3.6.1), there is written:
it (
vector
) supports (amortized) constant time insert and erase operations at the end
The question is whether resize(size()+1)
is considered to be "insertion at the end".
The C++ function std::vector::resize() changes the size of vector. If n is smaller than current size then extra elements are destroyed. If n is greater than current container size then new elements are inserted at the end of vector.
The main difference between vector resize() and vector reserve() is that resize() is used to change the size of vector where reserve() doesn't. reserve() is only used to store at least the number of the specified elements without having to reallocate memory.
To achieve this the vector uses an internal array. To improve performance a larger array (as needed) is allocated (thats the capacity). The push_back new has one job: to add a new element at the end of the vector (see last line of push_back). But sometimes the internal array is already full.
Resizing a vector doesn't destroy the values stored in the vector (except for those beyond the new size when shrinking, of course), however growing a vector beyond its capacity will copy (or, in C++11, move) them to a new place, thus invalidating and iterators, pointers or references to those elements.
As far as I can tell, neither resize
nor reserve
is required to have the demonstrated behaviour. Both are however allowed such behaviour although both could either allocate the exact amount, and both could multiply the previous allocation as far as the standard is concerned.
Each allocation strategies have their advantages. The advantage of allocating exact amount is that it has no memory overhead when the maximum allocation is known beforehand. The advantage of multiplying is that it maintains the constant amortized property when mixed with end-insertion operations.
The approach chosen by the tested implementations has the advantage that it allows both strategies when resizing. To use one strategy, one can reserve and then resize. To use the other, just resize. Of course, one has to be aware of the unspecified behaviour to take advantage of this. This advantage may or might not be the reasoning behind the choice of these implementations.
One might consider it a failure of the vector API, as specified in the standard, that expressing the intended reallocation behaviour is not possible (in a way that is guaranteed by the standard).
When you resize
more than there is capacity you already "demonstrate" that you don't want to reserve just the right capacity. On the other hand, if you use reserve
you explicitly ask for the right capacity. If reserve
would use the same strategy as resize
there would be no way to reserve just the right amount.
In this sense resize
without reserve
is for the lazy ones or in case you don't know the exact amount to reserve. You call reserve
if you know what capacity you need. That's two different scenarios.
PS: As StoryTeller pointed out, also reserve
is not required to reserve the exact amount that is asked for as per the standard. Nevertheless I think my main argument still holds: resize
(without reserve
) and reserve
are meant for different scenarios, where you either give a hint of how much you want to reserve or don't care about the actual capacity and just want to have the container sized to what you ask for.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With