如何实现std :: vector insert？C++

Question

最近我正在重读ISO C++标准,并发现了非常有趣的说明:

请注意,std::vector上式的唯一约束T的std::vector<T>是该类型T必须有拷贝构造函数.实际上,如果在插入时向量的内存已满,则分配一个新的内存size = 2 * oldSize(这是依赖于实现的),然后在其中复制旧元素并插入该元素.

可是等等？？

要分配类型的新内存,我们需要这样的东西, ptr = new T[2*size];

1. 如何做到这一点,因为类型T可能没有默认构造函数？
2. 然后分配,在分配内存之后我们必须将旧值分配给新内存,对吧？
3. 考虑到这两件事,如何std::vector用"仅复制构造器"来做到这一点？使用了哪些实现和语言习语？

Answer 1

它通过调用allocator函数allocate()来获取原始内存并跟随调用allocator 构造(iterator,val)以使用placement new复制构造元素,即类似于:

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

在C++中,allocator用于隔离必须从物理内存细节分配内存的算法和容器的实现者.

也可以采用直接使用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的"C++ ...第3版"中有更详细的描述.这是基于此编写的示例.

Answer 2

作为一般规则，标准容器将分配与初始化分开（您编写的任何容器也应如此）。标准容器使用非常复杂的机制来允许自定义分配和初始化，但在默认情况下，它归结为使用 operator new/operator delete 函数来分配内存，使用 new 来初始化它，并显式调用析构函数来销毁对象。换句话说，代替序列：

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

（这是一个彻底的简化，以显示基本概念。在实践中，它会更复杂，例如出于异常安全的原因。）