Tuesday, January 23, 2007

Vector's size and capacity

Are you confused with vector's two member functions namely size() and capacity? Don't be.

size() is related to the number of elements currently in a vector object. It has no relation to memory management internally taken care of by the vector (well there is but that's not a direct relation and you will understand that better as you proceed ahead with this post).

On the contrary, capacity() is directly affected and is directly related to vector's memory management.

Consider vector to have an internal array that it maintains to hold elements. Not all locations of the array can be occupied by elements or refer to valid constructed objects. The total size of that array is called and referred to as vector's capacity. And the total number of elements constructed and being currently held in that array is called and referred to as size().

When all the void places of the array get utilized to keep multiple objects and you add one more element to that collection, you will see that the capacity increases (probably twice the last value, I say "probably" because it is an implementation detail, the standard does not mandate it and hence the factor can vary from one STL implementation to another) but size will only increase by 1.

Its like size() <= capacity(). This will never be untrue for any correct standard vector implementation. Implementations may have a default capacity (8 or 16 elements holding power minimum) and you can't go below that even with the shrink-to-fit technique to empty the vector container object. There may be STL implementations where there might not be any minimum capacity limit and you might see a non-zero positive capacity for an empty vector object (even though it does not have any elements i.e. size() would return 0). There is nothing wrong with that though, since it is something that is implementation defined by the C++ standards. To test what I said, you may write a small test program where you can verify the size() and capacity relationship : size() being always <= capacity. You can keep inserting about 100 elements in the vector and see how each push back affects the size() and capacity() both. A small note on vector member function reserve(): when you do reserve() for any "N" (positive integral value) elements - the capacity is guaranteed to be >= N, not less than that. And if "N" is lower than the current capacity of the vector object it is invoked on then the capacity remains unchanged.

That is all there is to it as far as the distinction between size() and capacity() is concerned.

More, later! Have a great time!


Leixir said...

A C++ starter used this as a reference since cplusplus.com didn't explain it clearly.


In A Digital Age said...

Hey thanks for explaining the typical implementations of capacity. I'm making my own vector class for a computer science class and I was having a lot of trouble finding out how must compilers implemented the capacity member.