12
\$\begingroup\$

I have implemented a basic stack just for fun. I've just started learning about move constructors and assignment and move semantics as a whole, so I would really appreciate some feedback as to whether I've done it right, and if not, some tips as to how I should do it would be most welcome!

I'm also following the example set by the STL, so I'm trying to build the class in an STL-like manner.

The stack class is in a different namespace, which I've removed from this example, so conflicts with std::stack will not appear.

The _stack_node is also in a different details namespace, so it is not exposed to the user.

#include <iostream>
#include <cstdlib>
#include <stdexcept>
#include <initializer_list>
#include <cstddef>
#include <utility>

//FORWARD DECLARATION
template<class T>
class stack;

template<class T>
class _stack_node
{
private:
    using node = _stack_node<T>;

    friend class stack<T>;

private:
    T _key;
    node *_next;

public:
    //COPY CONTRUCTORS
    constexpr _stack_node()
        : _key(0), _next(nullptr)
    {}

    constexpr _stack_node(const T &new_key)
        : _key(new_key), _next(nullptr)
    {}

    constexpr _stack_node(const T &new_key, node *new_node)
        : _key(new_key), _next(new_node)
    {}

    //MOVE CONSTRUCTORs
    constexpr _stack_node(T &&new_key) 
        : _key(std::forward<T>(new_key)), _next(nullptr) 
    {}

    constexpr _stack_node(T &&new_key, node *new_node)
        : _key(std::forward<T>(new_key)), _next(new_node) 
    {}

    //DESTRUCTOR
    ~_stack_node() {}

    //COPY ASSIGNMENT
    node &operator=(const node &rhs) 
    { 
        this->_key = rhs._key; 
        this->_next = rhs._next; 
        return *this; 
    }

    //MOVE ASSIGNMENT
    node &operator=(node &&rhs)
    {
        this->_key = std::move(rhs._key);
        this->_next = std::move(rhs._next);
        return *this;
    }
};

template<class T>
class stack
{
private:
    using node = _stack_node<T>;

public:
    using value_type      = T;
    using size_type       = std::size_t;
    using reference       = T&;
    using const_reference = const T&;

private:
    node *_top;

    std::size_t _size;

private:
    void _throw_stack_empty() const
    { //in case we try to pop an empty stack!!
        try
        {
            if (this->_top == nullptr)
                throw std::out_of_range("You tried to pop an empty stack!"
                                        " Why the hell would you do that?");
        }
        catch (const std::out_of_range &rang)
        {
            std::cerr << "blew::stack: " << rang.what();
            std::abort();
        }
    }

    void _add_node(const T &key)
    {
        node *new_node = new node(key, this->_top);

        this->_top = new_node;

        ++this->_size; //increase size
    }

    void _delete_node()
    {
        this->_throw_stack_empty(); //check and throw if stack is empty

        node *temp_top = this->_top; 
        this->_top = this->_top->_next;
        delete temp_top;

        --this->_size; //decrease size
    }

    void _clear_all_nodes()
    {
        while (this->_top != nullptr)
        {
            node *temp = this->_top;
            this->_top = this->_top->_next;
            delete temp;
        }

        this->_size = 0;
    }

public:
    //COPY CONSTRUCTORS
    constexpr stack()
        : _top(nullptr), _size(0)
    {}

    stack(const std::initializer_list<T> &ilist)
    {
        for (const auto &el : ilist)
            this->_copy_add_node(el);
    }

    stack(const stack &rhs)
    {
        node *temp = rhs._top;
        while (temp != nullptr)
        {
            this->_copy_add_node(temp->_key);
            temp = temp->_next;
        }
    }

    //MOVE CONSTRUCTORS
    stack(std::initializer_list<T> &&ilist) 
    {
        for (const auto &el : ilist)
            this->_move_add_node(std::move(el));
    }

    stack(stack &&rhs) 
    {
        node *temp = std::move(rhs._top);
        while (temp != nullptr)
        {
            this->_move_add_node(std::move(temp->_key));
            temp = temp->_next;
        }
    }

    //DESTRUCTOR
    ~stack() { this->_clear_all_nodes(); }

    //OPERATIONS
    void push(const T &key) { this->_add_node(key); }
    void push(T &&key)      { this->_add_node(std::move(key)); }

    template<class... Args>
    void emplace(Args&&... args) { this->_add_node(std::forward<Args>(args)...); }

    void pop() { this->_delete_node(); }

    //ELEMENT ACCESS
    reference top()             { return this->_top->_key; }
    const_reference top() const { return this->_top->_key; }

