5
\$\begingroup\$

I'm working on a stack implementation using a linked list, but I have a strong feeling that I overcomplicated my solution. I would appreciate it if you review this code and give me any suggestions on code and style.

#pragma once
#include <functional>
#include <iostream>
#include <type_traits>
#include <stdexcept>
template <typename T>
class StackList
{
private:
    class Node
    {
        T data;
        Node * next;
        Node(Node * next, const T & data) :next(next), data(data) {};
        friend class StackList<T>;
    };
    int size_ = 0;
    Node * head_ = nullptr;
    Node * tail_ = nullptr;
    void AddToTail(T& data);
public:
    StackList() = default;
    StackList(StackList & other);
    StackList(StackList && other);
    StackList & operator=(StackList & other);
    StackList & operator=(StackList && other);
    ~StackList() { EmptyList(); }

    void EmptyList();
    void push(const T & data);
    T pop();
    const T& operator[](int count) const; 
    T& operator[](int count) { return const_cast<T &>(static_cast<const StackList &>(*this).operator[](count)); };
    int size() { return size_; }
    void Traverse(std::function<void(T&)> lamda) const;
    void Traverse(std::function<void(T&)> lamda){ (static_cast<const StackList &>(*this).Traverse(lamda)); }

    template <typename T>
    friend std::ostream & operator<<(std::ostream & os, StackList<T> & stack);
};

template <typename T>
void StackList<T>::AddToTail(T& data)
{
    if (head_ == nullptr)
        head_ = tail_ = new Node(nullptr, data);
    else
    {
        tail_->next = new Node(nullptr, data);
        tail_ = tail_->next;
    }
}

template <typename T>
StackList<T>::StackList(StackList & other)
{
    std::function<void(T&)> lamda = [&](T& data) {this->AddToTail(data); this->size_++; };
    other.Traverse(lamda);
}

template <typename T>
StackList<T>::StackList(StackList && other) : head_(other.head_), tail_(other.tail_), size_(other.size_)
{
    other.head_ = 0;
    other.tail_ = 0;
    other.size_ = 0;
}

template <typename T>
StackList<T> & StackList<T>::operator=(StackList<T> & other)
{
    if (this != &other)
    {
        if (other.size_ == 0)
            EmptyList();
        else
        {
            if (size_ >= other.size_)
            {
                Node * current = head_;
                std::function<void(T&)> lamda = [&](T& data) {current->data = data; tail_ = current; current = current->next; };
                other.Traverse(lamda);
                while (current != nullptr)
                {
                    Node * save = current->next;
                    delete current;
                    current = save;
                }
            }
            else
            {
                Node * current = other.head_;
                std::function<void(T&)> lamda = [&](T& data) {data = current->data; current = current->next; };
                Traverse(lamda);
                while (current != nullptr)
                {
                    AddToTail(current->data);
                    current = current->next;
                }
            }
            tail_->next = nullptr;
            size_ = other.size_;
        }
    }
    return *this;
}

template <typename T>
StackList<T> & StackList<T>::operator=(StackList<T> && other)
{
    if (this != &other)
    {
        head_ = other.head_;
        tail_ = other.tail_;
        size_ = other.size_;
        other.head_ = 0;
        other.tail_ = 0;
        other.size_ = 0;
    }
    return *this;
}

template <typename T>
const T& StackList<T>::operator[](int count) const
{
    if (count > size_ - 1 && count < 0)
        throw std::invalid_argument("Out of range index!");
    Node * search = head_;
    for (int i = 0; i < count; i++)
        search = search->next;
    return search->data;
}

template <typename T>
void StackList<T>::EmptyList()
{
    while (head_ != nullptr)
        pop();
}

template <typename T>
void StackList<T>::push(const T & data)
{
    head_ = new Node(head_, data);
    if (tail_ == nullptr)
        tail_ = head_;
    size_++;
}

