C++ Internals :: STL vector, Part II

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.

Update 08/Aug/2015: I added a little bit more information regarding inner service members (_Myfirst, _Mylast, etc.)


This is the second article in STL Vector Internals series. First part was about std::vector's definition, its growth factor and some special methods it has.

Emplacing Items

std::vector in C++ provides two additional methods - analogous to insert() and push_back():

  • emplace - constructs items in-place at given position
  • emplace_back() - constructs items in-place at the end

std::deque and std::list in addition have emplace_front method and std::forward_list has emplace_after method

The difference is in constructing new values right in-place without making redundant copies. If you want to know more about the origins of the creation of emplace methods, refer to Placement Insert for Containers paper. You'll find there a lot of stuff: motivation, examples, possible implementations.

Here are the signatures of two std::vector's emplace methods:

template <class... Args>  
iterator emplace (const_iterator position, Args&&... args);  

template <class... Args>  
void emplace_back (Args&&... args);  


In order to accept a variable number of arguments for constructing an object, emplace methods use parameter packing and in order to successfully transfer all arguments they use so-called perfect forwarding (parameter forwarding via std::forward).

To get an idea of what lays behind emplacing objects, consider the following class that represents a too costly-to-create object:

class HugeObject  
{
    std::string value;

public:

    HugeObject(std::string p_value) : value(std::move(p_value)) {
        std::cout << "Constructor" << std::endl;
    }

    // Not being invoked. It's here for illustration purpose
    HugeObject(const HugeObject& other) : value(other.value) {
        std::cout << "Copy Constructor" << std::endl;
    }

    HugeObject(HugeObject&& other) : value(std::move(other.value)) {
        std::cout << "Move Constructor" << std::endl;
    }
}


Let's see what happens when you use push_back() and emplace_back() methods:

int main()  
{
    std::vector<HugeObject> objects;

    // Avoid reallocations
    objects.reserve(10);

    // Construct and Move
    objects.push_back(HugeObject("I'm a big object!"));

    // Construct in-place
    objects.emplace_back("I'm a big object too!");
}

Output:

Constructor  
Move Constructor  
Constructor  


Pretty self-explanatory, isn't it? Again, the main purpose of emplace methods is to eliminate redundant object copying by creating those objects in-place.

Each vendor is free to implement mentioned emplace methods by its own, with their own "flavor". For example, in Microsoft's implementation, inserting a vector's items into itself causes a known issue. That doesn't happen in either GCC or in Clang.

Consider the following example:

#include <vector>
#include <iostream>

int main()  
{
    std::vector<int> numbers { 0x22, 0x37, 0x59, 0x90 };

    numbers.emplace_back(numbers[1]);
    numbers.push_back(numbers[1]);

    for (auto number : numbers) {
        std::cout << std::hex << number << "; ";
    }

    std::cout << std::endl;

    return 0;
}

Output:

MSVS 2013
22; 37; 59; 90; feeefeee; 37;

GCC 5.2.0
22; 37; 59; 90; 37; 37;

Clang 3.6
22; 37; 59; 90; 37; 37;

If you call reserve() before inserting items (in MSVS), all three results will be the same - no garbage.

The bug appears only if a vector has to grow in size. This somehow causes references to the passed items be invalidated. Let's dive into MSVS's implementation of std::vector and figure out why that happens.

MSVS 2013 & emplace_back

emplace_back implementation (vector:l:892):

template<class... _Valty>  
void emplace_back(_Valty&&... _Val)  
{        
    // insert by moving into element at end
    if (this->_Mylast == this->_Myend)
        _Reserve(1);
    _Orphan_range(this->_Mylast, this->_Mylast);
    this->_Getal().construct(this->_Mylast, _STD forward<_Valty>(_Val)...);
    ++this->_Mylast;
}


Update 08/Aug/2015: Let me provide additional clarification related to the code snippet above. std::vector class has different instance members (both regular and internal) and among them are the following:

  • _Myfirst - points to the beginning of the data array
  • _Mylast - points to the first uninitialized element in the data array. If equals to _Myend, next insertion will cause reallocation. You get this guy on end() call
  • _Myend - points to the end of the data array

So, in terms of memory addresses, the following inequality takes place:

