How is std::vector insert implemented? C++

Question

Recently I was rereading ISO C++ standard, and found very interesting note:

Note that for std::vector, the only constraint on type T of std::vector<T> is that type T must have copy constructor. Actually, if the memory of vector is full while insertion, is allocate a new memory of size = 2 * oldSize (this is implementation dependent) and then copy old elements in it and insert that one element.

But Wait??

To allocate new memory of type the we need something like this, ptr = new T[2*size];

1. How this is done, because the type T may not have a default constructor?
2. Then Assignment, after allocating the memory we must assign old values to new memory, right?
3. To taking into consideration this 2 things, how does std::vector do this with "ONLY COPY CONSTRUCTOR?" What implementation and language idioms are used?

Sisterhood

It's not done with array-new. Array-new is a complete misfeature of the language and utterly useless, as you're just discovering. Instead, memory allocation and object construction are done completely separately from one another. – Calyx

If no explicit default compiler provided, the compiler will make one. – Tourcoing

@Tourcoing if the class has a user-defined constructor of any sort, then there is no compiler-generated default constructor – Becharm

@KerrekSB why would you say something is completely useless just because it isn't appropriate for this case? Array-new is good for allocating arrays. You can argue that explicit manual allocation is bad (in which case you are against new, delete, new[] and delete[] and likely raw pointers as well), but that's different from arguing that only array-new is bad. – Fairminded

@immibis: Dynamic arrays are conceptually broken. You cannot use a dynamic array without knowing its size, so you have to carry the size information around separately, which violates encapsulation. And to add insult to the injury, the compiler will need to duplicate the size information anyway in order to call destructors. The short answer is, just use std::vector. – Calyx

Sure, and that means C is even more broken. It's not, it just does not agree with that particular programming style. void* is also "conceptually broken" because you need to remember the type of the thing pointed to. – Fairminded

@immibis: C is a different language. It doesn't have destructors nor encapsulation supported natively by the language. Void pointers are generally for memory, not objects, and for that purpose they work just fine. – Calyx

And new[] lets you allocate several contiguous PODs (or even full objects). For that purpose it works just fine. – Fairminded

OP: I'm curious why you didn't just read the code. – Hughhughes

possible duplicate of How is C++ std::vector implemented? – Arola

Answer 1

As a general rule, the standard containers separate allocation from initialization (as should any containers you write too). The standard containers use a very complex mechanism in order to allow customization of both allocation and initialization, but in the default case, it boils down to using the operator new/operator delete functions to allocate the memory, placement new to initialize it, and an explicit call to the destructor to destroy the objects. In other words, insteaad of the sequence:

p = new T[n];
//  ...
delete [] p;

it uses:

p = operator new( n * sizeof( T ) );
for ( int i = 0; i != n; ++ i ) {
    new ( p + i ) T( otherValue );
}

//  ...
for ( int i = 0; i != n; ++ i ) {
    p->~T();
}
operator delete( p );

(This is a radical simplification, to show the basic concept. In practice, it will be more complex, for reasons of exception safety, for example.)

Pye

Answer 2

It is done with a call to allocator function allocate() to get raw memory and following call to allocator construct( iterator, val) to construct an element by copy using placement new, i.e. something similar to this:

/* approach similar to std::uninitialized fill taken */
template<typename T, typename A >
vector<T,A>::vector( size_type n, const T& val, const A& a) : alloc( a)  // copy the allocator
{
    /* keep track of which elements have been constructed
     * and destroy those and only those in case of exception */
    v = alloc.allocate( n); // get memory for elements
    iterator p;             // declared before try{} so it is still valid in catch{} block

    try {
        iterator end = v + n;
        for( p = v; p != end; ++p)
            alloc.construct( p, val); /* construct elements (placement new):
                                      e g. void construct( pointer p, const T& val) 
                                      { ::new((void *)p) T( val); } */
        last = space = p;
    } catch( ...) {
        for( iterator q = v; q != p; ++q)
            alloc.destroy( q);       /* destroy constructed elements */
        alloc.deallocate( v, n);     /* free memory */
        throw;                       /* re-throw to signal constructor that failed */
    }
}

In C++ allocator is used to insulate implementers of algorithms and containers that must allocate memory from the details of physical memory.

Approach using uninitialized_fill directly can also be taken:

 std::uninitialized_fill( v, v + n, val); /* copy elements with (placement new):
                                             e g. void construct( pointer p,
                                                                  const T& val) 
                                             { ::new((void *)p) T( val); } */

This is described with more details in Bjarne Stroustrup's "C++...3rd edition". Here is a sample written based on this.

Astrophotography

It's a nitpick, but allocate has return type std::allocator_traits<A>::pointer, whereas construct expects a C * (for an arbitrary object type C). The former need not be of the latter form (e.g. it could be a user-defined type). – Calyx

+1 for showing complete and readable code, including a possible inlining of alloc.construct() in the comment. Note that the OP asked about the case when the vector resizes, where it would also need to destroy the elements in the old array. But doing this is trivial once the above code is understood. – Ensheathe

It might be worth providing an example alloc.destroy too (ie q->~T()). Also, iterators are not necessarily pointers. Other than that, excellent answer, +1. – Wylde

@Wylde but it happens that the std::vector::iterator is a pointer – Salonika

@ratchetfreak: std::vector::iterator is not necessarily a pointer. In many implementations it may be, yes, but the standard does not guarantee that. – Disembody

Answer 3

Think about emplace_back() : most probably vector allocates a new chunk of unititialized memory, then runs placement new to copy-construct the objects in-place.

Zielsdorf