如何實現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是基於此編寫的示例。