C++ Internals :: STL vector, Part III

Greetings, folks.

Update 22/Aug/2015: I updated the section Iterators Debugging Facilities in MSVC by adding a class layout for an empty class inheriting from std::vector<float>. Now you will have a whole picture of how inner classes (_vector_alloc, _Container_base_12, etc.) construct the std::vector entity.

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++).


This is the third article in STL Vector Internals series.

  • First part was about std::vector's definition, its growth factor and some special methods it has;
  • Second part told us about iterators and emplace methods and its implementation.

This part is the final one. We are going:

  • to see how one can provide a custom allocator and use it to get details about how std::vector allocates new memory;
  • dive into the deeps of std::vector implementation by learning classes hierarchy and finding out what kind of debugging support STL provides for iterators security checkings;
  • check a few third-party vector implementations.

Let's get started.

Using Custom Allocator

Recall std::vector's constructor signature:

template<class T, class Allocator = std::allocator<T>> class vector;

Pay attention to the second template parameter Allocator and its default argument std::allocator<T>. Allocator is an important component that defines a policy of allocating new elements of type T within std::vector class.

It's not that common to provide your own Allocator implementation, but, say, for game developers or embedded engineers this is a way to adapt STL's data structure to their needs. They basically have two options: 1) using slightly modified allocation strategy by providing custom Allocator type (stack-based or pool allocators are examples) or 2) using completely custom implementation of a data structure.

This section aims at showing you how the vector allocates a new space. You already know much of the theory behind the process (growth, reallocation, etc.), but wouldn't it be more interesting to investigate further, to see the numbers? We'll consider two implementations - MSVS 2013 Update 4 and GCC 5.2.0.

To perform the observations, we need to provide custom Allocator implementation that std::vector is fully compliant with. To do so, we must provide specific methods. What are they exactly you can find in the section 17.6.3.5 Allocators, specifically in Table 28 — Allocator requirements of the C++ standard.

I won't stay too long here, as memory allocation is out of scope of the article (stay tuned for future ones), so I already made it for you (you can find the implementation here, check for simple_allocator header-only class). We'll use it for tracking std::vector's memory allocations:

#include <vector>
#include <iterator>
#include <iostream>
#include "simple_allocator.hpp"

int main()  
{
    std::cout << "Create a vector" << '\n';
    // Use our custom allocator
    std::vector<int, simple_allocator<int>> numbers;

    std::cout << '\n' << "Insert items" << '\n';

    for (int i = 1; i < 10; i++)
    {
        bool is_print{};
        if (numbers.size() == numbers.capacity())
            is_print = true;

        numbers.push_back(i);

        if (is_print)
            std::cout << 
                "Size: " << numbers.size() << "; " << 
                "Capacity: " << numbers.capacity() << "\n\n";
    }

    std::cout << "Deleting items and vector" << "\n\n";

    return 0;
}

Please note, we track only how vector allocates items (for its internal dynamic array) and not how many bytes the vector itself is occupied in memory.

Here is what happened with Debug build in MSVS 2013:

Create a vector  
Allocating 1 object of size 8.  
Allocation has been completed at 00FAA398

Insert items  
Allocating 1 object of size 4.  
Allocation has been completed at 00FAAE68  
Size: 1; Capacity: 1

Allocating 2 objects of size 4.  
Allocation has been completed at 00FAAEA8  
Deallocating 1 object of size 4.  
Size: 2; Capacity: 2

Allocating 3 objects of size 4.  
Allocation has been completed at 00FAAEF0  
Deallocating 2 objects of size 4.  
Size: 3; Capacity: 3

Allocating 4 objects of size 4.  
Allocation has been completed at 00FAAE68  
Deallocating 3 objects of size 4.  
Size: 4; Capacity: 4

Allocating 6 objects of size 4.  
Allocation has been completed at 00FAAEB8  
Deallocating 4 objects of size 4.  
Size: 5; Capacity: 6

