I am not exactly good to come up with algorithm costs, so here I am asking.
Here is a vector initially initialized with 1000 elements:
vector<unsigned int> mFreeIndexes(1000);
I will continuously pop_back/push_back elements to the vector, but never push_back over 1000 (so never force vector to reallocate).
In this case will the pop_back/push_back operations be O(1) or O(n)?
From the C++ standard 23.3.7.5:
void push_back(const T& x);
void push_back(T&& x);
Remarks: Causes reallocation if the new size is greater than the old capacity (...)
Note that it doesn't say that it can't reallocate in the other scenario but this would be a very unusual implementation of the standard. I think you can safely assume that push_back
won't reallocate when there's still capacity.
The thing with pop_back
is a bit more complicated. The standard does not say anything about reallocation in the pop_back
context. But it seems to be a common implementation (with no know exception) that pop_back
does not reallocate. There are some guarantees though, see this:
Can pop_back() ever reduce the capacity of a vector? (C++)
Anyway as long as you don't go over predefined size you are safe to assume that no reallocation happens and the complexity is indeed O(1).
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