8

So, it would seem that the segregation of .top and .pop in stack is no longer needed to be so strict in C++11.

Maybe I am missing something, but the problem in C++03 and previous was that if .pop were to return a value, there was a danger the copy operation could throw an exception during the element copy. Example (code sample taken from here):

template <class T>
    // T must have default ctor and copy assignment
class Stack
{
public:
    Stack();
    ~Stack();
    Stack(const Stack&);
    Stack& operator=(const Stack&);

    unsigned Count();   // returns # of T's in the stack
    void     Push(const T&);
    T        Pop();     // if empty, returns default-
                        // constructed T
    T        Top();     // For backwards compatibility
                        // 

private:
    T*       v_;        // pointer to a memory area big
                        //  enough for 'vsize_' T objects
    unsigned vsize_;    // the size of the 'v_' area
    unsigned vused_;    // the number of T's actually
                        //  used in the 'v_' area
};

If you are to do this:

int main(){
  Stack<vector<double>> stack;
  fill_stack(stack); //fill stack with huge vectors
  stack.pop(); //danger of exception being throw from low memory
}

In C++11 this problem goes entirely away since the element can be moved from the stack, entirely eliminating the exception safety concern. That is under the presumption that the element is movable and that the move operation will not throw.

So, my question boils down to, is there a real concert to safety exception concern if .pop were to return the element via move semantics?

dyp
  • 38,334
  • 13
  • 112
  • 177