Allocating 9 objects of size 4.  
Allocation has been completed at 00FAAF10  
Deallocating 6 objects of size 4.  
Size: 7; Capacity: 9

Deleting items and vector

Deallocating 9 objects of size 4.  
Deallocating 1 object of size 8.  


These verify what you already know (reallocation process, the order of allocation/deallocation, sizes, etc.). But there is one interesting fact here. Compare output with Release-MSVS and GCC/Clang builds:

Create a vector

Insert items  
Allocating 1 object of size 4.  
Allocation has been completed at 0x1e8bc20  
Size: 1; Capacity: 1

Allocating 2 objects of size 4.  
Allocation has been completed at 0x1e8bc40  
Deallocating 1 object of size 4.  
Size: 2; Capacity: 2

Allocating 4 objects of size 4.  
Allocation has been completed at 0x1e8bc20  
Deallocating 2 objects of size 4.  
Size: 3; Capacity: 4

Allocating 8 objects of size 4.  
Allocation has been completed at 0x1e8bc60  
Deallocating 4 objects of size 4.  
Size: 5; Capacity: 8

Allocating 16 objects of size 4.  
Allocation has been completed at 0x1e8bc90  
Deallocating 8 objects of size 4.  
Size: 9; Capacity: 16

Deleting items and vector

Deallocating 16 objects of size 4.


See the difference? MSVS compiler allocates additional space (8 bytes) for the vector in Debug mode. That is a pointer that refers to an object known to be called "the aux object" and here is a decent explanation from Stephan T. Lavavej about its origin (to read full story refer to this link):

The _HAS_ITERATOR_DEBUGGING functionality was provided by Dinkumware ... The _SECURE_SCL functionality was added by Microsoft, in order to improve the security of programs running on Windows. In order to perform their checks, both _HAS_ITERATOR_DEBUGGING and _SECURE_SCL make iterators contain additional data members, such as pointers to their parent containers. _HAS_ITERATOR_DEBUGGING, because it is enabled by default in debug mode (and not obtainable in release mode), also builds singly linked lists that allow containers to refer to all of their iterators. ...

_SECURE_SCL, because it is enabled by default in release mode, strives to impose minimal performance penalties. Therefore, when it is enabled, although iterators have pointers back to their containers, containers don't have pointers to their iterators. (Updating "iterator lists" is too time-consuming for release mode.)

Now, VC8 RTM/SP1 (Visual Studio 2005) had a bug when _HAS_ITERATOR_DEBUGGING was disabled and _SECURE_SCL was enabled (e.g. the default for release mode). When you have persistent iterators into two containers, and then swap the containers, the Standard requires that the iterators remain valid. Unfortunately, the parent pointers that _SECURE_SCL added to iterators were broken by such a swap. ... Dinkumware's _HAS_ITERATOR_DEBUGGING is immune to this problem since it can walk the iterator lists and update all of the parent pointers. This option is not available to _SECURE_SCL.

In order to fix this conformance bug, The Swap Fix in Orcas makes every Standard container own an additional dynamically allocated object, imaginatively called "the aux object". Each container holds a pointer to its aux object, which holds a pointer back to the container. Each iterator, instead of holding a pointer directly to its parent container, now holds a pointer to its parent container's aux object.

All that is enough to basic understanding some specifics of MS's std::vector implementation, but if you want to get a more deep understanding, next section is at your service. Otherwise, you're free to skip it and move straightforward to the overview of the third-party implementations of the STL.

Iterators Debugging Facilities in MSVC

The aforementioned quote brings into the scope a few macros: _ITERATOR_DEBUG_LEVEL and _SECURE_SCL. Let's find out what for were these things created. According to MSDN, the main reason is to make the libraries that ship with Visual C++ and iterators and algorithms more secure.

