保留 space 时自定义容器不必要地创建新元素实例

Question

为了我自己的教育，我正在尝试学习如何在 C++ 中实现高效的自定义容器。我现在有了自定义矢量类型的基本工作版本。但是，出于某种原因，当必须扩展向量以容纳更多元素时（在这种情况下调用其内部 'reserve' 函数），它会创建额外的元素副本。

为了帮助解释我的意思，我在下面展示了一个最小的可重现示例。让 CustomVector class 的最小版本如下所示：

template<class T>
class CustomVector
{
private:
    size_t m_size = 0;
    size_t m_capacity = 1;
    T *m_data = nullptr;

public:
CustomVector()
{
}

CustomVector(const size_t new_capacity)
{
    m_capacity = new_capacity;
    m_size = 0;
    m_data = new T[m_capacity]();
}

~CustomVector()
{
    if (m_data != nullptr)
        delete[] m_data;
}

void reserve(size_t new_capacity)
{
    if (m_data == nullptr)
    {
        m_capacity = new_capacity;
        m_size = 0;
        m_data = new T[m_capacity]();
    }
    else if (new_capacity > m_capacity)
    {
        T* new_data = new T[new_capacity]();
        memmove(new_data, m_data, (m_size) * sizeof(T));
        delete[] m_data;
        m_capacity = new_capacity;
        m_data = new_data;
    }
}

void push_back(const T & value)
{
    if (m_data == nullptr)
    {
        m_capacity = 1;
        m_size = 0;
        m_data = new T[m_capacity]();
        m_data[0] = value;
    }
    else if (m_size + 1 >= m_capacity)
    {
        reserve(m_capacity*2);
    }
    else
    {
        m_data[m_size-1] = value;
        m_size++;
    }
}

};

现在，为了方便查看问题，我还创建了一个名为 Object 的 class。自动创建的此类 class 的每个新实例都会收到一个唯一的 ID 号：

class Object
{
private:
    static int idCounter;
public:
    int id;
    Object()
    {
        id = idCounter;
        idCounter++;
    }
};
int Object::idCounter = 0;

最后，这里是这个例子的 main 函数的样子：

int main()
{
    CustomVector<Object> objects; //comment this line...
    //std::vector<Object> objects; //...and uncomment this to try with std::vector
Object x;
printf("%d\n", x.id);
objects.push_back(x);

Object y;
printf("%d\n", y.id);
objects.push_back(y);

Object z;
printf("%d ", z.id);

system("Pause");
return 0;

}

使用我的 CustomVector 作为容器的输出是：

0 2 5

而使用 std::vector 作为容器的输出是：

0 1 2

对我来说理想的行为正是 std::vector 的行为，即推回 classes 的实例应该创建此类 class.[=22 的全新临时实例=]

有人可以帮助我了解我做错了什么吗？

Answer 1

问题很可能是 push_back 函数中的这一行：

m_data = new T[m_capacity]();

这将导致创建 m_capacity 个 T 对象，因此 m_capacity 调用 T 构造函数。如果 T 构造函数很昂贵（更不用说一些初学者在构造函数中进行输入和其他操作），这就很糟糕了。

std::vector 最有可能做的是保留字节的缓冲区，然后在推回时执行 placement new在缓冲区中的某个位置构造一个对象。

保留 space 时自定义容器不必要地创建新元素实例

Custom container unnecessarily creating new elements instances when space is reserved

c++

containers

constructor

allocation