3
\$\begingroup\$

I have decided to rewrite what I did here, following the suggestions to use smart pointers. I will rewrite the other data structures as well using smart pointers where appropriate.

I just want to see how my code stands now, I am sure there are still areas I need to improve or fix. I again want to thank this community in their effort in evaluating my code, I really appreciate it and I believe it is slowly but surely taking my coding skills to the next level.

Here is my header file:

#ifndef Stack_h
#define Stack_h

#include <iterator>
#include <memory>

template <class T>
class Stack {
    struct Node {
        T data;
        std::unique_ptr<Node> next = nullptr;

        template<typename... Args, typename = std::enable_if_t<std::is_constructible<T, Args&&...>::value>>
        explicit Node(std::unique_ptr<Node>&& next, Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value)
        : data{ std::forward<Args>(args)... }, next{ std::move(next) } {}

        // disable if noncopyable<T> for cleaner error msgs
        explicit Node(const T& x, std::unique_ptr<Node>&& p = nullptr)
        : data(x)
        , next(std::move(p)) {}

        // disable if nonmovable<T> for cleaner error msgs
        explicit Node(T&& x, std::unique_ptr<Node>&& p = nullptr)
        : data(std::move(x))
        , next(std::move(p)) {}
    };
    std::unique_ptr<Node> front = nullptr;

    void do_unchecked_pop() {
        front = std::move(front->next);
    }

public:
    // Constructors
    Stack() = default;                                           // empty constructor
    Stack(Stack const &source);                                  // copy constructor

    // Rule of 5
    Stack(Stack &&move) noexcept;                                // move constructor
    Stack& operator=(Stack &&move) noexcept;                     // move assignment operator
    ~Stack();

    // Overload operators
    Stack& operator=(Stack const &rhs);

    // Create an iterator class
    class iterator;
    iterator begin();
    iterator end();
    iterator before_begin();

    // Create const iterator class
    class const_iterator;
    const_iterator cbegin() const;
    const_iterator cend() const;
    const_iterator begin() const;
    const_iterator end() const;
    const_iterator before_begin() const;
    const_iterator cbefore_begin() const;

    // Member functions
    template<typename... Args>
    iterator emplace(const_iterator pos, Args&&... args);

    void swap(Stack& other) noexcept;
    bool empty() const {return front == nullptr;}
    int size() const;
    void push(const T& theData);
    void push(T&& theData);
    T& top();
    const T& top() const;
    void pop();

};

template <class T>
class Stack<T>::iterator {
    Node* node = nullptr;
    bool before_begin = false;

public:
    friend class Stack<T>;

    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T * ;
    using reference = T & ;

    operator const_iterator() const noexcept { return const_iterator{ node }; }
    iterator(Node* node = nullptr, bool before = false) : node{ node }, before_begin{ before } {}

    bool operator!=(iterator other) const noexcept;
    bool operator==(iterator other) const noexcept;

    T& operator*() const { return node->data; }
    T& operator->() const { return &node->data; }

    iterator& operator++();
    iterator operator++(int);
};

template <class T>
class Stack<T>::const_iterator {
    Node* node = nullptr;
    bool before_begin = false;

public:
    friend class Stack<T>;

    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T * ;
    using reference = const T & ;

    const_iterator() = default;
    const_iterator(Node* node, bool before = false) : node{ node }, before_begin{ before } {}


    bool operator!=(const_iterator other) const noexcept;
    bool operator==(const_iterator other) const noexcept;

    const T& operator*() const { return node->data; }
    const T& operator->() const { return &node->data; }

    const_iterator& operator++();
    const_iterator operator++(int);
};


template <class T>
Stack<T>::Stack(Stack<T> const& source) {
    try {
        for(auto loop = source.front.get(); loop != nullptr; loop = loop->next.get())
            push(loop->data);
    }
    catch (...) {
        while(front != nullptr)
            do_unchecked_pop();
        throw;
    }
}