However, you won't be able to notice _ITERATOR_DEBUG_LEVEL or _SECURE_SCL in STL code anymore, because starting from Visual Studio 2010 they were replaced by the new _ITERATOR_DEBUG_LEVEL (IDL) macro, which supersedes and combines the functionality of the _SECURE_SCL (SCL) and _HAS_ITERATOR_DEBUGGING (HID) macros.

So, let's briefly get familiar with those obsoletes macros and find out how they are superseded the new one. Strict definition took from MSDN:

  • _SECURE_SCL (SCL) - defines whether Checked Iterators are enabled. If defined as 1, unsafe iterator use causes a runtime error and the program is terminated. If defined as 0, checked iterators are disabled. Checked Iterators, in turn, ensure that the bounds of your container are not overwritten.

  • _HAS_ITERATOR_DEBUGGING (HID) - Defines whether the iterator debugging feature is enabled in a debug build. The iterator debugging feature detects incorrect iterator use, and asserts and displays a dialog box at run time.

Sounds pretty much the similar, doesn't it?

Before IDL appeared (in MSVS 2012), HID had been turned on in MSVS 2005/2008 Debug mode and only in that mode, whereas SCL had been turned on in MSVS 2005/2008 Release mode and available in Debug mode. However, in Debug mode, HID supersedes SCL.

HID's main goal was to provide strong correctness check to detect STL misuses (access items out of container range, access invalidated iterators).

SCL - Release mode feature - behaves very aggressively: if it identifies potentially dangerous behavior in your program, it kills it. The reason for that is to avoid vulnerability exploit. So,SCL is for security check.

As a note, the possible values of the SCL and HID macros are:

  • SCL=0 - Disables checked iterators
  • SCL=1 - Enables checked iterators
  • HID=0 - Disables iterator debugging in debug builds
  • HID=1 - Enables iterator debugging in debug builds

There is no SCL or HID macro now, instead, IDL unifies them and has the following values depending on mode:

Release: IDL = 0 Debug: IDL = 2

And here is how you can decypher the value:

IDL = 0 (Default for Release): SCL=0, HID=0
IDL = 1: SCL=1, HID=0
IDL = 2 (Default for Debug): SCL=(does not apply), HID=1

All related preprocessor things happen in yvals.h file:

#ifdef _ITERATOR_DEBUG_LEVEL /* A. _ITERATOR_DEBUG_LEVEL is already defined. */
    /* A1. Validate _ITERATOR_DEBUG_LEVEL. */
    ...
    /* A2. Inspect _HAS_ITERATOR_DEBUGGING. */
    #ifdef _HAS_ITERATOR_DEBUGGING /* A2i. _HAS_ITERATOR_DEBUGGING is already defined, validate it. */
        #if _ITERATOR_DEBUG_LEVEL == 2 && _HAS_ITERATOR_DEBUGGING != 1
            #error _ITERATOR_DEBUG_LEVEL == 2 must imply _HAS_ITERATOR_DEBUGGING == 1 .
        #elif _ITERATOR_DEBUG_LEVEL < 2 && _HAS_ITERATOR_DEBUGGING != 0
            #error _ITERATOR_DEBUG_LEVEL < 2 must imply _HAS_ITERATOR_DEBUGGING == 0 .
        #endif
    #else /* A2ii. _HAS_ITERATOR_DEBUGGING is not yet defined, derive it. */
        #if _ITERATOR_DEBUG_LEVEL == 2
            #define _HAS_ITERATOR_DEBUGGING 1
        #else
            #define _HAS_ITERATOR_DEBUGGING 0
        #endif
    #endif /* _HAS_ITERATOR_DEBUGGING */
    /* A3. Inspect _SECURE_SCL. */
    ...
#else /* B. _ITERATOR_DEBUG_LEVEL is not yet defined. */
    /* B1. Inspect _HAS_ITERATOR_DEBUGGING. */
    ...
    /* B2. Inspect _SECURE_SCL. */
    ...
    /* B3. Derive _ITERATOR_DEBUG_LEVEL. */
    ...
