c++ - std::vector pop_back() 实现

Question

我刚刚开始学习数据结构，并且正在实现某种数组列表(~=std::vector)。我想知道 pop_back() 是如何实现的，以便它具有恒定的复杂性？它必须将大小减少 1 并删除最后一个元素。现在我在某个地方看到它基本上将大小减少了 1 并通过一些迭代器/指针销毁了最后一个元素，但是为什么我们不能以相同的方式实现 pop_front() 并将指针重定向到第一个元素到下一个元素？/p>

template <typename T>
ArrayList<T>& ArrayList<T>::pop_back()
{
    --size_;
    auto p = new T[size_];
    std::copy(elements_,elements_+size_,p);
    delete [] elements_;   //elements_ being my pointer
    elements_ = p;
    return *this;
}

Answer 1

这不是 pop_back() 通常的实现方式。虽然它是一个实现细节，但通常您的列表/vector/动态数组会跟踪两种大小:一个是列表的实际大小，另一个是容量。容量是底层分配的内存的大小。现在 pop_back() 只是将大小减少 1 并在最后一个元素上运行析构函数(不要混淆析构，即使用 delete 运算符调用 ~T() 方法)。它不会重新定位任何东西。容量保持不变。整个操作不依赖于列表的大小(与您的实现不同)。

请注意，您不能以简单的方式对 pop_front() 执行相同的操作。您必须跟踪列表的开头和结尾以及底层内存(并且取决于方法:存储大小和容量或在运行时计算它们)。这需要更多的内存和可能更多的 CPU 操作。而且这样的结构也变得很奇怪。你知道容量，你知道大小，但你实际上不知道在调整大小发生之前你可以执行多少次push_back()(你只知道该数字以“容量减去大小”为界，但它可以更小)。除非您将此信息添加到您的结构中，否则它会再次占用内存或 cpu。

旁注:如果您打算采用原始析构函数方式，则根本不要使用 delete[] 运算符。删除操作几乎就是“调用析构函数+释放内存”。因此，如果您手动解构，则对 delete[] 的额外调用将​​导致未定义的行为。除非您实际分配 char 内存(无论 T)并使用 placement new (这还需要一些手动尺寸和偏移计算)。这是实现此类 vector 的好方法，尽管需要额外小心(手动内存跟踪是一个b***h)。