_Myfirst $<=$ _Mylast $<=$ _Myend

Finally:

Figure 1. Memory layout of integer vector's dynamic data array


Aha! See that line with _Reserve(1) in it? This function call causes our bug to reveal itself.

Let's work through step-by-step (refer to previous example function). Review line #8:

numbers.emplace_back(numbers[1]);

First we get a reference to the item because operator[] returns a reference (vector:l:1196):

reference operator[](size_type _Pos) { ... }

Then we move into emplace_back method, passing fresh and valid reference to the item we want to insert. What we immediately see at the beginning is a check on vector's size exceeding. As long as our insertion causes a vector to grow its size, we get reference invalidated just after reallocation happens. That's the reason of such interesting but expected (once we got into implementation) behavior.

I said earlier that this is a bug. But I wouldn't treat it strongly that way. Things are more complicated. Yes, the behavior might surprise you, but the standard gives a lot of freedom sometimes. For example, section 17.6.4.9 Function arguments states:

Each of the following applies to all arguments to functions defined in the C++ Standard Library unless explicitly stated otherwise.

  • If an argument to a function has an invalid value (such as a value outside the domain of the function or a pointer invalid for its intended use), the behavior is undefined.

Another quote from 23.3.6.5 vector modifiers:

[... emplace/emplace_back ...] Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

So, what would you expect from the emplace_back then, if even the standard provides a cover for that? Yes, it not quite right to put a garbage into a vector, but you were warned about invalidation that might happen.

Let's now review how GCC implements emplace_back method and why it doesn't have the problem just described. I refer to libstdc++-v3 STL implementation in GCC 5.2.0.

GCC 5.2.0 & emplace_back

emplace_back implementation (.../bits/vector.tcc:l:87):

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
    void vector<_Tp, _Alloc>::emplace_back(_Args&&... __args)
    {
        if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
        {
            _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
                std::forward<_Args>(__args)...);
            ++this->_M_impl._M_finish;
        }
        else
            _M_emplace_back_aux(std::forward<_Args>(__args)...);
    }
#endif


and _M_emplace_back_aux implementation (.../bits/vector.tcc:l:403):

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
    void vector<_Tp, _Alloc>::
    _M_emplace_back_aux(_Args&&... __args)
    {
        const size_type __len =
            _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
        pointer __new_start(this->_M_allocate(__len));
        pointer __new_finish(__new_start);

        __try
        {
            _Alloc_traits::construct(this->_M_impl, __new_start + size(),
                std::forward<_Args>(__args)...);
            __new_finish = pointer();

            __new_finish
                = std::__uninitialized_move_if_noexcept_a
                    (this->_M_impl._M_start, this->_M_impl._M_finish,
                        __new_start, _M_get_Tp_allocator());

            ++__new_finish;
        }
        __catch(...)
        {
            if (!__new_finish)
                _Alloc_traits::destroy(this->_M_impl, __new_start + size());
            else
                std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
            _M_deallocate(__new_start, __len);
            __throw_exception_again;
        }

        std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
            _M_get_Tp_allocator());
        _M_deallocate(this->_M_impl._M_start,
            this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
        this->_M_impl._M_start = __new_start;
        this->_M_impl._M_finish = __new_finish;
        this->_M_impl._M_end_of_storage = __new_start + __len;
    }
#endif


Recall our tiny program:

auto main() -> int  
{
    std::vector<int> numbers { 0x22, 0x37, 0x59, 0x90 };

    numbers.emplace_back(numbers[1]);
    ...
}

Running it, we soon be in _M_emplace_back_aux function, because emplace_back's condition fails and instead of construction in-place, reallocation happens:

...
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)  
{
    // Constructing object in-place
    ...
}
else  
    // Do reallocation and then insert; our case
    _M_emplace_back_aux(std::forward<_Args>(__args)...);
...


Just as we wanted. Going through _M_emplace_back_aux function quickly clarifies how GCC version works: it first allocates new block of memory, copies new item in its place in that new memory region, then moves old data into a new place too and after that destroys old memory.

Want proofs? Here are few excerpts from the GDB.

First, let's verifing that we indeed get a reference (set a breakpoint, hit it and step into the operator[]):