#endif /* _ITERATOR_DEBUG_LEVEL */

Now, as we got into what all these things mean, it's time to reveal our aux object.

But before doing that let's see how the checking work (it's interesting, right?).
Consider example:

#include <vector>
#include <iostream>

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

    for (int i = 1; i < 4; i++)
        numbers.push_back(i + 100);

    // At this point, size = capacity = 3
    auto it = numbers.end();
    std::advance(it, -2);

    std::cout << *it << std::endl;

    return 0;
}


Will print 102 as expected. Now, let's cause iterator invalidation by letting the vector reallocates its data:

#include <vector>
#include <iostream>

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

    for (int i = 1; i < 4; i++)
        numbers.push_back(i + 100);

    // At this point, size = capacity = 3
    auto it = numbers.end();
    std::advance(it, -2);

    std::cout << *it << std::endl;

    // Inserting an item causes reallocation
    numbers.push_back(777);

    return 0;
}

Compile and run it.

Figure 1. Debug message window showing that we failed while working with iterators

Boom! vector iterator not dereferenceable. It's quite useful - now you know what kind of error you did. By default, _ITERATOR_DEBUG_LEVEL = 2, that's why we were warned. Try to define IDL = 1 and run the program again:

102  
-17891602

No checking - no warnings! Program just silently prints a garbage and finishes its execution. Although you get a free access to those macros I suggest not playing with them unless you really need it.

Ok, finally, going back to the aux object.

In order to be able to perform the validation, it's required to get additional knowledge about what's happening with a vector:

  • has it just gone over resize procedure and
  • how many iterators pointing to the vector's data exist.

The latter is the hardest one - there is no way to know how many iterators were created and there are no tools available to fix them once the reallocation happened.

However, this can be archived by modifying an STL object - adding additional members (this was mentioned in the quote above). Assuming we use default values for IDL, an STL container (vector in our case) receives two more pointers: a pointer to a proxy object (we'll see it a bit later in code) and a pointer to a linked list of iterators.

A picture costs a thousand words, so, the figure below shows how vector and iterator classes are represented with IDL equal 0:

Figure 2. Vector and iterator classes cooperation without debug information

They look pretty simple. Now, if we turn on all the debug stuff, the picture will be changed:

Figure 3. Vector and iterator classes cooperation with debug information

Important Note: don't be confused by the fact that the Back pointer from _Container_proxy object doesn't refer to the std::vector directly, but instead points to _Container_base12 object which is a part of std::vector in Debug mode. That's all about how Base classes relate to Derived ones and from the memory organization point of view. Also, I put a _Container_base_12 object under _Myfirst, _Mylast and _Myend members, which is not quite correct (the earliest Bases lie earlier in object's memory representation), but this allows me to draw more comprehensible picture. So, please, forgive my familiarity.

Note: our mystery beast - the aux object - has been unveiled. It's just a _Container_proxy class instance.

Although, the figure above looks a bit complicated, it clearly shows that:

  • iterators now can get a knowledge about the parent container - where it lives
  • a vector instance now knows about their iterators.

All that helps to perform a complex iterators validation. For additional help for those who are going to investigate even further, here is a simplified class hierarchy diagram:

Figure 4. Vector/Iterator classes hierarchy

Now as you have a deep knowledge of how vectors work, let me harden this by providing code excerpts (vector and xutility files) and highlight those places you can start digging into from.

  • How _Container_base/_Iterator_base becomes either _Container_base0/_Iterator_base0 or _Container_base12/_Iterator_base12 accordingly (xutility:l:244):
 #if _ITERATOR_DEBUG_LEVEL == 0
typedef _Container_base0 _Container_base;  
typedef _Iterator_base0 _Iterator_base;

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
typedef _Container_base12 _Container_base;  
typedef _Iterator_base12 _Iterator_base;  
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */
  • How the proxy object is being created (vector:l:620):
