c++ - std::vector 插入是如何实现的？ C++

Question

最近在重读ISO C++标准，发现很有意思的注释:

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.

但是等等？？

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

1. 这是如何做到的，因为类型 T可能没有默认构造函数？
2. 然后Assignment，分配完内存后我们必须将旧值赋给新内存，对吧？
3. 考虑到这两点，std::vector用“ONLY COPY CONSTRUCTOR”做到这一点？使用了哪些实现和语言习语？

Answer 1

通过调用 allocator 函数 allocate() 来获取原始内存，然后调用分配器 construct( 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++ 中，分配器用于将必须分配内存的算法和容器的实现者与物理内存的细节隔离开来。

也可以采取直接使用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++...3rd edition”中有更详细的描述。 Here是基于此编写的示例。