In C++, will the vector function push_back increase the size of an empty array?

Question

Quick question. Let's say I declare a vector of size 20. And then I want to add a few integers to it using push_back.

vector<int> myVector(20);
myVector.push_back(5);
myVector.push_back(14);

Is the capacity of my vector now 22, or is it still 20? Were 5 and 14 added to indices [19] and [20], respectively? Or are they at [0] and [1]?

Solution 1

After those statements its capacity is implementation-defined. (Please note that is different from its size.)

---

vector<int> myVector(20);

This creates a vector filled with twenty 0's. Its size is twenty, exactly, and its capacity is at least twenty. Whether or not it's exactly twenty is implementation-defined; it may have more (probably not, in practice).

myVector.push_back(5);

After this, the twenty-first element of the array is 5, and the capacity is once again implementation-defined. (If the capacity had been exactly twenty before, it is now increased in an unspecified manner.)

myVector.push_back(14);

Likewise, now the twenty-second element of the array is 14, and the capacity is implementation-defined.

---

If you want to reserve space, but not insert elements, you'd do it like this:

vector<int> myVector;
myVector.reserve(20); // capacity is at least twenty, guaranteed not
                      // to reallocate until after twenty elements are pushed

myVector.push_back(5); // at index zero, capacity at least twenty.
myVector.push_back(14); // at index one, capacity at least twenty.

Solution 2

• size is the number of elements in the vector container.
• capacity is the size of the allocated storage space
• push_back effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call.

More info: http://www.cplusplus.com/reference/stl/vector/

Solution 3

push_back increases the size of the std::vector and places the new elements at the back of the vector (other containers also have a push_front method to do the same thing at the front as well).

However, there is a difference between the size and the capacity of a vector. The size refers to how many items are actually in the vector right now; the capacity refers to the total number of items that the vector can hold without reallocating memory. It's possible to reserve() memory if you know that you're going to add several elements and don't want to grow the vector piecemeal.

Solution 4

As the vector is not empty but has a size of 20 (contains 20 elements) and you push 2 elements to the back, it now contains 22 elements. But the new elements are not placed at indices 19 and 20, but 20 and 21.

If you really want to only reserve enough memory for the vector to hold 20 elements (without actually containing any elements), to prevent costly reallocations, then you should call

std::vector<int> myVector;
myVector.reserve(20);

In this case the vector is still empty, but it has enough memory to add at least 20 elements (using push_back, for example) without needing to reallocate its internal storage. In this case the vector only contains the 2 elements you pushed_back.

Solution 5

push_back will increase the capacity of the vector to at least the new size of the vector, but possibly (i.e. probably) somewhat larger.

Because push_back is required to run in O(1) amortized time, each reallocation will be to some multiple of the old capacity. In a typical implementation that multiple is 2.

But the exact capacity increase is not specified. If you require precise control over the capacity, use reserve.

...

Re-reading your question, I am not sure you understand the difference between a vector's size and its capacity. The size is the number of elements. The capacity is the number of elements the vector can hold without performing a reallocation. That is, you can push_back capacity()-size() elements before a reallocation happens.

In your example, 5 and 14 will appear at myVector[20] and myVector[21], respectively.

View more solutions

Comments

[iaacp]

Right. What I didn't understand is that vectors dont require a capacity when creating them, that's they're point - they're dynamic, right? So it's kind of pointless to give them an initial capacity.

[In silico]

Note that C++03 standard 23.2.4/1 requires that vectors "support (amortized) constant time insert and erase operations at the end", so in practice the capacity usually expands by a factor of two when push_back() needs more room.

[iaacp]

Okay, so push_back doesn't increase the capacity, right? Unless that vector is already at full capacity.

[iaacp]

Very helpful, thank you. Essentially what I want to do is create a vector, and only add elements to the end. It didn't occur to me that I don't even have to give a size initially, because vectors are dynamic. Thank you!

[In silico]

@iaacp: No, it's not pointless. If you know in advance how much stuff you plan to put inside the vector, but you don't have the actual stuff on hand when initializing the vector, then you can reserve() an amount so that the vector will not have to do any reallocation.

[iaacp]

Alright. Thank you. I didn't know it would fill with 20 0's. That would have really messed my program up. I don't know why I didn't think to just not specify a size, seeing as how they're dynamic and that's what I need. A derp on my behalf.

[Nemo]

@iiacp: It is not pointless if you actually care about reallocation. Reallocation (a) takes time and (b) invalidates references/pointers to elements inside the vector. reserve lets you set the capacity to avoid future reallocations. Note that your example sets the size of the vector, not the capacity. You are creating a vector of 20 uninitialized integers.

[Max Lybbert]

Correct, it doesn't necessarily increase the capacity. I only mention it because std::vector goes through the trouble of making the distinction so it's important to keep the terms straight, especially when reading documentation for std::vector.