Как внедрена вставка std::vector? С++

Недавно я перечитывал стандарт ISO С++ и нашел очень интересное замечание:

Обратите внимание, что для std::vector единственным ограничением типа T для std::vector<T> является то, что тип T должен иметь конструктор копирования. На самом деле, если память вектора заполнена во время вставки, выделяется новая память size = 2 * oldSize (это зависит от реализации), а затем копирует в нее старые элементы и вставляет этот один элемент.

Но подождите?

Чтобы выделить новую память типа, нам нужно что-то вроде этого, ptr = new T[2*size];

Как это делается, потому что тип T может не иметь конструктора по умолчанию?
Затем Assignment, выделив память, мы должны назначить старые значения новой памяти, правильно?
Принимая во внимание это 2 вещи, как std::vector сделать это с помощью "ТОЛЬКО КОПИРОВАТЬ КОНСТРУКТОР?" Какая реализация и языковые идиомы используются?

Ответ 1

Выполняется с вызовом функции allocator allocate() для получения необработанной памяти и последующего вызова структуры allocator (iterator, val) для создания элемента путем копирования с использованием нового места размещения, то есть что-то похожее на это:

/* 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 */
    }
}

В С++ распределитель используется для изоляции исполнителей алгоритмов и контейнеров, которые должны выделять память из деталей физической памяти.

Подход, использующий uninitialized_fill, также можно взять:

 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); } */

Это описано более подробно в Bjarne Stroustrup "С++... 3rd edition". Здесь приведен пример, основанный на этом.

Ответ 2

Как правило, стандартные контейнеры разделяют выделение от инициализации (как и в любых контейнерах, которые вы пишете). Стандартные контейнеры используют очень сложный механизм, чтобы разрешить настройку как выделения, так и инициализации, но в случае по умолчанию, это сводится к использованию operator new/operator delete функции для выделения памяти, размещение нового для его инициализации и явный вызов деструктор для уничтожения объектов. Другими словами, insteaad of последовательность:

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

он использует:

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

(Это радикальное упрощение, чтобы показать основную концепцию. На практике это будет более сложным, по причинам исключения безопасность, например.)

Ответ 3

Подумайте о emplace_back(): скорее всего, вектор выделяет новый блок унифицированной памяти, затем запускает новое место для копирования-сборки объектов на месте.