template <class T>
Stack<T>::Stack(Stack&& move) noexcept {
    move.swap(*this);
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack&& move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
Stack<T>::~Stack() {
    while(front != nullptr) {
        do_unchecked_pop();
    }
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack const& rhs) {
    Stack copy(rhs);
    swap(copy);
    return *this;
}

template <class T>
void Stack<T>::swap(Stack& other) noexcept {
    using std::swap;
    swap(front,other.front);
}

template <class T>
template <typename... Args>
typename Stack<T>::iterator Stack<T>::emplace(const_iterator pos, Args&&... args) {
    if (pos.before_begin) {
        emplace_front(std::forward<Args>(args)...);
        return begin();
    }

    if (pos.node->next) {
        pos.node->next = std::make_unique<Node>(std::move(pos.node->next), std::forward<Args>(args)...);  // Creating a new node that has the old next pointer with the new value and assign it to the next pointer of the current node
        return { pos.node->next.get() };
    }
}

// Free function
template <typename T>
void swap(Stack<T>& a, Stack<T>& b) noexcept {
    a.swap(b);
}

template <class T>
int Stack<T>::size() const {
    int size = 0;
    for (auto current = front.get(); current != nullptr; current = current->next.get())
        size++;
    return size;
}

template <class T>
void Stack<T>::push(const T& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

    if(front) {
        newNode->next = std::move(front);
    }
    front = std::move(newNode);
}

template <class T>
void Stack<T>::push(T&& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(std::move(theData));

    if(front) {
        newNode->next = std::move(front);
    }
    front = std::move(newNode);
}

template <class T>
T& Stack<T>::top() {
    if(!empty()) {
        return front->data;
    }
    else {
        throw std::out_of_range("The stack is empty!");
    }
}

template <class T>
const T& Stack<T>::top() const {
    if(!empty()) {
        return front->data;
    }
    else {
        throw std::out_of_range("The stack is empty!");
    }
}

template <class T>
void Stack<T>::pop() {
    if(empty()) {
        throw std::out_of_range("The stack is empty!");
    }
    do_unchecked_pop();
}

// Iterator Implementaion////////////////////////////////////////////////
template <class T>
typename Stack<T>::iterator& Stack<T>::iterator::operator++() {
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
typename Stack<T>::iterator Stack<T>::iterator::operator++(int) {
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
bool Stack<T>::iterator::operator==(iterator other) const noexcept {
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
bool Stack<T>::iterator::operator!=(iterator other) const noexcept {
    return !(*this == other);
}



template<class T>
typename Stack<T>::iterator Stack<T>::begin() {
    return front.get();
}

template<class T>
typename Stack<T>::iterator Stack<T>::end() {
    return {};
}

template <class T>
typename Stack<T>::iterator Stack<T>::before_begin() {
    return { front.get(), true };
}

// Const Iterator Implementaion////////////////////////////////////////////////
template <class T>
typename Stack<T>::const_iterator& Stack<T>::const_iterator::operator++() {
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
typename Stack<T>::const_iterator Stack<T>::const_iterator::operator++(int) {
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
bool Stack<T>::const_iterator::operator==(const_iterator other) const noexcept {
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
bool Stack<T>::const_iterator::operator!=(const_iterator other) const noexcept {
    return !(*this == other);
}


template <class T>
typename Stack<T>::const_iterator Stack<T>::begin() const {
    return front.get();
}

template <class T>
typename Stack<T>::const_iterator Stack<T>::end() const {
    return {};
}

template <class T>
typename Stack<T>::const_iterator Stack<T>::cbegin() const {
    return begin();
}

template <class T>
typename Stack<T>::const_iterator Stack<T>::cend() const {
    return end();
}

template <class T>
typename Stack<T>::const_iterator Stack<T>::before_begin() const {
    return { front.get(), true };
}

template <class T>
typename Stack<T>::const_iterator Stack<T>::cbefore_begin() const {
    return before_begin();
}


#endif /* Stack_h */

Here is the test cpp file I used:

#define CATCH_CONFIG_MAIN
#include "catch.h"
#include "Stack.h"

TEST_CASE("An empty stack", "[Stack]") {
    Stack<int> stack;

    REQUIRE(stack.empty());
    REQUIRE(stack.size() == 0u);

    SECTION("inserting an element makes the map not empty") {
        stack.push(2);

        REQUIRE(!stack.empty());
    }

    SECTION("inserting an element increases the size") {
        stack.push(4);

        REQUIRE(stack.size() == 1u);
    }

    SECTION("pop on empty stack does nothing") {
        stack.push(6);
        stack.pop();

        REQUIRE(stack.size() == 0);
        REQUIRE(stack.empty());
    }
}

TEST_CASE("Create a stack list with multiple elements", "[Stack]") {
    Stack<int> stack;
    stack.push(2);
    stack.push(4);
    stack.push(6);
    stack.push(8);
    stack.push(10);

    static auto init_values = std::vector<int>{2, 4, 6, 8, 10};

    REQUIRE(stack.size() == init_values.size());
    REQUIRE(!stack.empty());
    REQUIRE(std::distance(stack.begin(), stack.end()) == init_values.size());
    //REQUIRE(std::equal(stack.begin(), stack.end(), init_values.begin()));

    SECTION("Can find elements with std::find") {
        auto found = std::find(std::begin(stack), std::end(stack), 4);

        REQUIRE(found != std::end(stack));
        REQUIRE(*found == 4);
    }

    SECTION("pop removes last element") {
        stack.pop();

        REQUIRE(stack.top() == 8);
        REQUIRE(stack.size() == 4);
    }

    SECTION("copy construction") {
        auto second_list = stack;

        REQUIRE(stack.size() == init_values.size());
        //REQUIRE(std::equal(stack.begin(), stack.end(), init_values.begin()));
        REQUIRE(second_list.size() == stack.size());
        //REQUIRE(std::equal(second_list.begin(), second_list.end(), stack.begin()));
    }

    SECTION("copy assignment") {
        auto second_list = Stack<int>{};

        second_list = stack;

        REQUIRE(stack.size() == init_values.size());
        //REQUIRE(std::equal(stack.begin(), stack.end(), init_values.begin()));
        REQUIRE(second_list.size() == stack.size());
        //REQUIRE(std::equal(second_list.begin(), second_list.end(), stack.begin()));
    }

    SECTION("move construction leaves original list in empty state") {
        auto second_list = Stack<int>{ std::move(stack) };

        REQUIRE(stack.empty());
        REQUIRE(second_list.size() == init_values.size());
       // REQUIRE(std::equal(second_list.begin(), second_list.end(), init_values.begin()));
    }
}

For tests, I used the Catch2 testing framework. I guess the only problem I had was the std::equal() but other than that I am satisfied with the tests it passed.

\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$
int size() const;

Why not a std::size_t like the standard containers? Using a signed type here gives warnings when compiling the tests, and is likely to be a nuisance for other users.

Making it unsigned gives a different signed/unsigned comparison, here:

REQUIRE(std::distance(stack.begin(), stack.end()) == init_values.size());

But we can make an equivalent test that requires no cast:

REQUIRE(std::next(stack.begin(), init_values.size()) == stack.end());

There's complication (and an iterator member!) for before_begin, but I don't see that used in any of the implementation, nor tested as part of the public interface. We can get rid of that, and just work with the usual range of valid and one-past-the end.


We can (from C++20 onwards) default the iterators' == and != operators.


The use of do_unchecked_pop to ensure that destructor and failed-construction don't throw shows that you've thought about these cases properly. That said, I thought that part of the point of using a smart-pointer to Node was that it should clean up properly without needing to write any code here?


Is there a good reason we can't emplace at the end of the list? We test pos.node->next, but I think we should instead be checking that pos.node is valid (and its next can perfectly well be a null pointer). This suggests we're missing some tests.


This implementation differs from std::stack in a few ways. Notably, its size() has linear complexity, which will likely catch out users who would normally expect it to execute in constant time.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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