std::vector pop_back() 实施
std::vector pop_back() implementation
我刚刚开始使用我的数据结构，并且正在实现某种数组列表 (~=std::vector)。我想知道 pop_back() 如何实现以使其具有恒定的复杂性？它必须将大小减 1 并删除最后一个元素。现在我在某处看到它基本上将大小减小 1 并通过一些 iterator/pointer 销毁最后一个元素，但是为什么我们不能以相同的方式实现 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;
}
pop_back() 通常不是这样实现的。虽然这是一个实现细节，但通常您的 list/vector/dynamic 数组会跟踪两种大小：一种是列表的实际大小，另一种是容量。容量是底层分配内存的大小。现在 pop_back() 只是将大小减 1 并在最后一个元素上运行析构函数（不要混淆析构，即调用 ~T() 方法和 delete 运算符）。它不会重新定位任何东西。容量保持不变。整个操作不依赖于列表的大小（与您的实现不同）。
请注意，您无法通过简单的方式对 pop_front() 执行相同的操作。您将必须跟踪列表的开头和结尾以及底层内存（并且取决于方法：存储大小和容量或在运行时计算它们）。这需要更多的内存和可能更多的 cpu 操作。而且这样的结构也变得很奇怪。你知道容量，你知道大小，但你实际上不知道在调整大小发生之前你可以做多少 push_back() （你只知道这个数字受 "capacity minus size" 限制，但它可以是更小）。除非您将此信息添加到您的结构中，否则它会再次占用内存或 cpu.
旁注： 如果您打算采用原始析构函数方式，则根本不要使用 delete[] 运算符。删除操作差不多"call destructors + deallocate memory"。因此，如果您手动销毁，那么对 delete[] 的额外调用将导致未定义的行为。除非你真的分配 char 内存（不管 T）并使用 placement new（这也需要一些手动大小和偏移量计算）。这是实现此类向量的好方法，尽管需要格外小心（手动内存跟踪是 b***h）。
当您在标准向量上 pop_back 时，您实际上并没有释放关联的内存。只有最后一个元素被销毁， size 减少但 capacity 没有。没有其他元素被复制或移动。这很难用自定义容器复制，因为您不能 delete 或销毁数组的单个元素。
因此 std::vector<T> 实际上并没有使用 T 的数组。它分配原始未初始化的内存（类似于 std::aligned_storage) and performs placement new 以根据需要在该分配中创建元素。Placement new 是 new 的一个版本，它不分配，而是在应该分配的位置给出一个指针构造对象。这意味着对象的生命周期与它的分配没有直接关联，并且唯一地允许您单独销毁元素，而无需通过调用它的析构函数释放它的底层内存。在内部，它看起来像 pop_back() { back().~T(); --size; }。
您在实现复杂度为 O(1) 的 pop_back() 时遇到困难的原因是，通过使用 new[] 和 delete[]，您将 捆绑在一起包含对象的生命周期 与对象的存储。我的意思是，当您使用 new T[n]; 创建一个动态分配的原始数组时，会发生两件事：1) 分配存储空间和 2) 在该存储空间中构造对象。相反，delete[]会先销毁所有对象（调用它们的析构函数），然后然后将底层内存释放回系统。
C++ 确实提供了分别处理存储和生命周期的方法。这里涉及的主要内容是原始存储、放置new、指针转换和令人头疼的问题。
在您的 pop_back() 函数中，您似乎希望能够仅销毁数组中的一个对象 而不会 销毁所有其他对象或释放它们的存储空间。不幸的是，使用 new[] 和 delete[] 是不可能的。 std::vector 和其他一些容器解决此问题的方法是使用低级语言功能。通常，这是通过分配一个连续的原始内存区域（输入为 unsigned char 或 std::byte，或使用像 std::aligned_storage 这样的助手）来完成的，执行 ton 的簿记和安全检查以及额外的工作，然后使用 placement new 在原始内存中构造一个对象。要访问该对象，您需要计算原始内存（的数组）中的偏移量，并使用 reinterpret_cast 生成指向您放置在那里的对象的指针。这也需要显式调用对象的析构函数。在这个低级别上工作，实际上对象生命周期的每个细节都掌握在您手中，这是非常乏味且容易出错的。我不建议这样做。但这是可能的，它允许 std::vector::pop_back() 以 O(1) 复杂度实现（并且不会使先前元素的迭代器失效）。
I was wondering how is pop_back() implemented so that it has constant complexity? It has to reduce the size by 1 and delete the last element.
没错。这就是它所要做的。不管你总共有多少个元素。
这就是常量复杂性的定义。
Now I saw somewhere that it basically reduces the size by 1 and destroys last element via some iterator/pointer
没错。内存仍然被分配，但是住在那里的对象经历了逻辑销毁。
but then why couldn't we implement pop_front() the same way and just redirect our pointer to first element to the next one?
你可以！这就是 std::deque 的工作原理，这就是为什么 std::deque 的 pop_front() 具有恒定的复杂性。
但是，你不能在维护其他廉价操作的同时进行，因为它一定会在几次后造成内存碎片。内存以块的形式分配，向量需要以连续的块分配。想象一下，如果您 pop_front() 了第一个元素，向量只是 "ignored" - 现在这样做五百次。你有未使用的记忆永远坐在那里。不好！如果你现在想添加到前面怎么办？最终，除非您想最终使用无限内存，否则您必须将内存分成不同的块，但这会破坏连续性保证。
其他容器旨在为您提供您想要的，但需要权衡取舍。特别是，std::deque 不能保证连续存储。这就是它如何防止始终留下大量未使用的内存。
我刚刚开始使用我的数据结构，并且正在实现某种数组列表 (~=std::vector)。我想知道 pop_back() 如何实现以使其具有恒定的复杂性？它必须将大小减 1 并删除最后一个元素。现在我在某处看到它基本上将大小减小 1 并通过一些 iterator/pointer 销毁最后一个元素，但是为什么我们不能以相同的方式实现 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;
}
pop_back() 通常不是这样实现的。虽然这是一个实现细节，但通常您的 list/vector/dynamic 数组会跟踪两种大小：一种是列表的实际大小，另一种是容量。容量是底层分配内存的大小。现在 pop_back() 只是将大小减 1 并在最后一个元素上运行析构函数（不要混淆析构，即调用 ~T() 方法和 delete 运算符）。它不会重新定位任何东西。容量保持不变。整个操作不依赖于列表的大小（与您的实现不同）。
请注意，您无法通过简单的方式对 pop_front() 执行相同的操作。您将必须跟踪列表的开头和结尾以及底层内存（并且取决于方法：存储大小和容量或在运行时计算它们）。这需要更多的内存和可能更多的 cpu 操作。而且这样的结构也变得很奇怪。你知道容量，你知道大小，但你实际上不知道在调整大小发生之前你可以做多少 push_back() （你只知道这个数字受 "capacity minus size" 限制，但它可以是更小）。除非您将此信息添加到您的结构中，否则它会再次占用内存或 cpu.
旁注： 如果您打算采用原始析构函数方式，则根本不要使用 delete[] 运算符。删除操作差不多"call destructors + deallocate memory"。因此，如果您手动销毁，那么对 delete[] 的额外调用将导致未定义的行为。除非你真的分配 char 内存（不管 T）并使用 placement new（这也需要一些手动大小和偏移量计算）。这是实现此类向量的好方法，尽管需要格外小心（手动内存跟踪是 b***h）。
当您在标准向量上 pop_back 时，您实际上并没有释放关联的内存。只有最后一个元素被销毁， size 减少但 capacity 没有。没有其他元素被复制或移动。这很难用自定义容器复制，因为您不能 delete 或销毁数组的单个元素。
因此 std::vector<T> 实际上并没有使用 T 的数组。它分配原始未初始化的内存（类似于 std::aligned_storage) and performs placement new 以根据需要在该分配中创建元素。Placement new 是 new 的一个版本，它不分配，而是在应该分配的位置给出一个指针构造对象。这意味着对象的生命周期与它的分配没有直接关联，并且唯一地允许您单独销毁元素，而无需通过调用它的析构函数释放它的底层内存。在内部，它看起来像 pop_back() { back().~T(); --size; }。
您在实现复杂度为 O(1) 的 pop_back() 时遇到困难的原因是，通过使用 new[] 和 delete[]，您将 捆绑在一起包含对象的生命周期 与对象的存储。我的意思是，当您使用 new T[n]; 创建一个动态分配的原始数组时，会发生两件事：1) 分配存储空间和 2) 在该存储空间中构造对象。相反，delete[]会先销毁所有对象（调用它们的析构函数），然后然后将底层内存释放回系统。
C++ 确实提供了分别处理存储和生命周期的方法。这里涉及的主要内容是原始存储、放置new、指针转换和令人头疼的问题。
在您的 pop_back() 函数中，您似乎希望能够仅销毁数组中的一个对象 而不会 销毁所有其他对象或释放它们的存储空间。不幸的是，使用 new[] 和 delete[] 是不可能的。 std::vector 和其他一些容器解决此问题的方法是使用低级语言功能。通常，这是通过分配一个连续的原始内存区域（输入为 unsigned char 或 std::byte，或使用像 std::aligned_storage 这样的助手）来完成的，执行 ton 的簿记和安全检查以及额外的工作，然后使用 placement new 在原始内存中构造一个对象。要访问该对象，您需要计算原始内存（的数组）中的偏移量，并使用 reinterpret_cast 生成指向您放置在那里的对象的指针。这也需要显式调用对象的析构函数。在这个低级别上工作，实际上对象生命周期的每个细节都掌握在您手中，这是非常乏味且容易出错的。我不建议这样做。但这是可能的，它允许 std::vector::pop_back() 以 O(1) 复杂度实现（并且不会使先前元素的迭代器失效）。
I was wondering how is pop_back() implemented so that it has constant complexity? It has to reduce the size by 1 and delete the last element.
没错。这就是它所要做的。不管你总共有多少个元素。
这就是常量复杂性的定义。
Now I saw somewhere that it basically reduces the size by 1 and destroys last element via some iterator/pointer
没错。内存仍然被分配，但是住在那里的对象经历了逻辑销毁。
but then why couldn't we implement pop_front() the same way and just redirect our pointer to first element to the next one?
你可以！这就是 std::deque 的工作原理，这就是为什么 std::deque 的 pop_front() 具有恒定的复杂性。
但是，你不能在维护其他廉价操作的同时进行，因为它一定会在几次后造成内存碎片。内存以块的形式分配，向量需要以连续的块分配。想象一下，如果您 pop_front() 了第一个元素，向量只是 "ignored" - 现在这样做五百次。你有未使用的记忆永远坐在那里。不好！如果你现在想添加到前面怎么办？最终，除非您想最终使用无限内存，否则您必须将内存分成不同的块，但这会破坏连续性保证。
其他容器旨在为您提供您想要的，但需要权衡取舍。特别是，std::deque 不能保证连续存储。这就是它如何防止始终留下大量未使用的内存。