Greetings, folks.

Update 05/Aug/2015: I put a link on reddit and received a lot of useful comments and fixes, so updates will be provided soon.

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. Simplified 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 a pointer to item in any function that accepts pointer to array type

The second thing that std::vector implements and which makes it C-friendly (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 [05/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 indeces 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 saviour. You should be certain about what your program does and why it behaves in such a way.

Let's recall all the ways you can put std::vector in your code.

#include <vector>
#include <string>

auto main(int argc, char** argv) -> int  
{
    // 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 a 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. Inserting new item in std::vector

But why it can't? Assume that such an operation (alocate 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 vector to do that properly. Thus no choice left, vector has to reallocate the place for all items it already has plus additional one.

That's quite 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 exceed 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). 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>

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

    // Fill vector with values
    for (auto x : { 34, 55, 89, 144, 233, 377, 610, 987, 1597 })
    {
        dyn_arr.push_back(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. Picking right coeffient

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>

auto main() -> int  
{
    // 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>

auto main() -> int  
{
    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>

auto main() -> int  
{
    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>

auto main() -> int  
{
    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!