    //CAPACITY
    constexpr bool      empty() const { return this->_size == 0 ? true : false; }
    constexpr size_type size()  const { return this->_size; }

    void clear() { this->_delete_all_nodes(); }

    //COPY ASSIGNMENT
    stack operator=(const stack &rhs)
    {
        this->_clear_all_nodes();

        node *temp = rhs._top;
        while (temp != nullptr)
        {
            this->_add_node(temp->_key);
            temp = temp->_next;
        }
        return *this;
    }

    stack operator=(const std::initializer_list<T> &ilist)
    {
        this->_clear_all_nodes();

        for (const auto &el : ilist)
            this->_add_node(el);

        return *this;
    }

    //MOVE ASSIGNMENT
    stack operator=(stack &&rhs)
    {
        this->_clear_all_nodes();

        node *temp = std::move(rhs._top);
        while (temp != nullptr)
        {
            this->_add_node(std::move(temp->_key));
            temp = temp->_next;
        }
        return *this;
    }

    stack operator=(std::initializer_list<T> &&ilist)
    {
        this->_clear_all_nodes();

        for (const auto &el : ilist)
            this->_add_node(std::move(el));

        return *this;
    }
};
\$\endgroup\$
  • 4
    \$\begingroup\$ Don't remove things like namespaces. It makes it harder to review. \$\endgroup\$ – Martin York Nov 23 '15 at 21:36
12
\$\begingroup\$

General Comments

Don't like the naming of your class _stack_node or stack.

The first one has a leading underscore. This is usually a bad sign. Do you know all the rules for leading underscore? More importantly, does everybody that reads your code understand all the rules?

Also it is traditional to use a leading uppercase letter for user defined types.

Also the same applies to all your method and member variable names. The leading underscore is distracting. Also this says to me that you needed to distinguish local variables from member variables which indicates that you are having trouble writing clear readable code (and need an artificial way to help you discriminate).

Its very C like to put the * next to the name. Over the years it has become more traditional in C++ code to put the * next to the type. This is because it is type information and type information is the most important part of C++.

    node *_top;

Note: The same rule applies to & and &&. They belong with the type.

Your use of this is an indication that you are having trouble naming your members well enough to distinguish them from local variables. It is uncommon in C++ code to see this. If you have your compiler warning set correctly then shadowed variables will generate a warning and warnings should be treated as errors (as they are logical errors in your thinking).

if (this->_top == nullptr)

_stack_node

Is there ever going to be a case where you have an empty node?

    //COPY CONTRUCTORS
    constexpr _stack_node()
        : _key(0), _next(nullptr)
    {}

If so then maybe you need a special node to handle this because not all types are going to be construct-able with int(0). I did not see anywhere in your code where you used this constructor so may as well delete it.

I hate the attempt at saving vertical space:

    constexpr _stack_node(const T &new_key)
        : _key(new_key), _next(nullptr)
    {}

I don't think it hinders readability (and it definitely does not help the compiler). So why make the code harder to read. Like the one variable declaration per line try and use one member per line initialization.

This constructor and the last one can be combined into a single constructor using default values (just make the new_node default to nullptr).

    constexpr _stack_node(const T &new_key, node *new_node)
        : _key(new_key), _next(new_node)
    {}

Same here:

    constexpr _stack_node(T &&new_key, node *new_node)
        : _key(std::forward<T>(new_key)), _next(new_node) 
    {}

If your code is not different from the compiler generated code then there is no point in adding cognitive burden to the reader of your class.

    //DESTRUCTOR
    ~_stack_node() {}

May as well delete this destructor it has the same result as the compiler generated version.

Move Semantics (Will go into more details about the move semantics below with the stack class).

stack

Not sure why you throw and catch in the same function!

    void _throw_stack_empty() const
    { //in case we try to pop an empty stack!!
        try
        {
            if (this->_top == nullptr)
                throw std::out_of_range("You tried to pop an empty stack!"
                                        " Why the hell would you do that?");
        }
        catch (const std::out_of_range &rang)
        {
            std::cerr << "blew::stack: " << rang.what();
            std::abort();
        }
    }

Just test and throw.
If the exception is not caught then the application will exit. If the exception is caught by the application then it is non of your business (it definitely should not be the business of a container class to arbitrarily decide that the application should exit (unless you can show corruption).

You should finish the state update of your object before calling delete.

    void _delete_node()
    {
        this->_throw_stack_empty(); //check and throw if stack is empty

        node *temp_top = this->_top; 
        this->_top = this->_top->_next;

        // Though it is rare for delete to throw it can happen.
        // If it does then you will not decrement the size of your
        // class and thus your object is left in an inconsistent state.
        delete temp_top;

        --this->_size; //decrease size
    }

When modifying an object it should be done in three phases.

    1) Create new state into temporary object.s
       Thus if the creating the state is dangerous and causes an exception
       the state of your object will be unchanged.

    2) Modify the state of your object in an exception safe manner.

    3) Clean up.
       Only destroy resources and other objects once the state of your
       object is a completely consistent state. This way if there is an
       exception your object is going to maintain the strong exception
       guarantee.

