Почему pop() принимает аргумент?

Question

Quick background
Я разработчик Java, который играл со С ++ в свободное время.

Предисловие
В C++, вы часто видите поп принимает аргумент по ссылке:

void pop(Item& removed); 

Я понимаю, что это хорошо «заполнить» параметр с тем, что вы удалили. Для меня это совершенно разумно. Таким образом, человек, который попросил удалить верхний элемент, может посмотреть, что было удалено.

Однако, если бы я сделать это в Java, я хотел бы сделать что-то вроде этого:

Item pop() throws StackException; 

Таким образом, после того, как поп мы возвращаем либо: NULL в результате, элемент, или исключение будет выбрано.

В моем текстовом сборнике на C++ показан пример выше, но я вижу много реализаций стека без аргументов (например, stl stack).

Вопрос
Как следует реализовать функцию поп в C++?

Бонус
Почему?

Answer 1

Чтобы ответить на вопрос: вы не должны реализовывать функцию pop в C++, поскольку она уже реализована STL. Адаптер контейнера предоставляет метод top для получения ссылки на верхний элемент в стеке и метод pop для удаления верхнего элемента. Обратите внимание, что один метод pop не может использоваться для выполнения обоих действий по вашему запросу.

Зачем это делается так?

1. Исключение безопасности: Herb Sutter дает хорошее объяснение этого вопроса в GotW #82.
2. Принцип единой ответственности: также упоминается в GotW # 82. top берет на себя ответственность и pop заботится о другом.
3. Не платите за то, что вам не нужно: Для некоторого кода может быть достаточно изучить верхний элемент, а затем поместить его, не создавая (потенциально дорого) копию элемента. (Об этом говорится в документации SGI STL.)

Любой код, который желает получить копию элемента может сделать это без каких-либо дополнительных затрат:

Foo f(s.top()); 
s.pop(); 

Кроме того, this discussion может быть интересно.

Если вы собираетесь реализовать pop, чтобы вернуть значение, неважно, вернетесь ли вы по значению или напишите его в параметр out.Большинство компиляторов реализуют RVO, что оптимизирует метод return-by-value так же эффективно, как метод copy-in-out-parameter. Просто имейте в виду, что любой из них, вероятно, будет менее эффективен, чем исследование объекта с помощью top() или front(), поскольку в этом случае абсолютно не выполняется копирование.

Answer 2

Проблема с подходом Java заключается в том, что его метод pop() имеет как минимум два эффекта: удаление элемента и возврат элемента. Это нарушает принцип единоначалия разработки программного обеспечения, который, в свою очередь, открывает двери для сложностей дизайна и других вопросов. Это также подразумевает штраф за исполнение.

В способе STL идеи такова, что иногда, когда вы pop(), вы не заинтересованы в том, что элемент появился. Вам просто нужен эффект удаления верхнего элемента. Если функция возвращает элемент, и вы игнорируете его, то это потерянная копия.

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

СТЛ не перегружать pop() функции, а разбивает их на две функции: back() (или top() в случае std::stack адаптера) и pop(). Функция back() просто возвращает элемент, а функция pop() просто удаляет ее.

Answer 3

Единственная причина, я могу видеть, для использования этого синтаксиса в C++:

void pop(Item& removed); 

, если вы беспокоитесь о ненужных копиях происходящих.

если вы возвращаете Item, он может потребовать дополнительную копию объекта, который может быть дорогим.

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

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

Более подробная информация here

Answer 4

IMO, хорошая подпись для eqivalent из pop функции Java в C++ будет что-то вроде:

boost::optional<Item> pop(); 

Использование типов параметров является лучшим способом, чтобы вернуть то, что может или могут быть недоступны.

Answer 5

Использование C++ 0x делает все это снова трудным.

В

stack.pop(item); // move top data to item without copying 

позволяет эффективно перемещать верхний элемент из стека. В то время как

item = stack.top(); // make a copy of the top element 
stack.pop(); // delete top element 

не допускает таких оптимизаций.