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?

Answer 1

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.

Answer 2

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

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.