You suffer from the same problem in _clear_all_nodes() as _delete_node()

    void _clear_all_nodes()
    {
        while (this->_top != nullptr)
        {
            node *temp = this->_top;
            this->_top = this->_top->_next;
            delete temp;
        }

        this->_size = 0;
    }

I would do it like this.

    void _clear_all_nodes()
    {
        node* tmp = _top;

        _top  = nullptr;
        _size = 0;

        while(tmp) {
            node* next = tmp->_next;
            delete tmp;
            tmp = next;
        }
    }

You forgot to initialize the state of your stack before adding elements from list.

    stack(const std::initializer_list<T> &ilist)
    {
        for (const auto &el : ilist)
            this->_copy_add_node(el);
    }

Both _top and _size are POD values. If they are not explicitly initialized then they have indeterminate value. So you are are calling methods on a class that has not been initialized.

Same problem with all the other constructors.

Move semantics

Move constructor should be exception safe. To help the compiler determine this you should mark your move constructor and move assignment operators as noexcept.

When using the standard containers. If your class is contained inside a standard container (yes I can have a vector of stacks). An attempt to resize a standard container will attempt to use the move constructor of the contained class. But the standard containers provide the strong exception guarantee. This means they can not move your object during a re-size unless you guarantee that your class will not throw during the move. The compiler detects this by checking that the move constructor is declared as noexcept. If it can find that guarantee it will fall back to using the copy constructor.

    stack(std::initializer_list<T> &&ilist)       noexcept // Add no except here    
    stack(stack &&rhs)                            noexcept // Add no except here

The whole point of the move constructor is you take the state of the other object. You have to leave the original object in a consistent state but you don't need to go through the process of copying it like this:

    stack(stack &&rhs)
    {
        node *temp = std::move(rhs._top);
        while (temp != nullptr)
        {
            this->_move_add_node(std::move(temp->_key));
            temp = temp->_next;
        }
    }

This should be written as:

    stack(stack &&rhs) 
        : _top(nullptr)               // define a valid state.
        , _size(0)
    {
        std::swap(_top, rhs._top);    // Then swap the state of the two objects.
        std::swap(_size, rhs._size);
    }

The assignment operator is implicated in the rule of three/five. So you should place the assignment (copy/move) close to the constructors (so they can be viewed together). All three/five methods should be close together as they define the resource management characteristics of your object.

Your copy looks like it works. But because you don't follow the rule I described above with _delete_node(). You can accidentally leave your object in an inconsistent state if the constructor goes wrong.

    //COPY ASSIGNMENT
    stack operator=(const stack &rhs)
    {
        this->_clear_all_nodes();

        /*
         * If copying the nodes fail here you have a problem.
         * You can not revert the state back to its original
         * value so a failure here will leave the object in a
         * state that does not fulfill the post condition. So
         * you are only fulfilling the "Basic Guarantee" not the "Strong Guarantee"
         */
        node *temp = rhs._top;
        while (temp != nullptr)
        {
            this->_add_node(temp->_key);
            temp = temp->_next;
        }
        return *this;
    }

1. You clear the state of this object before validating that you can
   successfully make a copy of the rhs. This means if you throw
   you have violated the strong exception.

There is actually a simple technique for implementing the assignment operator in terms of the copy constructor that provides the strong exception guarantee. It is called the copy and swap idiom.

    stack operator=(stack rhs)       // Pass by value to get your copy.
    {
         std::swap(_top, rhs.top);   // Swap the state of your object and the
         std::swap(_size, rhs._size);// parameter.
    }                                // When the parameter is destroyed.
                                     // it tidies up the state of the original object.

Again you violate the strong exception guarantee.

    stack operator=(const std::initializer_list<T> &ilist)
    {
        this->_clear_all_nodes();      // because you destroy the state before
                                       // knowing the assignment will work

        for (const auto &el : ilist)
            this->_add_node(el);

        return *this;
    }

Again simply use the copy and swap idiom.

    stack operator=(const std::initializer_list<T>& list)
    {
        stack tmp(list);
        std::swap(_top, tmp._top);
        std::swap(_size, tmp._size);

        return *this;
    }                    // The original value is now destroyed when
                         // tmp goes out of scope.

