Why does push_back in this implementation reserve 2 * capacity + 1 instead of 2 * capacity?

Viewed 135

I'm looking at the implementation of vector on https://www.cs.odu.edu/~zeil/cs361/sum18/Public/vectorImpl/index.html.

Under 1.3.1, it shows:

if( theSize == theCapacity ) ➀
    reserve( 2 * theCapacity + 1 ); ➁

I am wondering, why is it reserving 2 * theCapacity + 1 instead of 2 * theCapacity?

In std::vector, it just doubles the capacity when the size of the vector is equal to the capacity, and you're trying to perform an append operation. I don't quite understand the purpose of the +1 here.

3 Answers

The C++ standard does not specify how a std::vector needs to grow in size. Doubling is a common implementation1, possibly born out of laziness than anything else. The +1 is there too in order to obviate the issue of a zero capacity, which can occur if vector::reserve is called with a zero argument, or if your implementation constructs a zero capacity std::vector by default.


1 Personally I believe that growing the capacity using a Fibonacci sequence is perhaps more natural, although I've never come across a std::vector implementation which does that.

Consider that std::vector::push_back is required to have amortized constant complexity (see eg here).

Reallocating all elements has linear cost.

Now imagine you would increase capacity to have space for only one additional element. This would mean that push_back has linear complexity. The only way to get amortized constant is to reduce frequency of reallocations the more elements are in the vector.

Doubling the capacity each time the vector is full is one way to achieve that. However, implementations are free to choose different allocation strategies as long as they are in accordance with the specification and nowhere the standard says that capacity has to double.

Having said this, capacity*2+1 is probably to avoid branching for capacity== 0 each time capacity changes.

PS: Actually the article already has a teaser below that code: "We’ll see later what this does to the big-O complexity for push_back()." and later they explore in detail how their allocation strategy ensures amortized constant complexity for push_back.

I am pretty sure this is due to the initial value of theCapacity. While this is not shown on the page you linked, we can assume that theCapacity is initialized to zero. This makes sense, as a vector that remains untouched should't allocate memory. Hence, on the first push_back, the + 1 makes sure memory for at least one element is allocated.

Related