std::vector pop_back() 实现

Question

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

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

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

旁注：如果您打算采用原始析构函数方式，那么delete[]根本不要使用运算符。删除操作几乎就是“调用析构函数+释放内存”。因此，如果您手动析构，则额外的调用delete[]将导致未定义的行为。除非你实际分配char内存（不管T）并使用placement new（这也需要一些手动大小和偏移计算）。这是实现此类向量的好方法，尽管需要额外小心（手动内存跟踪是 ab***h）。