Move assignment is like Move construction. The easiest way to implement is to swap the state of the two objects. The src object should be left in a valid but indeterminate state. So you may as well give it the state of the current object.

    //MOVE ASSIGNMENT
    stack operator=(stack &&rhs)  noexcept
    {
        std::swap(_top, rhs._top);
        std::swap(_size, rhs._size);
        return *this;
    }

This move assignment operator breaks the strong exception guarantee. Again you can create a temporary object. Then swap the state of the current object with the temporary. The destructor of the temporary will clean up the original state.

    stack operator=(std::initializer_list<T> &&ilist)
    {
        this->_clear_all_nodes();            // because you destroy the state before
                                             // knowing the move will work. 
                                             // also you are copying the nodes

        for (const auto &el : ilist)
            this->_add_node(std::move(el));

        return *this;
    }

    stack operator=(std::initializer_list<T>&& list)   noexcept
    {
        stack tmp(std::forward<std::initializer_list<T>>(list));

        std::swap(_top, tmp._top);
        std::swap(_size, tmp._size);
        return *this;
    }

Don't remember seeing this version of _add_node or of a _stack_node constructor that would work with this.

    template<class... Args>
    void emplace(Args&&... args) { this->_add_node(std::forward<Args>(args)...); }
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – 200_success Nov 24 '15 at 17:38
7
\$\begingroup\$

Moving Issues

There are several issues related to rvalues in your code. I'll start with the move constructor. The idea is that we're taking over the other guy's stack completely, and we want this to be as cheap as possible. Rather than move each node, we just take over the root:

stack(stack&& rhs) 
: _top(rhs._top)
, _size(rhs._size)
{
    rhs._top = nullptr;
    rhs._size = 0;
}

That's it. Our _top now points to rhs's _top, and we cleared that one out so that it thinks it's empty.

The move assignment has two big problems. Self-assignment clears the stack, and it returns a copy instead of a reference. You could just swap the pointers:

stack& operator=(stack&& rhs) {
    std::swap(_top, rhs._top);
    std::swap(_size, rhs._size);
    return *this;
}

Your copy assignment has the same problem with clearing - prefer to use the copy-and-swap idiom.

Lastly, you went through all the effort of trying to make it as efficient as possible to add new nodes:

//OPERATIONS
void push(const T &key) { this->_add_node(key); }
void push(T &&key)      { this->_add_node(std::move(key)); }

template<class... Args>
void emplace(Args&&... args) { this->_add_node(std::forward<Args>(args)...); }

And yet:

