vector::erase 如何从其内部数组中删除所选元素

Question

由于 vector 类型的对象在内部由数组支持，因此 vector class 的擦除函数如何从其内部数组中删除所选元素？

我正在寻找至少包含基本代码示例的深入说明。

Answer 1

通过复制擦除元素之后的元素，然后在末尾填充一个"empty"元素。然后将尺寸标记为少一

代码大致是这样的[实际实现将使用一些技巧来避免制作不必要的副本等，例如使用移动语义]

template<typename T>std::vector::erase(int index)
{
   // Call destructor of T for the one being deleted.
   storage[index].T~();
   for(i = index; i < size-1; i++)
   {
       storage[i] = storage[i+1];
   }
   storage[size-1] = T();
   size--;
}

如果您想了解 REAL 实现的工作原理，我建议您启动调试器并亲自尝试一下。但是，如果它非常复杂且难以理解，请不要感到惊讶 - 编写库代码的人通常非常精通该语言的工作原理，并且会使用 "any trick in the book" 使其成为 faster/smaller/neater.

Answer 2

当删除除末尾元素以外的任何元素时，删除元素之后的元素将向左打乱。

Answer 3

矢量必须在不调用任何构造函数的情况下分配内存。然后它可以使用 placement new 和 placement delete （也就是手动调用析构函数）。

Placement new 涉及指定一个内存地址，并使用指向该内存地址的 this 调用构造函数。 放置删除涉及运行析构函数，但不释放内存。（向量将保持在内存块上，然后将另一个对象放置到同一位置）。

向量也可以使用复制赋值运算符、复制构造函数、移动构造函数, 移动赋值运算符来完成它的工作。

在C++11之前，vectors要求元素是CopyAssignable，所以一个基本的vector实现（显然我省略了很多功能）：

template<typename T>
struct vector
{
    T *base;
    size_t m_count;
    size_t m_capacity;

    // start off with space reserved for 20 elements, but no actual elements
    vector(): base((T *)new unsigned char[20 * sizeof(T)]), 
              m_count(0), m_capacity(20) {}

    void push_back(T const &t) {
        if ( m_count == m_capacity )
             reserve(m_capacity * 2);

        // placement new, using copy-constructor
        new(base + m_count) T(t);
        ++m_count;
    }

    void erase(size_t index)
    {
    // Use the assignment-operator to shuffle all objects down by one
    // (The "being erased" object doesn't get destructed directly, but it
    //  loses its state by having another object assigned to it. This is
    //  permitted because T must be CopyAssignable prior to C++11. In
    //  C++11 this function would try to Move objects down instead.
         for (size_t i = index; i < m_count - 1; ++i)
             base[i] = base[i+1];

    // Call destructor for the last object (which we currently have 2 of)
         base[m_count-1].~T();
         --m_count;

    }
};

vector::erase 如何从其内部数组中删除所选元素

how does vector::erase remove the chosen element from it's internal array

c++

arrays

vector