(gdb) break 8
Breakpoint 1 at    0x400d4e: file test.cpp, line 8.  
(gdb) run
Starting program: /home/gahcep/test/test.out 

Breakpoint 1, main () at test.cpp:8  
(gdb) step
std::vector<int, std::allocator<int> >::operator[] (this=0x7fffffffdd10, __n=1) at /usr/local/include/c++/5.2.0/bits/stl_vector.h:780  
(gdb) finish
finish  
Run till exit from #0  std::vector<int,    std::allocator<int> >::operator[] (this=0x7fffffffdd10, __n=1) at /usr/local/include/c++/5.2.0/bits/stl_vector.h:780  
0x0000000000400d5f in main () at test.cpp:8  
Value returned is $1 = (__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type &) @0x605014: 55  


Yeah, operator [] returned a reference (0x605014), so our next step is to check the addresses of old and new vector's data.

At the beginning of the _M_emplace_back_aux function we have this vector's memory layout:

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
    void vector<_Tp, _Alloc>::
    _M_emplace_back_aux(_Args&&... __args)
    {
        const size_type __len =
            _M_check_len(size_type(1), "vector::_M_emplace_back_aux");    // <- WE ARE HERE
        ...

(gdb) x/16xw this->_M_impl._M_start
0x605010:     0x00000022  0x00000037  0x00000059  0x00000090  
0x605020:     0x00000000  0x00000000  0x00020fe1  0x00000000  
0x605030:     0x00000000  0x00000000  0x00000000  0x00000000  
0x605040:     0x00000000  0x00000000  0x00000000  0x00000000  


Starting from 0x605010 16 bytes are occupied by our numbers (0x22, 0x37, 0x59, 0x90). Next thing shows the memory after new memore was allocated and new items was "emplaced":

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
    void vector<_Tp, _Alloc>::
    _M_emplace_back_aux(_Args&&... __args)
    {
        ...
        __try
        {
            _Alloc_traits::construct(this->_M_impl, __new_start + size(),
                std::forward<_Args>(__args)...);
            __new_finish = pointer();    // <- WE ARE HERE

(gdb) x/16xw this->_M_impl._M_start
0x605010:    0x00000022  0x00000037  0x00000059  0x00000090  
0x605020:    0x00000000  0x00000000  0x00000031  0x00000000  
0x605030:    0x00000000  0x00000000  0x00000000  0x00000000  
0x605040:    0x00000037  0x00000000  0x00000000  0x00000000  
(gdb) x/8xw __new_start
0x605030:    0x00000000  0x00000000  0x00000000  0x00000000  
0x605040:    0x00000037  0x00000000  0x00000000  0x00000000  


New memory was allocated very close to existing one (__new_start: 0x605030) and as you can see, old memory with our values are still there, and new item was placed right at the position after the last existing item (0x605040: 0x00000037) in a newly allocated region of memory. Let's see the final one:

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
    void vector<_Tp, _Alloc>::
    _M_emplace_back_aux(_Args&&... __args)
    {
        ...
            __new_finish
                = std::__uninitialized_move_if_noexcept_a
                    (this->_M_impl._M_start, this->_M_impl._M_finish,
                        __new_start, _M_get_Tp_allocator());

            ++__new_finish;    // <- WE ARE HERE
        }
    ...

(gdb) x/16xw this->_M_impl._M_start
0x605010:    0x00000022  0x00000037  0x00000059  0x00000090  
0x605020:    0x00000000  0x00000000  0x00000031  0x00000000  
0x605030:    0x00000022  0x00000037  0x00000059  0x00000090  
0x605040:    0x00000037  0x00000000  0x00000000  0x00000000  


Values were moved and short after deleted (this->_M_impl._M_start points to new location, so we use explicitly the old address):

(gdb) x/16xw 0x605010
0x605010:    0x00000000  0x00000000  0x00000059  0x00000090  
0x605020:    0x00000000  0x00000000  0x00000031  0x00000000  
0x605030:    0x00000022  0x00000037  0x00000059  0x00000090  
0x605040:    0x00000037  0x00000000  0x00000000  0x00000000  


I won't be telling about Clang's implementation as it looks almost the same as GCC's one, so it will be your homework.

I hope now you have a good understanding how std::vector's insertion procedure internally works and why MSVS has an issue whilst others don't.

Check out an interesting discussion on Reddit (involving Stephan T. Lavavej itself) regarding this well-known std::vector pitfall.

Yes, ok. We got it. But you may ask, why the hell, push_back works, shouldnt' it grow under the same conditions and behaves the same as emplace_back does? Here is a MSVS 2013 push_back implementation:

void push_back(const value_type& _Val)  
{    
    // insert element at end
    if (_Inside(_STD addressof(_Val)))
    {
        // push back an element
        size_type _Idx = _STD addressof(_Val) - this->_Myfirst;
        if (this->_Mylast == this->_Myend)
            _Reserve(1);
        _Orphan_range(this->_Mylast, this->_Mylast);
        this->_Getal().construct(this->_Mylast, this->_Myfirst[_Idx]);
        ++this->_Mylast;
    }
    else
    {
        // push back a non-element
        if (this->_Mylast == this->_Myend)
            _Reserve(1);
        _Orphan_range(this->_Mylast, this->_Mylast);
        this->_Getal().construct(this->_Mylast, _Val);
        ++this->_Mylast;
    }
}


See that check - if (_Inside(_STD addressof(_Val)))? Here is the code for _Inside:

bool _Inside(const value_type *_Ptr) const  
{
    // test if _Ptr points inside vector
    return (_Ptr < this->_Mylast && this->_Myfirst <= _Ptr);
}


push_back checks if the passed address is within it's items range and if so, it calculates and saves the item initial index and after reallocation is done, continue to work with memory cell addressed by the saved index value.

Now, GCC's push_back implementation:

void push_back(const value_type& __x)  
{
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
    {
        _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
        ++this->_M_impl._M_finish;
    }
    else
#if __cplusplus >= 201103L
        _M_emplace_back_aux(__x);
#else
        _M_insert_aux(end(), __x);
#endif
}

#if __cplusplus >= 201103L
    void push_back(value_type&& __x)
    { emplace_back(std::move(__x)); }

    template<typename... _Args>
    void emplace_back(_Args&&... __args);
#endif


So, basically, what you see here is that GCC substitutes push_back method's internals - in C++11 (#if __cplusplus >= 201103L) push_back uses emplace approach.

Ok, enough with this. We have more to discuss.

Iterators

Iterators are a well-known concept in C++. I wouldn't go into too much details describing every iterator type - you can do this by your own (any decent book or cppreference to the rescue). I'm just gonna mention few things that will ease your work with iterators and will help you to avoid falling into a trap.

First big thing to know about is traits. Iterator traits allows you to make a compile-time decisions based on types. You can vary class's behavior depending on iterator class: what kind of type does the item in std::vector have and what kind of iterator (forward or random access) does the given container provide? Use std::iterator_traits for that.

For example, consider a custom container-based type which decomposes given container via template argument:

#include <iterator>

template <class Cont>  
class ContWrapper  
{
public:  
    // One way is to retrieve information from the container ...
    typename Cont::value_type value_type;

    // ... or we can use another way using iterator_traits class
    typename std::iterator_traits<Cont>::value_type another_value_type;

    // Get iterator category to use later in SFINAE or in type check
    // For example, std::vector has random_access_iterator_tag iterator's category
    typename std::iterator_traits<Cont>::iterator_category iterator_category;

    // Do some stuff based on what kind of iterator we have
    /* ... */
}

You see typenames because we use dependent types.

Example shows how to get a knowledge about type of iterator we were provided with, so later we can enable/disable some functionality based on that information.

Next big thing is new stuff regarding iterators available in C++11. Besides well-known iterator types - iterator, reverse_iterator and they const versions (plus those related to IO streams), we have two specific, that were available before C++11 - back_insert_iterator and front_insert_iterator. They are special output iterators designed to allow algorithms inserting new elements at the end or at the beginning (accordingly). They're usually used in algorithms that overwrites items.

Example:

#include <vector>
#include <deque>
#include <iostream>
#include <iterator>

int main()  
{
    std::vector<int> numbers { 34, 55, 89, 144 };

    /* std::back_insert_iterator */

    // Filled at end
    std::vector<int> numbers_at_end { 1, 2, 3, 4 };

    // 'back_insert_iterator' uses 'push_back' method
    std::back_insert_iterator<std::vector<int>> back_iter(numbers_at_end);

    // Use generic functions
    std::copy(std::begin(numbers), std::end(numbers), back_iter);

    // Will print [1, 2, 3, 4, 34, 55, 89, 144]
    for (auto item : numbers_at_end) {
        std::cout << item << "; ";
    }
    std::cout << '\n';

    /* std::front_insert_iterator */

    // Filled at front
    std::deque<int> numbers_at_front{ 1, 2, 3, 4 };

    // 'back_insert_iterator' uses 'push_front' method
    std::front_insert_iterator<std::deque<int>> front_iter(numbers_at_front);

    // Use specific functions
    std::copy(numbers.begin(), numbers.end(), front_iter);

    // Will print [144, 89, 55, 34, 1, 2, 3, 4]
    for (auto item : numbers_at_front) {
        std::cout << item << "; ";
    }
    std::cout << '\n';

    return 0;
}


C++11 brings us, as you know, move semantics. That's why adding std::move_iterator:

template <class Iterator> class move_iterator;

was highly expected. However, new iterator was added in std namespace; containers don't have such a thing.

std::move_iterator accepts iterator class and returns a move version of it. Let's check how it works:

#include <vector>
#include <string>
#include <iterator>

int main()  
{
    std::vector<std::string> first { "one", "two", "and three" };
    std::vector<std::string> second (3);

    using _iter_ = std::vector<std::string>::iterator;

    std::copy(
        std::move_iterator<_iter_>(first.begin()),
        std::move_iterator<_iter_>(first.end()),
        second.begin());

    // At this point 'first' has three empty strings

    return 0;
}


In addition to std::move_iterator namespace <iterator> defines std::make_move_iterator which adapts an iterator in such a way that dereferencing it produces rvalue references (as if `std::move was applied).

Other methods new to C++ world are:

  • begin() and end() - returns corresponding iterators. Methods are generic and not bound to particular container
  • next() and prev() - returns iterators pointing to another items taking as a base current one

Last big thing to be worry about is invalidation. This thing should be kept in memory all the time. Especially if you intensively work with vector's items - inserting or erasing. To know what kind of guarantee brings a method, refer to C++ standard.

In general, invalidation rules depend on what type of container and method you are going to use. The safest container, for example, is std::list. But if you work with unordered associative collections (std::unordered_map or std::unordered_multiset) then you probably know about their internal implementation (variation of hash tables with elements organized into buckets) and here is what the standart says about rehashing (23.2.5.8):

Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements.

What follows is a couple excerpts related to invalidation issues regarding sequence containers.

Concerning vector's reallocation (23.3.6.3):

Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

Regarding insert and emplace methods (23.2.4/9):

The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

Another interesting example. swap() method. C++ is clear about it (23.2.1/10):

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

Pretty strong guarantee, right? That's mean I can do any tricks with swap without invalidating my iterators? Let's give it a try:

#include <vector>
#include <iterator>
#include <cassert>

int main()  
{
    std::vector<int> vec_1{ 1, 2, 3, 4, 5, 6 };
    std::vector<int> vec_2{ 100, 200, 300, 400, 500, 600 };

    // First vector: points to first item
    auto it_for_vec_1 = vec_1.begin();
    // First vector: points to fifth item now
    std::advance(it_for_vec_1, 4);
    assert(*it_for_vec_1 == 5);

    // First vector: points to first item
    auto it_for_vec_2 = vec_2.begin();
    // First vector: points to third item now
    std::advance(it_for_vec_2, 2);
    assert(*it_for_vec_2 == 300);

    // Swap vectors
    vec_1.swap(vec_2);

    assert(*it_for_vec_1 == 5);
    assert(*it_for_vec_2 == 300);

    return 0;
}


Indeed, it worked!

I mentioned a trap that you can fall in if not enough care provided regarding invalidation. Here is what can happen:

#include <vector>

int main()  
{
    std::vector<int> numbers { 34, 55, 89, 144 };

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        numbers.erase(it);
        // at this point iterator has been invalidated, 
        // you can't use it anymore
    }

    return 0;
}


That's all for the second part. Stay tuned, next one will be quite interesting too.

Sergei Danielian

Read more posts by this author.

Vladivostok, Russia