如何高效地清空C++中的栈？

Question

我有一个名为pages的C++栈。 由于没有clear()函数可以清空栈，所以我编写了以下代码：

stack<string> pages;
//here is some operation
//now clearing the stack
while(!pages.empty())
    pages.pop();

现在我的问题是：是否有更好的高效方式来清空栈？

- Misbah Ahmad

---

你是否尝试过将一个空栈赋值给你的栈？ - krzaq

不，谢谢你的建议 (y) - Misbah Ahmad

你问到了效率问题。创建一个新的栈可能不会更高效，因为它会导致更多的堆分配。底层容器默认情况下将是一个 deque。如果你使用一个 deque 或 vector，你将浪费已经为容器声明的分配内存，否则这些内存可以被重复利用。 - Paul Rooney

@PaulRooney 反过来也可以使用同样的论点。在循环中销毁具有平凡析构函数的类型可能比（可能省略的）分配更浪费。此外，保留分配的内存可能与他想要的相反。这完全取决于做出明智的决策。 - krzaq

当然。我并不是在说一个比另一个好，只是根据原帖作者的需求，这是需要考虑的事情。 - Paul Rooney

不确定您真正遇到的效率问题是什么，但您总是可以通过牺牲空间来换取速度。不要清除容器，而是保留一个额外的标志来指示它应被视为空。将容器和标志包装在自己的类中。 - Christian Hackl

Answer 1

通常情况下，你无法在O(1)的时间内清空复制容器，因为你需要销毁这些副本。但是，一个模板化的复制容器可能会有一个偏特化，以O(1)时间清空，并且由指示所包含对象类型具有平凡析构函数的特征触发。

如果你想避免循环操作。

pages=stack<std::string>();

或者

stack<std::string>().swap(pages);

- v78

---

有没有一种方法可以不需要显式声明类型来实现这个（在C++14中）？ - John H.

除了array之外，所有容器都有clear函数。这是为什么stack没有clear函数的原因吗？如果是这样，忽略或避免这个例外岂不更有用？在使用stack时，没有clear函数似乎很奇怪。 - John H.

@JohnH. 是的：pages = {}; - jhasse

当我使用它时，它会清空所有其他栈，我不确定出了什么问题。 - Joseph

你的堆栈可能只是一个实际对象的所有引用。@Joseph。 - v78

Answer 2

我认为没有更有效的方法了。栈是一种定义明确的数据类型，专门设计用于LIFO上下文中操作，并且不打算一次性清空。

为此，您可以使用vector或deque（或list），它们基本上是基础容器； stack实际上是一个容器适配器。有关更多信息，请参见此C++参考文献。

如果您别无选择，必须使用栈，那么您所做的方式就没有错。无论如何，如果构造了元素，这些元素都必须被销毁，无论是分配新的空栈还是弹出所有元素等等。

我建议改用vector; 它确实具有您需要的操作：

• size（或resize）
• empty
• push_back
• pop_back
• back
• clear

这只是更方便，因此您可以使用clear方法。不确定是否真正使用vector会更高效; 栈操作基本相同。

- Ely

Answer 3

把一个新的空栈分配给它怎么样？

pages = stack<string>();

它不会逐个删除元素，并且使用移动赋值，因此具有潜力非常快。

- Piotr Siupa

Answer 4

将其转换为智能指针：

stack.reset();
stack = make_shared<stack<string>>();

- Tracker647

Answer 5

关于子类化std::stack并实现一个简单的clear()方法，像这样访问底层容器c，你怎么看？

public:
    void clear() { c.clear(); }

- serget

---

这是非标准化的且一个糟糕的想法，因为有几个原因。底层容器名称将根据实现而变化，并且不能保证实现不依赖于除底层容器之外的某些变量，清除它可能会破坏堆栈的状态。 - asu

尽管这个答案受到了批评，但它似乎是最高效的解决方案，如果不考虑可移植性的话。 - The Matt

底层容器的类型将是什么？ - Mikolasan