template <typename T>
T StackList<T>::pop()
{
    if (size_ > 0)
    {
        T retval = head_->data;
        Node * temp = head_->next;
        delete head_;
        head_ = temp;
        size_--;
        if (size_ == 0)
            head_ = tail_ = nullptr;
        return retval;
    }
    else
    {
        throw std::invalid_argument("Pop of empty list");
    }

}
template <typename T>
void StackList<T>::Traverse(std::function<void(T&)> lamda) const
{
    Node * cur = head_;
    while (cur != nullptr)
    {
        lamda(cur->data);
        cur = cur->next;
    }
}

template <typename T>
std::ostream & operator<<(std::ostream & os, StackList<T> & stack)
{
    std::function<void(T&)> lamda = [&](T& data) { os << data << std::endl; };
    std::ios_base::fmtflags f(os.flags());
    os << "Stack of " << typeid(T).name() << ", size = " << stack.size() << std::endl;
    stack.Traverse(lamda);
    os.flags(f);
    return os;
}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Stack only needs to implement push, pop, top, empty. Additionally you can have copy, assignment, swap, clear and serialization routines to make your class user-friendly.

Comments about this implementation:

  • Recommend separate files (H & CPP) for class definition and implementation. May even want to go to lengths to have a Stack interface (in C++ this can be done via class with only public pure virtual function and virtual no-op destructor). This StackList would be an implementation/child of the Stack.

  • You don't need both head_ and tail_, only one is sufficient for FIFO/Stack API implementation

  • Copy Constructor function signature is incorrect, it needs to be StackList(const StackList & other), it is incorrect to be able to modify the input during copy via lvalue-ref.

  • Recommend following Copy-Swap idiom to implement operator=. You may even be able to get away with not needing to create 2 overloads one for lvalue-reference and one for rvalue-reference, use an object copy instead.

  • Do not create operator[] as it is not needed for Stack. Its run-time complexity is linear, so no need to add a slow unnecessary public method.

  • Traverse doesn't need to be public on the StackList class

  • Recommend having const reference of StackList in operator<<(std::ostream & os, const StackList<T> & stack) as it doesn't need to modify the stack.

  • Follow std data structure API convention:

    • Naming: Recommend changing the name of EmptyList to clear
    • Adding an empty member function. This can be achieved via 0 == size(), but prefer to have an explicit empty to ease Stack usage
\$\endgroup\$
1
  • \$\begingroup\$ What would go into the implementation file, given that the entire class is a template type? \$\endgroup\$ Mar 5, 2019 at 9:00
3
\$\begingroup\$

I'd recommend putting a blank line after your #pragma once, and again after your #includes, just for readability.

Nit on the naming: When I (a speaker of English, which is an adjective-noun language) see StackList, I think "a list of stacks" or possibly "a list implemented in terms of a stack," which in fact is the exact opposite of what you have here. What you have here is a ListStack — a stack implemented in terms of a linked list.


StackList() = default;
StackList(StackList & other);
StackList(StackList && other);
StackList & operator=(StackList & other);
StackList & operator=(StackList && other);
~StackList() { EmptyList(); }

First of all, personally I'd recommend defining all these functions in-line right here, rather than making me scroll down to find their definitions later in the same file.

Another naming nit: if a StackList is a List implemented as a Stack, then surely an EmptyList should be a List that's always Empty! As @Chintan pointed out, what you actually have here is traditionally named this->clear(). "Empty" is a particularly bad name because it can be read as a verb or as an adjective, and actually C++ uses the adjective reading: vec.empty() asks "Is this vector empty?", not "Please make this vector empty." (This was a large part of the motivation for C++17's [[nodiscard]] attribute.)

The biggest problem here, though, is that you got the copy constructor's signature wrong!

StackList(StackList & other);
StackList(StackList && other);
StackList & operator=(StackList & other);
StackList & operator=(StackList && other);

should read

StackList(const StackList& other);
StackList(StackList&& other) noexcept;
StackList& operator=(const StackList& other);
StackList& operator=(StackList&& other) noexcept;

The const is very important! Without it, you wouldn't be able to make a copy of a list that you had promised never to modify.

void foo(const StackList& lst) {
    auto lst2 = lst;  // this line fails to compile
}

const T& operator[](int count) const; 
T& operator[](int count) { return const_cast<T &>(static_cast<const StackList &>(*this).operator[](count)); };

