0xA28's blog

Ambiguity in Data Structures with Amortized Analysis O(1) Operations
By 0xA28, history, 9 years ago, In English

As I managed to understand, When we are dealing with some dynamic data structure which has an average cost of O(1) Amortized Analysis in push and pop operations like vector in c++, the vector takes constant time per each push till it reaches to the Nth push (N = current size reserved), in the Nth push it takes linear time to allocate a new space typically with double the old size, and pretty the same done in pop operations.

Now assume that we have a vector of N current reserved space with N — 1 elements, every time we push a new element into the vector then pop it again, is this done in a linear time to change the allocated space ? it seems not, but why ?

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

It doubles when it becomes full, true.

But it doesn't contracts as soon as half of the elements are empty, it contracts when 1/4th of the allocated memory is being used. There is some calculations of amortized analysis, that is used to proof that its yet O(1) in both push and pop regardless of the example you gave above.

Let us, vector x(y), where x is the used array and y is the allocated memory. So for example 4(4), an element is inserted and memory is doubled, now 5(8). If now pop is called new state would be 4(8) but there will be no contraction. Again pop sometimes and it becomes 3(8)->2(8), and only then it contracts to 2(4).

I hope you understand :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that's pretty convincing! thanks a lot.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    it seems very convincing what you have said, but unfortunately i read in many articles and many answered questions at stackoverflow that pop_back doesn't shrink capacity at all. So i am confused about how it is really implemented.

    Source: https://frogatto.com/2009/11/17/how-cs-vector-works-the-gritty-details/

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Huh it seems it doesn't shrink , but it certainly should have . As I said in my earlier comment it is possible though. But may be c++ was going for faster runtime than memory efficiency. Thanks for pointing that out. ;-)

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The C++ Standard doesn't specify anything about reallocation when you pop_back from a vector, but there is the guarantee that no iterators will be invalidated after a call to pop_back, which implies that reallocation cannot occur.

Thankfully, when you care about the extra space your vectors are using, there's a shrink_to_fit method.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, I care about both the space and time, if i used shrink_to_fit every pop operation i would kill the time performance of the program. I think the proper thing to do is to check every pop operation if the size == 1/4 of the capacity then shrink_to_fit

    → Reply