C++ Internals :: STL vector, Part I

Greetings, folks.

Update 10/Aug/2015: Due to some confusion caused by useless usages of trailing return types (auto main() -> int) I've decided to get rid of it. Also for (auto item : { 1, 2, 3, 4, 5, 6, 7, 8, 9 }) was replaced by a classical one for (int i = 1; i < 10; i++).

Update 08/Aug/2015: Due to great comments and suggestions received from this Reddit post I made couple improvements:

  • images related to std::vector's definition and insertion procedure were significantly reworked - I hope now they provide more accurate and meaningful information

  • I put additional notes on at() method.


Today is a great day to disembowel something. How's about a well-known std::vector? You think there is nothing more you can learn about it? Believe me, you're wrong.

In this series of three articles we are going to check:

  • what is std::vector and how it works (suppress a yawn)
  • vector's growth factor
  • VC++ Debug's "aux object"
  • new C++11's methods
  • miscellaneous things

OS: Windows 8 x64, CentOS 7 x64
Compilers: MSVS Community Edition 2013 Update 4, GCC 5.2.0, Clang 3.6

std::vector

std::vector is the most famous sequence container in C++ world that encapsulates dynamic size arrays. Other sequence containers you might be aware of are std::forward_list (since C++11), std::list, std::deque and std::array (since C++11). But the scope of this article is std::vector. So, let's get started.

The items in std::vector are stored contiguously in memory:

Figure 1. std::vector definition

That's why std::vector is fully compatible with old style C-arrays:

  • you can use offsets on pointers to items instead of iterators (pointer arithmetics works fine)
  • you can pass &arr[0] to a C function accepting a pointer (ptrArr*) and expect it to work.

The second thing that std::vector implements and which makes it C-friendly (the first one is contiguous memory locations for items) is a possibility to use square brackets [] to address a single item. std::vector makes this available by implementing operator[] special method which, however, doesn't check for boundaries. This is understandable (due to compatibility) but obviously dangerous. More C++ way to get an access to an item is at() method (you should be using this one), which in turn does make an index check.

Update [08/Aug/2015]: To be honest, I personally don't use at() method and advising to use it in such a categorical manner - using the words like should be - is at least unfair. Not paying enough attention to whether your indexes are good and whether you are certain about them, but instead relying on at() method in array index validation is a bad practice or habit. In other words, at() method is not your savior. You should be certain about what your program does and why it behaves in such a way.


All the ways you can put std::vector in your code:

#include <vector>
#include <string>

int main(int argc, char** argv)  
{
    // Explicitly defined item and allocator types
    std::vector<float, std::allocator<float>> vec1;

    // Initializer syntax
    std::vector<int> vec2 { 11, 22, 33, 44, 55 };

    // Create 10 empty string (initialized with value = T())
    std::vector<std::string> vec3(10);

    // Create 10 items and initialize it with value 55
    std::vector<int> vec4(10, 55);

    // Fill vector using reverse iterator
    std::vector<int> vec5(vec2.rbegin(), vec2.rend());

    // Using copy constructor
    std::vector<int> vec6 = vec5;

    return 0;
}


Let's see how the std::vector allocates space for new items.

As a consequence of its requirement (all items have to be placed contiguously in memory), std::vector can't allocate a memory just for the new element - item's location should be adjacent to each other:

Figure 2. Adding new element in a std::vector which has a free space reserved previously

But why it can't? Assume that such an operation (allocate new adjacent memory cell without worrying about other elements) could indeed be performed by the vector. How, in that case, does it know whether or not the next adjacent memory cell is free and was not just occupied by another processor long time ago? There is no way (or they are too way hard and unrealistic) for a vector to do that properly. Thus, no choice left, the vector has to reallocate the place for all items it already has plus additional one.

That's quite an expensive operation (involves new memory allocation, old memory destruction and copy overhead), that's why std::vector allocates a space for future use, maintaining a property called capacity.

Capacity is the number of items that can be fit into existing memory storage without performing reallocation in memory. Once the number of items stored in vector exceeds its capacity, a vector increases the capacity value and perform mentioned reallocation procedure.

Due to performance reasons, the capacity value isn't just incremental (it isn't being increased each time new items are added - too damn expensive and make no sense at all).

Update [08/Aug/2015]:

Quote:

in fact, arithmetic growth (e.g. +10 when running out of capacity) is forbidden by the Standard because it leads to quadratic complexity. Geometric growth is mandated.

Example: imagine you have a vector that adds +1 to capacity value each time it needs reallocation; now calculate how many times 1000 items (that are being inserted one by one) will be copied before the operation ends? I'll give you a clue: first items will be copied 999 times, second - 998 times, etc. Got it? Yes, here we have quadratic complexity.