void _Alloc_proxy()  
{
    // construct proxy from _Alval
    typename _Alty::template rebind<_Container_proxy>::other _Alproxy;
    this->_Myproxy = _Alproxy.allocate(1);
    _Alproxy.construct(this->_Myproxy, _Container_proxy());
    this->_Myproxy->_Mycont = this;
}
  • How the dereference operator works (vector:l:64):
    reference operator*() const
        {    // return designated object
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (this->_Getcont() == 0
            || this->_Ptr == 0
            || this->_Ptr < ((_Myvec *)this->_Getcont())->_Myfirst
            || ((_Myvec *)this->_Getcont())->_Mylast <= this->_Ptr)
            {    // report error
            _DEBUG_ERROR("vector iterator not dereferencable");
            _SCL_SECURE_OUT_OF_RANGE;
            }

 #elif _ITERATOR_DEBUG_LEVEL == 1
        _SCL_SECURE_VALIDATE(this->_Getcont() != 0);
        _SCL_SECURE_VALIDATE_RANGE(
            this->_Ptr != _Tptr()
            && ((_Myvec *)this->_Getcont())->_Myfirst <= this->_Ptr
            && this->_Ptr < ((_Myvec *)this->_Getcont())->_Mylast);
 #endif /* _ITERATOR_DEBUG_LEVEL */

        _Analysis_assume_(this->_Ptr != _Tptr());

        return (*this->_Ptr);
        }

Let's decompose these bunch of checks under the #if _ITERATOR_DEBUG_LEVEL == 2 section:

First, this->_Getcont() == 0

The condition checks if the iterator has a container. this represents an iterator of type _Iterator_base12, thus it has a _Myproxy object pointing to _Container_proxy which in turn has a _Mycont member which points to the parent container. _Getcont() returns a proxy object:

const _Container_base12 *_Getcont() const  
{
        // get owning container
    return (_Myproxy == 0 ? 0 : _Myproxy->_Mycont);
}

Next, this->_Ptr == 0

Simply checks if a pointer to an element in a vector is valid.

Finally, this->_Ptr < ((_Myvec *)this->_Getcont())->_Myfirst || ((_Myvec *)this->_Getcont())->_Mylast <= this->_Ptr

Checks if the pointer is within bounds.

Pretty simple once you get into it. BTW, notice that without IDL macro the pointer is being dereferenced without any checks:

return (*this->_Ptr);

Decomposition is done!

Update 22/Aug/2015:

Last thing I wanted to show is std::vector's class layout representation. In order to do this you have to create a class inheriting std::vector and use undocumented /d1reportSingleClassLayoutYourClassName compiler switch (pay attention to YourClassName part).

Here is a empty class saved in Source.cpp file:

#include <vector>

class MyVector : std::vector<float>  
{};

int main()  
{}


And that's how we get a class layout in Debug:

cl /nologo /W4 /MTd /d1reportSingleClassLayoutMyVector Source.cpp | msvcfilt

Figure 5. Vector class layout representation. Debug mode

and Release mode:

cl /nologo /W4 /MT /d1reportSingleClassLayoutMyVector Source.cpp | msvcfilt

Figure 6. Vector class layout representation. Release mode

You can see how all the classes work together in order for std::vector to behave as it does. Note that in Debug mode the lowest base class is, indeed, _Container_base12 as opposed to Release, when it is _Container_base0.

BTW, do you remember that important note (about class members position) I made for figure 3? That's what I was talking about: _Myproxy is located before other members.

Regarding msvcfilt command. By default, /d1reportSingleClassLayoutMyVector produces decorated names (so-called name mangling). To convert them into readable form, you can use built-in undname utility:

G:\Projects\ClassLayoutTest>undname ?$vector@MV?$allocator@M@std@@  
Microsoft (R) C++ Name Undecorator  
Copyright (C) Microsoft Corporation. All rights reserved.

