increase in vector capacity

Question

i'm just a beginner in c++ . In my program i use vector push_back and go through this process many times .i also print the vector capacity after using push_back. the output shows that the capacity of the vector increases directly from 2 to 4 and then from 4 to 8. is this the way it works or is the capacity suppose to increase by 1 each time. I had this doubt because in 1 of the tutorials i was viewing the authors output showed the capacity of the vector increasing by one rather than powers of 2.

#include<iostream>
#include<vector>

void printStack(const std::vector<int> &stack)
{
    for (const auto &element : stack)
        std::cout << element << ' ';
    std::cout << "(cap " << stack.capacity() << " size " << stack.size() << ")\n";
}

int main()
{
    std::vector<int> stack;

    printStack(stack);

    stack.push_back(5); // push_back() pushes an element on the stack
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    printStack(stack);

    stack.push_back(5); // push_back() pushes an element on the stack
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    return 0;
}

Output:- (cap 0 size 0)

5 (cap 1 size 1)

5 3 (cap 2 size 2)

5 3 2 (cap 4 size 3)

5 3 2 5 (cap 4 size 4)

5 3 2 5 3 (cap 8 size 5)

5 3 2 5 3 2 (cap 8 size 6)

Thanks in advance.

That's the way it usually works (although the growth factor is implementation defined, and could just be 1 element). The idea is that if you `push_back()` and you're already at `capacity()`, the vector increases its capacity by some amount that should avoid another allocation on the next call to `push_back()`. The growth factor of 2 is quite common, although smaller factors (~ 1.5) may perform better, — Andrew, May 18 '16 at 12:16
@Andrew Is it still amortised constant time per addition of the factor is less than 2? — Angew is no longer proud of SO, May 18 '16 at 12:19
@Angew good question. I'll refer you to [the place I read about this](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling). The short answer is yes. — Andrew, May 18 '16 at 12:20
@Andrew That place just states the claim ("any factor greater than 1 ensures O(1) amortized append complexity towards infinity") without any supporting evidence. It may well be true, but a hint of a proof would be nice. — Angew is no longer proud of SO, May 18 '16 at 12:40
@Angew yes, that is a shame. Maybe [this](http://cs.stackexchange.com/questions/9380/why-is-push-back-in-c-vectors-constant-amortized) is more in line with what you were looking for? — Andrew, May 18 '16 at 12:48

score 2 · Answer 1 · answered May 18 '16 at 12:16

2

The capacity is supposed to increase such that the vector can hold enough elements. How this is done in detail is implementation dependent.

answered May 18 '16 at 12:16

463035818_is_not_an_ai

109,796
11
89
185

thnx for the help. – cecil jacob May 18 '16 at 12:27

increase in vector capacity

1 Answers1