Instead, std::vector multiplies the capacity value by the growth factor and allocates memory of that size. Just for now assume the growth factor is equal to 1.5 (we'll figure out why later), so the vector increases in half its storage each time the size exceeds internal capacity.

Consider, for example, the following program. It's required to insert nine numbers into a vector. This causes 6 memory reallocations:

#include <vector>
#include <iostream>

int main()  
{
    // Size and capacity equal to 0
    std::vector<int> dyn_arr;

    // Fill vector with values
    for (int i = 1; i < 10; i++)
    {
        dyn_arr.push_back(x * x);
        std::cout << 
            "Size: " << dyn_arr.size() << "; " << 
            "Capacity: " << dyn_arr.capacity() << '\n';
    }

    return 0;
} 

Result:

1st allocation
Size: 1; Capacity: 1

2nd allocation
Size: 2; Capacity: 2

3rd allocation
Size: 3; Capacity: 3

4th allocation
Size: 4; Capacity: 4

5th allocation
Size: 5; Capacity: 6
Size: 6; Capacity: 6

final allocation
Size: 7; Capacity: 9
Size: 8; Capacity: 9
Size: 9; Capacity: 9

Quite clear, isn't it?

Growth Factor

Let's talk about growth factor and how it is defined.

Main question is why can't we take any appropriate (not big though) number (>= 2) as a multiplier and end discussion right here? There is a reason for that.

Each time a vector allocates new memory (we consider exclusively about first-fit allocation here) and frees the old one, it leaves the gaps in memory which would be reasonable to fill later. And if the vector grows too fast (coefficient greater or equal to 2 is considered fast) it will always be too big to fit in to available memory. The memory that was "left behind".

So, we should carefully decide which coefficient better balances between memory utilization and expansion efficiency.

What follows is partially based on great discussion raised at comp.lang.c++.moderated thread. You definitely should go though it.

Assume, initially std::vector has size S, here is a picture of what happens after few reallocations happen.

Figure 3. Simplified view on growth factor

If we wouldn't have such a case, where old memory is kept until the new one arrives, we could calculate the coefficient - in order for $f*f*S$ to be fitted into previously allocated memory it should be less than or equal to:

$f*f*S <= S + f*S$

As long as S is always greater than 0, we get are to get rid of it by dividing by it.

$f*f <= 1 + f$
$f^2 - f - 1 <= 0$

Solving quadratic equation we get:

$f <= \frac{1 + \sqrt{5}}{2}$
or
$f <= 1.6$

Which, BTW, happens to be a golden ratio (Fibonacci growth is exponential growth with an exponent of $\frac{1 + \sqrt{5}}{2}$).

Next, as we can't touch memory occupied by our vector (say, a memory region of size $f^n*S$), a minor edit is required to be done - we have to be sure that all memory left from all the previous ($S+f*S + f^2*S + ... + f^{n-1}*S$) reallocations will be large enough to fit a region of size $f^{n+1}*S$ (recall, $f^n*S$ is unavailable):

$S+f*S+f^2*S+...+f^{n-1}*S >= f^{n+1}*S$

And the figure:

Figure 4. Growth factor in real life

I found a relevant text from facebook/folly dedicated to inequality we've just defined:

If some number n satisfies that equation, it means you can reuse memory after n reallocations. The graphical solver below reveals that choosing k = 1.5 (blue line) allows memory reuse after 4 reallocations, choosing k = 1.45 (red line) allows memory reuse after 3 reallocations, and choosing k = 1.3 (black line) allows reuse after only* 2* reallocations.

Figure 5. Choosing correct coefficient

Although the same coefficient ($\frac{1 + \sqrt{5}}{2}$) also is being used even in slightly modified conditions, still there are some subtleties that must be mentioned. Quote from the same thread:

  • Constant allocation overhead in every block
  • Populating the grown vector may pollute free store with allocations that the straightforward calculation doesn't take into account (typically in a rate that grows at the same speed with the size of the vector)
  • Attempts to reuse too large of a portion of the already deallocated memory will render the algorithm useless after the first application of this optimization, because the algorithm itself will then have polluted the ideal free store

It would be interesting to know that MSVS 2013 finally uses factor of 1.5 (vector:l:1570):

size_type _Grow_to(size_type _Count) const  
{
    // grow by 50% or at least to _Count
    size_type _Capacity = capacity();

    _Capacity = max_size() - _Capacity / 2 < _Capacity
        ? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%

    if (_Capacity < _Count)
        _Capacity = _Count;

    return (_Capacity);
}


Whereas modern GCC 5.2.0 and Clang 3.6 get stuck on, surprisingly, 2.

That's one of the reason why Facebook guys decided to create its own implementation called fbvector. It's available within their open-source C++ library folly.

Member Functions

OK, let's take a closer look at some specific methods std::vector has. You already know about size() and capacity(). The other two that go side by side are resize() and reserve(). Let's recheck them all:

  • size() - returns the number of existing elements in the container
  • resize() - resizes the container to store more items. Changes size property. If capacity is smaller than the new size, it becomes equal to new value. Otherwise it isn't changed.
  • capacity() - returns the number of elements that the container has allocated space for
  • reserve() - increase the capacity of the container. Isn't being changed if new value is less than the old one.

Example:

#include <vector>
#include <iostream>

int main()  
{
    // size and capacity equal 0
    std::vector<int> dyn_arr { 34, 55, 89, 144, 233, 377, 610, 987, 1597 };

    auto print_sizes = [&dyn_arr]() {
        std::cout 
            << "Size: " << dyn_arr.size() << "; "
            << "Capacity: " << dyn_arr.capacity() << '\n';
    };

    // Increases capacity too
    // Size: 99; Capacity: 99
    dyn_arr.resize(99);
    print_sizes();

    // Capacity stays the same
    // Size: 3; Capacity: 99
    dyn_arr.resize(3);
    print_sizes();

    // Size: 10; Capacity: 99
    dyn_arr.resize(10);
    print_sizes();

    // Doesn't decrease the capacity
    // Size: 10; Capacity: 99
    dyn_arr.reserve(5);
    print_sizes();

    // Size: 10; Capacity: 500
    dyn_arr.reserve(500);
    print_sizes();

    return 0;
}


You might be interested, how can we decrease container's size/capacity to lower the memory usage if passing low values in reserve() and resize() above don't cause capacity changes?

Looking though the list of std::vector member functions you might have noticed one function clear() that, as you might have thought, is intended to solve our problem. Does it? No, having invoked clear() method doesn't reduce the size/capacity values! It just removes the items.

Example:

#include <vector>
#include <iostream>

int main()  
{
    std::vector<int> dyn_arr{ 34, 55, 89, 144, 233, 377, 610, 987, 1597 };

    auto print_sizes = [&dyn_arr]() {
        std::cout 
            << "Size: " << dyn_arr.size() << "; "
            << "Capacity: " << dyn_arr.capacity() << '\n';
    };

    // Size = 9; Capacity = 100;
    print_sizes();

    // Size = 100; Capacity = 100;
    dyn_arr.resize(100);
    print_sizes();

    // No capacity change here!
    // Size = 0; Capacity = 100;
    dyn_arr.clear();
    print_sizes();
}


We have two options here:

#1. Create new std::vector and copy there all items from the old one (swap trick)

#include <vector>
#include <iostream>

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

    auto print_sizes = [&dyn_arr]() {
        std::cout
            << "Size: " << dyn_arr.size() << "; "
            << "Capacity: " << dyn_arr.capacity() << '\n';
    };

    dyn_arr.reserve(100);
    dyn_arr.insert(begin(dyn_arr), { 34, 55, 89, 144, 233, 377, 610, 987, 1597 });

    // Size = 9; Capacity = 100;
    print_sizes(dyn_arr);

    // Do a swap
    std::vector<int>(dyn_arr).swap(dyn_arr);

    // Size = 9; Capacity = 9;
    print_sizes(dyn_arr);
}


Trick is simple: we create a temporary vector object, initialize it with values in old vector - new vector has "valid" capacity - and then do a swap.

#2. Use C++11's new method - shrink_to_fit(), which reduces memory usage by freeing unused memory:

#include <vector>
#include <iostream>

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

    auto print_sizes = [&dyn_arr]() {
        std::cout
            << "Size: " << dyn_arr.size() << "; "
            << "Capacity: " << dyn_arr.capacity() << '\n';
    };

    dyn_arr.reserve(100);
    dyn_arr.insert(begin(dyn_arr), { 34, 55, 89, 144, 233, 377, 610, 987, 1597 });

    // Size = 9; Capacity = 100;
    print_sizes(dyn_arr);

    // Do a swap
    dyn_arr.shrink_to_fit();

    // Size = 9; Capacity = 9;
    print_sizes(dyn_arr);
}


Having in mind all the methods mentioned above, you can ask why do we have reserve() functions if pushing items causes a container to grow itself anyway? The answer is simple: it's useful when you know the number of items or the range of the items the vector is expected to work with.

That's all for the first part. Stay tuned!

Sergei Danielian

Read more posts by this author.

Vladivostok, Russia