C++ 当堆栈为空时，'pop()' 方法应该返回什么？

What should the 'pop()' method return when the stack is empty?

提问by zhanwu

Possible Duplicate:
C++ STL stack question: Why does pop() not throw an exception if the stack is empty?

可能的重复：
C++ STL 堆栈问题：如果堆栈为空，为什么 pop() 不抛出异常？

When designing a stack in C++, what should the pop()method (or front()method) return when the stack is empty? Which of the following design is better?

在C++中设计堆栈时，当堆栈为空时pop()方法（或front()方法）应该返回什么？以下哪个设计更好？

1. Throw an exception
2. Undefined, but require the user calling isempty()method to check before calling pop()
3. Return a bool code, while using an extra parameter (a reference) to pass the popped element
4. Define an unique empty element

1. 抛出异常
2. 未定义，但要求用户在调用pop()之前调用isempty()方法进行检查
3. 返回一个 bool 代码，同时使用一个额外的参数（一个引用）来传递弹出的元素
4. 定义一个唯一的空元素

---

---

OK, I see that my question is not that clear, let me try to rewrite it:

好吧，我看我的问题不是那么清楚，让我尝试重写它：

There are some data structures which can be implemented based on linked list like stack, queue, and each of them has a methods returning the front element (or the tail).

有一些数据结构可以基于链表来实现，比如栈、队列，它们每个都有一个返回前端元素（或尾部）的方法。

I want to know, is there any principle guideline about designing such a method regarding the case when the data is empty.

我想知道，对于数据为空的情况，是否有设计这种方法的原则指南。

And my definition of better is "easy to use correctly and hard to use incorrectly".

我对更好的定义是“容易正确使用，难以错误使用”。

回答by Raedwald

The programming-by-contract style would be that having a non-empty stack is a preconditionof calling pop, and that calling a method without meeting its preconditions has an undefinedoutcome. My implementation would throw a std::logic_error, but that would not be required. In C, my implementation would abortvia assert.

契约式编程风格将拥有非空堆栈是调用的前提条件pop，并且在不满足其前提条件的情况下调用方法具有未定义的结果。我的实现会抛出std::logic_error，但这不是必需的。在 C 中，我的实现将abort通过assert.

The caller of popis responsible for ensuring that the precendition that the stack is not empty holds before calling pop. The stack should therefore have an isEmptymethod for the caller to check.

的调用者pop负责确保在调用之前栈不为空的优先级成立pop。因此堆栈应该有一个isEmpty方法供调用者检查。

回答by Jason

The C++ STL actuall doesn't return anything via pop()since it decouples returning the value of an object and actually popping an object off the stack's internal data-structure, making them two separate functions. So that's another option to consider in your design of a stack data-structure.

C++ STL 实际上不返回任何内容，pop()因为它将返回对象的值与实际从堆栈的内部数据结构中弹出对象分离，使它们成为两个独立的函数。所以这是您在设计堆栈数据结构时要考虑的另一种选择。

Your third option is also a pretty idiomatic approach for these types of data-structures.

对于这些类型的数据结构，您的第三个选择也是一种非常惯用的方法。

For your fourth option, rather than a "unique empty element", I would actually do a variation on your third option where your pop()function that takes a pointer argument rather than a reference type, and returns NULL if there are no objects left in the stack.

对于您的第四个选项，而不是“唯一的空元素”，我实际上会对您的第三个选项进行变体，其中您的pop()函数采用指针参数而不是引用类型，如果堆栈中没有对象，则返回 NULL .

回答by Edwin Buck

Which environment type is the code to run in? Often it is far better to match existing paradigms of behavior than to strike out on your own way of doing things.

代码运行在哪种环境类型？通常，与现有的行为范式相匹配，比以自己的方式做事要好得多。

When you ask for a element from an empty abstract list, does it throw an exception? If so, it is far better to make popping off a non-full stack throw an exception.

当你从一个空的抽象列表中请求一个元素时，它会抛出异常吗？如果是这样，最好让弹出非满堆栈抛出异常。

Undefined behavior is a bad choice when it is trivially easy to define the behavior.

当定义行为非常容易时，未定义的行为是一个糟糕的选择。

If most of the code returns items via the return statement, then returning a control (bool for if it worked) is a bad design. If most of the code returns items via the parameter list, then returning a control via the return statement is a good design provided that the other calls on similar collections do likewise.

