std::vector pop_back() 实现

Question

std::vector pop_back() 实现

3

我刚开始学习数据结构，正在实现一种类似于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;
}

- Zlatan Radovanovic

你的问题是关于 pop_back() 还是 pop_front() 的？ - JohnFilleau

对于 pop_back()，您实际上不必删除/销毁最后一个元素。您只需将指针减少到数组的最后一个元素或减少大小成员（取决于您如何实现此操作）。为了 pop_front()，您仍然需要减小大小，但现在您必须将元素向前移动或增加前指针。同样取决于您的实现方式。重点是您不必费力去删除该元素。只需停止使用该元素即可。 - LLSv2.0

顺便提一下，我几个月前读了一篇关于一种数据结构的文章，类似于“vector”，它可以从中间增长，使得快速的前端操作也成为可能，但是我忘记它的名字了。在那种情况下，你可以以大致相同的方式实现“pop_front”。 - chris

@LLSv2.0 pop_back()一定要销毁最后一个元素。如果该元素有析构函数，则需要运行析构函数并结束元素的生命周期。 - François Andrieux

1

@chris 嗯，有一个名为 std::deque 的容器。它不像 vector 那样是连续的，但具有随机访问和快速从前面和后面插入/删除的功能。 - Kevin

@Kevin，确实有这样的情况。我特别记得有人发布了关于他们自己创建的东西以及它如何解决deque无法很好处理的问题的帖子。 - chris

4个回答

3

你之所以难以实现具有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），进行大量的簿记和安全检查和额外的工作，然后使用定位new在该原始内存中构造一个对象。要访问对象，您需要计算偏移量到原始存储器（数组）中，并使用reinterpret_cast将其转换为指向放置在那里的对象的指针。这还需要显式调用对象的析构函数。在这个低级别上工作，对象生命周期的每个细节都在你手中，而且非常繁琐和容易出错。我不建议这样做。但是它是可能的，并且可以使std::vector::pop_back()在O(1)复杂度下实现（并且不会使之前元素的迭代器无效）。

- alter_igel

不要使用reinterpret_cast将原始内存转换为对象指针。放置new已经返回一个正确的有效指向创建对象的指针。 - François Andrieux

@FrançoisAndrieux 是的，但是假设一个vector 的实现仅存储指向std::byte或std::aligned_storage数组的指针，那么您如何获取该数组中第i个元素的指针？ - alter_igel

我同意，一旦你知道该怎么做，这并不难。如果一个刚学会使用 new[] 和 delete[] 的人试图通过试错来完成这种操作，那将是一场灾难。 - alter_igel

“如何获取第i个元素的指针” 我之前没有考虑过这个问题，确实不实际存储每个元素的地址。你需要使用指针算术运算。但是由于这些元素实际上并不是数组对象的一部分，我想知道这种算法的可移植性如何。我不确定在不依赖于实现定义的行为的情况下如何实现它... 编辑：或者它们是否是数组对象的一部分？ - François Andrieux

1

不，为了澄清，当我做这种事情时，我的代码有70%的assert和static_assert，因为这种低级控制的数量让我感到非常焦虑。 - alter_igel

显示剩余2条评论

1

当你在标准向量上使用pop_back时，实际上并没有释放相关内存。只有最后一个元素被销毁，size会减小，但capacity不会变化。没有其他元素被复制或移动。这很难在自定义容器中复制，因为无法删除或销毁数组的单个元素。

因此，std::vector<T> 实际上并没有使用 T 数组。它分配了未初始化的原始内存（类似于 std::aligned_storage），并执行就地 new 以根据需要在该分配中创建元素。就地 new 是 new 的一种版本，它不会分配内存，而是给出一个指针，指向应构造对象的位置。这意味着对象的生命周期与其分配不直接关联，并且唯一允许您通过调用其析构函数单独销毁元素而不释放其基础内存。在内部，它看起来像是这样的pop_back() { back().~T(); --size; }。

- François Andrieux

为什么我不能通过显式调用数组的析构函数来删除例如最后一个元素？就像你在答案末尾所写的那样。 - Zlatan Radovanovic

1

如果您这样做，当您最终在容器的生命周期结束时或者需要扩展数组时使用delete[]删除数组，它将再次调用析构函数。我所写的代码仅适用于元素使用了放置new的情况。 - François Andrieux

0

我在想pop_back()是如何实现常数复杂度的？它必须将大小减1并删除最后一个元素。

没错，就是这样。无论你有多少元素。

这就是常数复杂度的定义。

现在我看到有人说它基本上通过一些迭代器/指针将大小减1并销毁最后一个元素。

没错。内存仍然被分配，但其中的对象经历了逻辑销毁。

但为什么我们不能用同样的方式实现pop_front()，并将指针重定向到下一个元素的第一个元素呢？

你可以！这就是std::deque的工作原理，这就是为什么std::deque具有具有常数复杂度的pop_front()的原因。

然而，你不能在保持其他廉价操作的同时这样做，因为它必然会在几次后导致内存碎片化。内存是以块分配的，而向量需要在连续的块中分配。想象一下，如果你使用 pop_front() 删除了第一个元素，那么向量就会“忽略”它——现在重复这个过程五百次。你会有未使用的内存一直存在。这不好！如果现在你想要添加到前面呢？最终，除非你想要无限制地使用内存，否则你必须将内存分成不同的块，但这会破坏保证的连续性。

其他容器旨在给你想要的东西，但需要进行权衡。特别地，std::deque 无法保证连续的存储。这就是它如何防止一直留下大量未使用的内存。

- Asteroids With Wings

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- freakish · Accepted Answer

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

请注意，您无法以简单的方式使用pop_front()执行相同的操作。您必须跟踪列表的开始和结束以及底层内存（根据方法的不同：存储大小和容量或在运行时计算它们）。这需要更多的内存和潜在的CPU操作。而且这样的结构变得奇怪。您知道容量，您知道大小，但实际上您不知道在发生调整大小之前可以进行多少次push_back()（您只知道该数字受“容量减去大小”的限制，但它可能更小）。除非您将此信息添加到结构中，否则会占用内存或CPU。 < p >< em >顺便提一下：如果你要采用原始析构函数的方式，那么根本不要使用 < code >delete[] 运算符。删除操作基本上是“调用析构函数+释放内存”。因此，如果您手动销毁，那么对 < code >delete[] 的额外调用将导致未定义的行为。除非您实际分配了 < code >char 内存（无论 < code >T 如何），并使用 placement new（这也需要一些手动大小和偏移计算）。这是实现这种向量的好方法，但需要额外小心（手动内存跟踪很麻烦）。