5

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

Avi
  • 1,066
  • 1
  • 15
  • 37
  • 3
    As long as no reallocation is performed it should be O(1). – JFMR Sep 12 '17 at 13:33
  • 6
    When you `push_back` you *add* elements to the vector. After the above definition, if you do e.g. `mFreeIndexes.push_back(1);` then the vector will have 1001 elements. Perhaps you want the [`reserve`](http://en.cppreference.com/w/cpp/container/vector/reserve) function? – Some programmer dude Sep 12 '17 at 13:34
  • 2
    This question is already answered in the [documentation](http://en.cppreference.com/w/cpp/container/vector/pop_back). – nwp Sep 12 '17 at 13:39
  • @Someprogrammerdude first i will "consume" elements with pop_back, and only push_back when there is "room", e.g.: i am in the range of capacity. – Avi Sep 12 '17 at 13:50
  • 1
    If the capacity never runs out, then no reallocation will be needed, and the push and pop operations shall be constant (in your case where no custom copy or move construction/assignment is made). The operations basically only need to increment or decrement the size, and for the push it will copy the value. – Some programmer dude Sep 12 '17 at 13:54
  • 2
    A `push_back` to a vector is O(1) *on average*. [Constant amortized time](https://stackoverflow.com/questions/200384/constant-amortized-time) – Bo Persson Sep 12 '17 at 14:00
  • 1
    The time complexity `push_back` operation in vector is [Amortized](https://stackoverflow.com/a/15079679/5811973) **`O(1)`**. – Ishpreet Sep 12 '17 at 14:14

1 Answers1

4

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

freakish
  • 54,167
  • 9
  • 132
  • 169
  • 1
    I just wanted to add that a `vector<>` with `push_back()` and `pop_back()` usage is pretty much the fastest stack that you can get: You won't have any memory allocation in your inner loop, and it provides good cache-locality. – cmaster - reinstate monica Sep 12 '17 at 15:32
  • The (iterator and reference) invalidation guarantees prevent it from reallocating if capacity does not change. – Caleth Sep 12 '17 at 15:57
  • 1
    @Caleth I couldnt find those guarantees in the standard. Not for pop. Only for erase. Pop might be functionally derived from erase but I couldnt find that as well. – freakish Sep 12 '17 at 16:03