Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

STL vector with reverse and pop/push_back cost

Tags:

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)?

like image 715
Avi Avatar asked Sep 12 '17 13:09

Avi


1 Answers

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).

like image 54
freakish Avatar answered Oct 04 '22 14:10

freakish