Note that it's "un-C++-ish" to provide such a concise spelling for an O(n) operation. Also, I think it would be more natural to use const_cast rather than static_cast here, since all you're doing (and all you're trying to do) is add a const qualifier.


template <typename T>
friend std::ostream & operator<<(std::ostream & os, StackList<T> & stack);

You should definitely move this operator in-line, so that you don't have to make it a template. Additionally, what you have here is actually invalid because you're trying to redefine the name T, which already has a meaning — it's the template type parameter to StackList. So what I would write is:

friend std::ostream& operator<<(std::ostream& os, const StackList& stack) {
    std::ostream os2(os.rdbuf());
    os2 << "Stack of " << typeid(T).name() << ", size = " << stack.size() << std::endl;
    stack.Traverse([&](T& data) {
        os2 << data << std::endl;
    });
    return os;
}

Note that I've made a few more changes; for example, rather than imperatively fiddle with the flags of the given ostream, I'd just create my own ostream. That way, the user couldn't mess up my output:

StackList<int> lst;
lst.push(100);
std::cout << std::hex << lst << std::endl;

With your code, this prints 64; with my code, this prints 100.

Also, "don't use endl" applies here.


Your code repeatedly uses the identifier lamda [sic] to refer to a variable of type std::function. That's not correct. I actually think you should get rid of all the std::functions in your code and just use lambdas, actually. (That's "lambdas" with a "b".) So for example, you have:

void Traverse(std::function<void(T&)> lamda) const;
void Traverse(std::function<void(T&)> lamda){ (static_cast<const StackList &>(*this).Traverse(lamda)); }

template <typename T>
void StackList<T>::Traverse(std::function<void(T&)> lamda) const
{
    Node * cur = head_;
    while (cur != nullptr)
    {
        lamda(cur->data);
        cur = cur->next;
    }
}

Actually there's a problem even before we get to the lambdas! You seem to have added the non-const overload of Traverse on autopilot. It doesn't do what you want at all. Remove it, and re-add it when you have a need for it.

Speaking of untested code, you should be compiling with -W -Wall and probably -Wextra, and fixing all the bugs that the compiler tells you about. That would catch things like

warning: field 'next' will be initialized after field 'data' [-Wreorder]
    Node(Node * next, const T & data) :next(next), data(data) {};
                                       ^

Every bug caught by the compiler is a bug you don't have to catch! And every bug caught by a unit test is a bug you don't have to catch, too. Write some tests for your code (such as Traverse). You'll find plenty of bugs.

Okay, so, here's how I would write Traverse:

template<class F>
void Traverse(const F& visit) {
    for (Node *cur = head_; cur != nullptr; cur = cur->next) {
        visit(cur->data);
    }
}

This is a better API than the std::function-based API you wrote, because with this API, I'm not forcing my caller to wrap their lambda into a std::function. This saves a lot of compile time, and saves a dynamic allocation at runtime, but perhaps most importantly, it allows the caller to pass in non-copyable lambdas such as

StackList<int> lst;
lst.Traverse([ptr = std::make_unique<int>(42)](int& data) {
    data += *ptr;
});

Consider why AddToTail doesn't ++size_, and whether perhaps it should.


Your copy-assignment operator seems much too complicated. (And is missing a pair of braces around the body of the first if.) I think I'd expect to see something about this long, lines-of-code-wise:

StackList& operator=(const StackList& rhs) {
    if (this != &rhs) {
        Node **src = &rhs.head_;
        Node **dst = &head_;
        while (*src != nullptr && *dst != nullptr) {
            (*dst)->data = (*src)->data;
            src = &(*src)->next;
            dst = &(*dst)->next;
        }
        while (*src != nullptr) {
            *dst = new Node(nullptr, (*src)->data);
            dst = &(*dst)->next;
            src = &(*src)->next;
        }
        while (*dst != nullptr) {
            Node *temp = (*dst)->next;
            delete *dst;
            *dst = temp;
        }
        // updating tail_ is left as an exercise for the reader
    }
    return *this;
}

You might compare your implementation to std::list, and think about whether it's possible to take that while (*dst != nullptr) loop and factor it out into a member function named erase.

\$\endgroup\$

Your Answer

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

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