如果大部分代码通过 return 语句返回项目，那么返回一个控件（如果它有效则为 bool）是一个糟糕的设计。如果大部分代码通过参数列表返回项目，那么通过 return 语句返回控件是一个很好的设计，前提是对类似集合的其他调用也这样做。

An empty element doesn't make a lot of sense, it becomes a magic value. For example, if I create a list and push five empty elements in it, is it the same as a list with no empty elements in it? Is it the same as a list with one empty element in it? Is it the same a list with some elements and an empty element in it? Empty lists being a "special" object is one thing, but empty elements are problematic because they don't really contain the behavior of the element, they contain the behavior of the list. Good object orientation has contents of the behavior encapsulated in the same object it describes.

一个空元素没有多大意义，它变成了一个魔法值。例如，如果我创建一个列表并在其中推送五个空元素，它是否与其中没有空元素的列表相同？它与包含一个空元素的列表相同吗？它是一个包含一些元素和一个空元素的列表吗？空列表是“特殊”对象是一回事，但空元素是有问题的，因为它们并不真正包含元素的行为，它们包含列表的行为。良好的面向对象将行为的内容封装在它所描述的同一对象中。

Note that empty elements are not the same as sentinels. Sentinels are implementation details contained within a collection (and ideally should never be exposed externally). When I read "returns an empty element", I think one would have to be intimately knowledgeable about the implementation of the stack to use it. Too much intimacy between classes is called tight coupling, and it can make the code much more difficult to modify / fix / change going forward.

请注意，空元素与哨兵不同。哨兵是包含在集合中的实现细节（理想情况下永远不应该暴露在外部）。当我读到“返回一个空元素”时，我认为必须非常了解堆栈的实现才能使用它。类之间过于紧密的联系称为紧耦合，它会使代码更难修改/修复/更改。

If you do strike out on your own way of doing things, then you should minimally make your entire side of the code behave the same. It makes it easier to read an maintain.

如果您确实以自己的方式做事，那么您应该至少使代码的整个方面表现相同。它使阅读维护变得更容易。

回答by R.. GitHub STOP HELPING ICE

I might suggest having both popand trypopmethods. popwould simply call trypopand throw and exception if it fails. My reasoning is that, for some uses of a stack, attempting to pop when the stack is empty is indicative of a program logic error that should not happen - either unbalanced push/pop, or mishandling of an earlier failure to push due to resource exhaustion. For other uses, failure to pop just means you're at the end of input. When using a programming model with exceptions, distinguishing these uses allows you to avoid cluttering the caller with performing the check for empty stack and throwing the exception.

我可能会建议同时使用pop和trypop方法。如果失败，pop将简单地调用trypop并抛出和异常。我的推理是，对于堆栈的某些用途，当堆栈为空时尝试弹出表示不应该发生的程序逻辑错误 - 不平衡的推送/弹出，或由于资源耗尽导致的早期推送失败的错误处理. 对于其他用途，无法弹出仅意味着您处于输入的末尾。当使用带有异常的编程模型时，区分这些用途可以避免调用者执行空堆栈检查和抛出异常而使调用者混乱。

回答by Gnawme

The SGI STL implementation of stackhas this design note:

堆栈的SGI STL 实现有这样的设计说明：

One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at alland to require clients to use top() to inspect the value at the top of the stack.

有人可能想知道为什么 pop() 返回的是 void，而不是 value_type。也就是说，为什么必须使用 top() 和 pop() 来检查和删除顶部元素，而不是将两者组合在一个成员函数中？事实上，这种设计是有充分理由的。如果 pop() 返回顶部元素，则它必须按值而不是按引用返回：按引用返回将创建一个悬空指针。然而，按值返回是低效的：它至少涉及一个冗余的复制构造函数调用。由于 pop() 不可能以既高效又正确的方式返回值，因此它根本不返回任何值并要求客户端使用 top() 检查值更明智栈顶。

SGI further specifies for pop():

SGI 进一步规定了 pop()：

Precondition: empty() is false. Postcondition: size() will be decremented by 1.

前提条件：empty() 为假。后置条件：size() 将减 1。

As for the behavior of top(), SGI specifies this:

至于 top() 的行为，SGI 是这样规定的：

Precondition: empty() is false.

前提条件：empty() 为假。

回答by Nemanja Trifunovic

I'd use an option type, perhaps Boost.Optional. It is specifically designed to provide support for optional return values, which is really what you want here.

我会使用一个选项类型，也许是Boost.Optional。它专门设计用于提供对可选返回值的支持，这正是您在这里想要的。