Undecoration of :- "?$vector@MV?$allocator@M@std@@"  
is :- "vector<float,class std::allocator<float> >"  


The reason I use msvcfilt instead is that undname doesn't work with input stream.

Note: if you have issues invoking MS's cl command, running %MSVSROOT%\VC\vcvarsall.bat prepares correct MSVS environment for you.


That's all for this section. In addition, I'd like to recommend 3rd lecture of Stephan T. Lavavej's Advanced STL course available on Channel 9:

  • to learn more details about how STL maintains internal debugging structures (proxy object and iterators linked list) and
  • to see more examples and code clarifications.

Third-Party implementations

Now it's interesting to check other vector container implementations. But before I continue I have to make a statement: I've never tested undermentioned containers in terms of space/time consumption versus std::vector and I've never verified what they claim they can do versus what they really can and how they do this. So it's up to you whether trust-and-use or test-decide-and-use scheme will work for you. What follows is a short overview.

facebook\folly

An open-source C++ library developed and used at Facebook

include header: folly/FBvector.h

requirements: GCC 4.8+; Boost compiled with C++11 support.

features:

  • Growth factor is 1.5
  • Scalable memory allocation using jemalloc
  • Object Relocation: provides a trait (folly::IsRelocatable) to mark an object as being relocatable
  • Aims at further improvements in raw memory copying promoting the collaboration with jemalloc

More info at wiki page.

uSTL

Partial implementation of the C++ standard library that focuses on decreasing the memory footprint of user executables.

include header: ustl/uvector.h

requirements: GCC 4.6 / Clang 3.2

features:

  • provides additional macros: container iteration (foreach/eachfor), alignment ()
  • aggregation of all memory management in one place (memblock class) and specific memory management mechanism:

    The uSTL way is to manage memory as an opaque, typeless block, and then use the container templates to cast it to an appropriate pointer type.

    This works just fine, except for one little catch: there is one type of object you can't store in uSTL containers -- the kind that has pointers to itself. In other implementations, resizing actually creates new objects in the new location and destroys them in the old location. uSTL simply memcpys them there without calling the copy constructor. In other words, the object can not rely on staying at the same address.

  • convenient memblock routines to replacing dynamically allocated buffers used for unstructured data (read_file/write_file)

  • using memlink object to link things together (ex.: pointer and size of whatever it points to):

    ... you get to store a pointer and the size of whatever it points to, but with uSTL you can use a memlink object to keep them together, reducing source clutter and making your code easier to read and maintain.

    You can link to constant blocks too with cmemlink, from which memlink is derived. Because all three are in a single hierarchy, you never need to care whether you're working on an allocated block or on somebody else's allocated block. Pointers are kept together with block sizes, memory is freed when necessary, and you never have to call new or delete again.

    Linking is not limited to memlink. You can link memblock objects. You can link string objects. You can even link containers!

More info at home page.

SGI STL

freely available implementation of the C++ Standard Template Library made by Silicon Graphics.

You can use it in the same way as you use current MSVS's and GCC's implementations.

More info at home page.

Although there are other implementations of the C++ Standard Library, I picked aforementioned because they seemed interesting to me at some point. If you aware of another interesting class or library related to what we were discussing, let me know and I will add it. Also, I didn't consider SIMD-powered vector implementations because they are related to the different paradigm we are not going to talk about in this series, especially as we almost finished our journey.

List of references

  1. GCC 5.2.0: libstdc++-v3 implementation
  2. Paper for ISO C++ Placement Insert for Containers regarding emplace methods
  3. Nice paper about to insert vs emplace comparison.
  4. Mentioned discussion regarding vector's growth factor
  5. Iterator invalidation rules (C++03) and (C++0x)
  6. uSTL library
  7. facebook/folly library
  8. SGI STL implementation

Sergei Danielian

Read more posts by this author.

Vladivostok, Russia