Что должен вернуть метод pop(), когда стек пуст?

Возможный дубликат:
Вопрос стека STL: почему pop() не выдает исключение, если стек пуст?

При проектировании стека в С++, что должен сделать метод pop() (или front()), когда стек пуст? Какой из следующих вариантов лучше?

Выбросить исключение
Undefined, но требует, чтобы пользователь вызывал метод isempty() для проверки перед вызовом pop()
Возвращает код bool, используя дополнительный параметр (ссылку), чтобы передать popped element
Определить уникальный пустой элемент

Хорошо, я вижу, что мой вопрос не так ясен, позвольте мне переписать его:

Существуют некоторые структуры данных, которые могут быть реализованы на основе связанного списка, такого как стек, очередь, и каждый из них имеет методы, возвращающие передний элемент (или хвост).

Я хочу знать, существует ли какое-либо принципиальное правило о разработке такого метода в отношении случая, когда данные пусты.

И мое определение лучше "легко использовать правильно и трудно использовать неправильно".

Ответ 1

Стиль программирования по контракту будет заключаться в том, что наличие непустого стека является предварительным условием вызова pop, а вызов метода без удовлетворения его предварительных условий имеет результат undefined, Моя реализация выбрала бы std::logic_error, но это не потребовалось бы. В C моя реализация была бы abort через assert.

Вызывающий pop отвечает за то, что перед тем, как позвонить pop, убедитесь, что предварительная проверка того, что стек не пуста, выполняется. Поэтому стек должен иметь метод isEmpty для проверки вызывающего.

Ответ 2

С++ STL actall ничего не возвращает через pop(), так как он отбрасывает возвращающее значение объекта и фактически выталкивает объект из внутренней структуры данных стека, делая их двумя отдельными функциями. Так что еще один вариант для рассмотрения в вашей структуре структуры данных стека.

Ваш третий вариант также является довольно идиоматическим подходом для этих типов структур данных.

Для вашего четвертого варианта, а не для "уникального пустого элемента", я бы сделал вариант вашего третьего варианта, где ваша функция pop(), которая принимает аргумент указателя, а не ссылочный тип, и возвращает NULL, если есть в стек не осталось объектов.

Ответ 3

Какой тип среды является кодом для запуска? Часто гораздо лучше соответствовать существующим парадигмам поведения, чем ударять по собственному пути выполнения вещей.

Когда вы запрашиваете элемент из пустого абстрактного списка, генерирует ли оно исключение? Если это так, гораздо лучше сделать исключение из не-полного стека исключение.

Undefined поведение - плохой выбор, когда тривиально легко определить поведение.

Если большая часть кода возвращает элементы через оператор return, то возврат элемента управления (bool for if it works) является плохим дизайном. Если большая часть кода возвращает элементы через список параметров, то возврат элемента управления с помощью оператора return является хорошим дизайном при условии, что другие вызовы аналогичных коллекций аналогичны.

Пустой элемент не имеет большого смысла, он становится магическим значением. Например, если я создаю список и нажимаю на него пять пустых элементов, это то же самое, что и список без пустых элементов в нем? Это то же самое, что и список с одним пустым элементом? Это тот же список с некоторыми элементами и пустой элемент в нем? Пустые списки, являющиеся "особым" объектом, - это одно, но пустые элементы проблематичны, потому что на самом деле они не содержат поведения элемента, они содержат поведение списка. Хорошая ориентация объекта имеет содержание поведения, инкапсулированного в том же объекте, который он описывает.

Обратите внимание, что пустые элементы не совпадают с часовыми. Стражи - это детали реализации, содержащиеся в коллекции (и в идеале никогда не должны подвергаться внешнему воздействию). Когда я читаю "возвращает пустой элемент", я думаю, что нужно было бы хорошо разбираться в реализации стека, чтобы использовать его. Слишком большая близость между классами называется жесткой связью, и это может сделать код намного сложнее изменить/исправить/изменить в будущем.

Если вы нарушаете свой собственный способ делать что-то, тогда вы должны минимально заставлять всю свою сторону кода вести себя одинаково. Это облегчает чтение содержания.

Ответ 4

реализация SGI STL стека имеет эту конструктивную заметку:

Можно спросить, почему pop() возвращает void вместо value_type. Что есть, почему нужно использовать top() и pop() для проверки и удаления верхней элемент, вместо объединения двух в одну функцию-член? В факт, есть веская причина для этого дизайна. Если pop() вернул верхний элемент, он должен был бы вернуться по значению, а не по reference: return by reference создаст висячий указатель. Вернуть по стоимости, однако, является неэффективным: он включает по меньшей мере один избыточный вызов конструктора копии. Поскольку pop() не может возвращать ценности, чтобы быть как эффективным, так и правильным, это больше разумно для него не возвращать никакого значения вообще и требовать от клиентов используйте top() для проверки значения в верхней части стека.

SGI дополнительно указывает на pop():

Условие: empty() - false. Postcondition: size() будет уменьшен на 1.

Что касается поведения top(), SGI определяет это:

Условие: empty() - false.

Ответ 5

Я бы использовал тип опции, возможно Boost.Optional. Он специально разработан для поддержки дополнительных возвращаемых значений, которые вы действительно хотите здесь.

Ответ 6

Я мог бы предложить использовать методы pop и trypop. pop будет просто вызывать trypop и бросать и исключать, если он терпит неудачу. Мое рассуждение состоит в том, что для некоторых применений стека, пытаясь выскочить, когда пуст пуст, указывает на ошибку логики программы, которой не должно быть: либо неуравновешенный push/pop, либо неправильное обращение с более ранним отказом от из-за исчерпания ресурсов, Для других применений отказ от всплытия означает, что вы находитесь в конце ввода. При использовании модели программирования с исключениями, различая эти виды использования, вы можете избежать загромождения вызывающего абонента выполнением проверки пустого стека и выброса исключения.