Honf
  • 215
  • 1
  • 6
  • 1
    *"That is under the presumption that the element is movable and that the move operation will not throw."* That's a wrong assumption. Maybe I can dig out a proposal later that introduced / allowed throwing move operations. Move operations can (partially) copy things, e.g. for older data types w/o move support. – dyp Dec 25 '13 at 19:36
  • 7
    Here it is: [n3050](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3050.html). The Standard Library is intended to be a tool useful for almost everyone, so it cannot ignore throwing move operations. There's an unfortunate consequence: you currently cannot use move-only types (directly) in `stack` and `priority_queue` (etc.), since they can only be *copied* out. AFAIK, this is still the case in the latest drafts of C++1y. – dyp Dec 25 '13 at 19:45
  • Reading through the proposal, thought this is a bad idea since you end up with one void function and one returning T. It would be possible to have two mutually exclusive pop functions via SFINAE. The exclusion factor would be has_nothrow_move_constructor::value. Not sure how wise that is for the std library, but perhaps for a third party non-std implementation? – Honf Dec 25 '13 at 20:08
  • Erratum: For `stack`, you *can* move the top element out, using `std::move( s.top() )` (as the non-const `top` returns a non-const reference). However, for `priority_queue`, moving could raise problems wrt the internal ordering of the elements (although rather in theory than in practice). It also only provides a const-ref access to top. See [this question](http://stackoverflow.com/a/20149745/420683). – dyp Dec 25 '13 at 20:18
  • 1
    Here's another reason to separate `top` from `pop`: You might want to access the element several times while it *resides* in the stack, but then just want to remove it. Moving it out might require some non-trivial actions (such as partial copying). I'm not sure if that can be elided by the compiler easily when discarding the return value of pop. – dyp Dec 25 '13 at 20:22
  • Also relevant: [a discussion about a possible future proposal for similar member move-out member functions in the isocpp-forums](https://groups.google.com/a/isocpp.org/forum/#!msg/std-proposals/TIst1FOdveo/D54Uo-QuGfUJ) – dyp Dec 25 '13 at 20:28
  • I'm not arguing for the removal of `top` since it does have its uses. Exploring the option of the addition that `pop` should return a move constructed T where possible. That at the very least can provide a class where no unnecessary copies are make, if `top` is not called. As is a copy is required before removal. Edit: After going to the provided link, `top` returns by reference so the element can be manually moved from, than `pop`-ed. I guess this solves the question? – Honf Dec 25 '13 at 20:58
  • Made a helper function that does exactly what I asked in the OP, [posted on pastebin](http://pastebin.com/f6iPNr8C). If you wish to reply with it, so I could accept your answer, can't accept a comment answer :) – Honf Dec 25 '13 at 21:08
  • For `stack`, yes. `template T pop_move(std::stack& p) { T ret( std::move(p.top()) ); p.pop(); return ret; }` (with possibly two moves). I also addressed this in my erratum (sorry for the large amount and size of comments.): I confused `stack` with `priority_queue`. In `stack`, there's a non-const `top` returning a non-const ref, but not for `priority_queue`. – dyp Dec 25 '13 at 21:09
  • You can also answer your own question ;) – dyp Dec 25 '13 at 21:10
  • Eh, I know I can, feels strange :) If its fine with you I'll post the code and accept it. The compiler _should_ be able to elide one move, and if not, still better than calling a copy ctor. `priority_queue` is another can of worms, haven't thought about that one, will read up on it and the n3050 proposal in full, skimmed it before. Thanks for the help. – Honf Dec 25 '13 at 21:19

1 Answers1

1

After a few pointer from DyP, this code should do the trick I'm asking for in OP. Since top returns by reference, it can be safely moved from and then immediately pop-ed. The helper function checks that the preconditions are meet (must be move constructible) and hopefully is a nothrow operation :)

template<class T>
T pull_top(std::stack<T>& x) noexcept(std::is_nothrow_move_constructible<T>::value)
{
    static_assert(std::is_move_constructible<T>::value, "pull_top requires the type to be move constructible");
    T val = std::move(x.top());
    x.pop();
    return val;
}
Honf
  • 215
  • 1
  • 6
  • 1
    If you don't want to overload `pull_top` with a variant that copies (twice), then maybe it's better not to use SFINAE here, but a `static_assert`. – dyp Dec 25 '13 at 21:34
  • True, a static assert would be much better here since no overloads are wanted. I'll modify it. – Honf Dec 25 '13 at 21:35
  • 1
    Wow I'm too tired to do this now ;) `is_move_constructible` checks if `T` can be constructed from an rvalue, not if the move-ctor is chosen for that operation (so it could be copied as well!). Furthermore, if the operation (copy or move invoked by `T val = std::move(x.top());`) throws, you'll *lose* that element. I'd only enable this function (`static_assert`) if `T` is nothrow move constructible. – dyp Dec 25 '13 at 21:48
  • I propose a different approach (nothrow should be noexcept in my comment, fixed it now). If its unknown whether a called function is allowed to throw (based on noexcept specifications), just pass it through a proxy function that will static_assert if it can throw. For an example I cooked up [this monstrosity](http://pastebin.com/Ys85Tyag). It only works for standalone functions, hope you see what I want to convey. – Honf Dec 25 '13 at 23:35
  • I think `strong_guarantee` is a misleading name: the strong exception guarantee is that if an exception is thrown, there is no (observable) effect (other than the exception itself). For example, if copy/move construction throws during a `push_back` on a `list`, the `list` is not altered. See [wikipedia: exception guarantees](http://en.wikipedia.org/wiki/Exception_guarantees). I suggest a name like `require_noexcept`. (Might be a bit of bike-shedding ;) It's an interesting idea if there are scenarios where you can afford losing the element (is this realistic?). – dyp Dec 25 '13 at 23:50
  • Ah, sorry. A tad late and mixed up strong guarantee and no exceptions. Indeed a misleading name. Not sure how to even provide a strong exception guarantee for a move constructor. I can't even think of a _good_ reason why a move constructor would throw, got any? Really in the dark here. As for the require_noexcept function, I imagine it could be useful in template meta programming if you want to assure at _certain_ (not all) call points that noexcept was resolved to `true`. No idea how really useful this is though. Well, time for sleep. – Honf Dec 26 '13 at 00:40
  • A throwing move-ctor: For example, a move constructor (e.g. an implicitly created one, see [this question](http://stackoverflow.com/q/20608662/420683)) can do a partial copy, and this copy might allocate memory. Also, `is_nothrow_move_constructible` uses the ctor selected through overload resolution for an rvalue argument, like `is_move_constructible`. Which means that it could check the exception-specification of the copy-ctor. – dyp Dec 26 '13 at 00:54