std::vector的插入操作是如何实现的？C++

Question

最近我重新阅读了ISO C++标准，发现了非常有趣的注释：

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

但是等等？

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

1. 这是如何实现的，因为类型T可能没有默认构造函数？
2. 然后进行赋值，在分配内存后，我们必须将旧值分配给新内存，对吗？
3. 考虑到这两点，std::vector如何仅使用“COPY CONSTRUCTOR”来完成此操作？使用了哪些实现和语言习惯用法？

- Eduard Rostomyan

---

这并不是使用数组-new完成的。数组-new是语言中完全错误的设计，而且毫无用处，正如你所发现的一样。相反，内存分配和对象构造完全是分开进行的。 - Kerrek SB

如果一个类有任何形式的用户定义构造函数，那么就没有编译器生成的默认构造函数。 - M.M

@KerrekSB 为什么你会说某个东西完全没用，只因为它不适合这种情况？Array-new 适用于分配数组。你可以认为显式手动分配是不好的（在这种情况下，你反对 new、delete、new[] 和 delete[]，很可能也反对原始指针），但这与仅仅认为 array-new 不好是不同的。 - user253751

@immibis：动态数组在概念上是有缺陷的。你不能在不知道其大小的情况下使用动态数组，因此你必须单独携带大小信息，这违反了封装原则。更让人恼火的是，编译器仍然需要复制大小信息才能调用析构函数。简而言之，只需使用std::vector即可。 - Kerrek SB

可能是如何实现C++ std::vector？的重复问题。 - sampathsris

Answer 1

使用allocator函数allocate()调用来获取原始内存，并接下来使用allocator 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++...第三版》中找到。 这里 提供了一个基于此的示例。

- 4pie0

---

这只是一个小问题，但是allocate的返回类型是std::allocator_traits<A>::pointer，而construct期望一个C *（对于任意对象类型C）。前者不一定是后者的形式（例如它可以是用户定义的类型）。 - Kerrek SB

+1 如果显示完整且易读的代码，包括在注释中可能内联的alloc.construct()。请注意，OP询问了向量调整大小的情况，其中还需要销毁旧数组中的元素。但是，一旦理解了上面的代码，这样做就很简单。 - user4815162342

也许提供一个alloc.destroy的例子会很有价值（例如q->~T()）。此外，iterator不一定是指针。除此之外，非常好的回答，+1。 - Mankarse

@Mankarse 但是有时候 std::vector::iterator 是一个指针。 - ratchet freak

std::vector::iterator 不一定是指针。在许多实现中，它可能是指针，但标准并不保证如此。 - JohannesD

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

（这是一个激进的简化，展示基本概念。实际上，出于异常安全的原因，它将变得更加复杂。）

- James Kanze

Answer 3

考虑emplace_back()：很可能vector会分配一个新的未初始化内存块，然后运行放置new在原地复制构造对象。

- Quentin