void _add_node(const T &key)
{
    node *new_node = new node(key, this->_top);

So what happens if, if we did:

my_stack.push(std::move(var));

You move it into _add_node(), but then you copy it into the node constructor anyway! Make sure you delay construction as far as possible. _add_node should just take whatever:

template <typename... Args>
void _add_node(Args&&... args);

and forward them into node::node, and only there do you construct a T. Never take a const T&, you're going to shoot yourself in the foot.

Minor Issues

Avoid writing expressions like expr ? true : false like you have in empty(), just use expr:

constexpr bool      empty() const { return this->_size == 0; }

You don't need an assignment operator to initializer_list<T>. Just copy assignment and move assignment suffice. Similarly, you have two constructors taking a const initializer_list<T>& and an initializer_list<T>&&. The latter isn't really useful since you can't move out of an initializer_list anyway (the elements you get back are of type const T). Just have the one constructor:

stack(std::initializer_list<T> elems) {
    for (const auto& el : elems) {
        _copy_add_node(el);
    }
}

_stack_node should probably be a private nested class to stack. It doesn't really make sense to expose it.

\$\endgroup\$
  • \$\begingroup\$ I had the whole moving concept completely wrong. It's not just fancy fast copying, but literally "moving" the contents of one thing to the other. Makes so much more sense now. Thanks a lot for your efforts!! \$\endgroup\$ – DeiDei Nov 23 '15 at 22:52
  • \$\begingroup\$ Explicit checking for self-assignment is an anti-pattern, as it pessimizes the normal case. Also, just swapping the resources is normally a gain too. \$\endgroup\$ – Deduplicator Nov 24 '15 at 0:13
  • \$\begingroup\$ @Deduplicator That's a good point, I'll fix it. \$\endgroup\$ – Barry Nov 24 '15 at 17:42
5
\$\begingroup\$
  1. If you make node a private member, it need not be templated. And that's appropriate, seeing as it's an implementation-detail.
    As an aside, in a class, whether templated or not, the class-name is injected for ease-of-use, so the using-declaration is not useful.

  2. Slash all of node's members but next and key to make it an aggregate and use aggregate-initialization. Much easier, and it reduced 58 lines down to one.
    If you don't do that, you need to add a templated constructor to allow inplace-construction of the key!

  3. Next, I suggest you start with the public interface, and put all the internals at the end.
    That way, someone reading your source-code will get an overview of what you are traing to do much faster.

  4. If you give your members an initializer, all constructors not explicitly overriding them will pick it up.
    This way, you can for example explicitly default the default-constructor.
    Members without either are default-initialized, which is the same as not initialized for builtin types!

  5. std::initializer_list<T> is an extremely lightweight trivial type, implementing a non-owning range.
    Just copy it wherever you need to pass it, that's probably even faster, and it certainly lets you dispense with useless duplication.

  6. If you add a constructor for initializing from an iterator-range, you can implement the initializer_list-constructor as a simple delegation.
    Add iterators, and the same holds for the copy-constructor.

  7. Currently, your copy-constructor reverses!

  8. Your move-constructor is buggy (self-assignment) and needlessly complicated.
    Just swap the members. I would provide a member-function swap to do it, which will also be picked up by std::swap.

  9. If you provide a public function to do something, and also a private one, there should be a good reason for that duplication. You don't have one.

  10. Mark everything you can noexcept for better performance and to make that part of the contract others can depend on.

  11. The point of emplace is to avoid copies. So why are you first constructing the final object, and only then copying (not even moving!!) it to its destination?
    Also, this is the base-operation push should be implemented in terms of.

  12. _throw_stack_empty() is a curious one. If you insist on extracting it, it should at least do what it advertizes, instead of aborting.
    For performance-reasons, the check should be in the caller and it should throw unconditionally (mark it [[noreturn]]).

    Still, calling pop on an empty stack is a logic-error which is easily avoided, assert-ing that in a debug-build and ignoring it in release allows marking that noexcept too.

  13. You should go over your includes and reduce them to the bare minimum. That's especially important in headers.

  14. As swapping, move-constructing and destroying (if empty) two of your objects is so very cheap, you should use the copy-and-swap-idiom for assignment.
    That lets you dispense with lots of duplicate code.

  15. There's exactly one place where you need to explicitly use this (operator=). It's very uncommon to use it where not needed.

Applying all that yields:

#include <initializer_list>
#include <iterator>
#include <stdexcept> // or <cassert>
#include <type_traits>
#include <utility>

template<class T>
struct stack
{
    using value_type = T;
    using size_type = std::size_t;
    using reference = T&;
    using const_reference = const T&;

    constexpr stack() noexcept {}

    stack(std::initializer_list<T> list) : stack(begin(list), end(list)) {}
    template<class InputIt,
        typename std::enable_if<std::is_base_of<std::input_iterator_tag,
            typename std::iterator_traits<InputIt>::iterator_category>::value
        >::type* = 0>
    stack(InputIt first, InputIt last) {
        for(; first != last; ++first)
            push(*first);
    }
    stack(const stack& other) : _size(other._size) {
        auto p = &_top;
        for(auto x = other._top; x; x = x->next, p = &p[0]->next)
            *p = new node{nullptr, x->key};
    }
    stack(stack&& other) noexcept { swap(other); }
    ~stack() { clear(); }

    void swap(stack& other) noexcept {
        std::swap(_top, other._top);
        std::swap(_size, other._size);
    }

    //OPERATIONS
    void push(const T& key) { emplace(key); }
    void push(T&& key) { emplace(std::move(key)); }

    template<class... ARGS>
    void emplace(ARGS&&... args) {
        _top = new node{_top, {std::forward<ARGS>(args)...}};
        ++_size;
    }

    void pop() {
        if(!_top) _throw_stack_empty(); // or better assert(_top);
        auto old = _top;
        _top = old->next;
        --_size;
        delete old;
    }

    //ELEMENT ACCESS
    reference top() noexcept { return _top->_key; }
    const_reference top() const noexcept { return _top->_key; }

    //CAPACITY
    constexpr bool empty() const noexcept { return !_size; }
    constexpr size_type size() const noexcept { return _size; }

    void clear() noexcept {
        for(T* next; _top; _top = next) {
            next = _top->next;
            delete _top;
        }
        _size = 0;
    }

    stack& operator=(stack other) noexcept { swap(other); return *this; }
private:
    struct node { node* next; T key; };
    node *_top = nullptr;
    std::size_t _size = 0;

    [[noreturn]] static void _throw_stack_empty() {
        throw std::out_of_range("You tried to pop an empty stack!"
                                " Why the hell would you do that?");
    }
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.