Stack template using linked list

Question

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;
}

Answer 1

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

• Toby Speight: What would go into the implementation file, given that the entire class is a template type?

Answer 2

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.