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

Question

最近我重读ISO C++标准，发现非常有趣注：

注意，对于std::vector，对std::vector<T>T类型的唯一的限制是该类型T必须有拷贝构造函数。实际上，如果向量的内存在插入时已满，则分配一个新的内存size = 2 * oldSize（这取决于实现），然后复制其中的旧元素并插入该元素。

但等待？

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

1. 如何做到这一点，因为类型T可能不会有一个默认的构造函数？
2. 然后赋值，在分配内存后，我们必须将旧值赋给新的内存，对吧？
3. 考虑到这两件事情，std::vector如何与“只有复制构造者？”做到这一点？使用什么实现和语言习语？

Answer 1

作为一般规则，标准容器从初始化中分离分配 （就像你写的任何容器一样）。 标准容器使用了非常复杂的机制，以 同时允许分配和初始化，但 在默认情况下定制，把它归结为使用 operator new/operator delete功能分配内存， 安置新初始化它，并明确地调用析构函数销毁对象。换句话说，的 insteaad序列：

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

（这是自由基简化，以示出基本概念 在实践中，这将是更复杂的，例如 安全的原因。）

Answer 2

想一想emplace_back（）：最有可能的是vector分配一块新的单元化内存，然后运行放置new来复制 - 在原地构建对象。

Answer 3

它与呼叫做分配器功能分配（）来获得原始内存和下面的呼叫分配器构建（迭代器，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 */ 
    } 
} 

在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++ ...第3版” 更详细地描述。 Here是基于此编写的示例。