# Superior improved stack implementation using a linked list

This is a followup to

Please review my hopefully improved stack implementation

• As suggested by some answers to my previous code, some of the functions can be overloaded to provide versions of return by value, return by reference and const or pass by value, pass by reference and const, but the function definitions are almost the same so I did not add it here.
• Regarding pointers, I know std::unique_ptr will be better and I already saw an implementation through an answer to my previous code, but I like to play with normal pointers right now.
template<class T>
class Stack {
using stacksize = std::size_t;
public:
Stack() : first{nullptr}, n{0} {}
stacksize size() const { return n; }
bool empty() const { return n == 0; }
Stack(const Stack&);
Stack(Stack&&);
Stack& operator=(Stack);
Stack& operator=(Stack&&);
T& operator[](const stacksize& i) {
Node* traverse = first;
stacksize x = 0;
while (x < i) {
traverse = traverse->next;
++x;
}
return traverse->item;
}
void push(const T&);
void pop();
T& peek() const;
~Stack() {
while (!empty()) {
pop();
}
}
private:
struct Node {
T item;
Node* next;
};
Node* first;
stacksize n;
};

template<class T>
Stack<T>::Stack(const Stack& s) :first{nullptr}, n{0}{
for (auto t = s.first; t != nullptr; t = t->next) {
push(t->item);
}
}

template<class T>
Stack<T>& Stack<T>::operator=(Stack s) {
std::swap(first,s.first);
std::swap(n,s.n);
return *this;
}

template<class T>
Stack<T>::Stack(Stack&& s) :first{s.first}, n{s.n} {
s.first = nullptr;
s.n = 0;
}

template<class T>
Stack<T>& Stack<T>::operator=(Stack&& s) {
std::swap(s.n,n);
std::swap(s.first,first);
return *this;
}

template<class T>
void Stack<T>::push(const T& t) {
first = new Node{t,first};
++n;
}

template<class T>
void Stack<T>::pop() {
Node* oldfirst = first;
first = first->next;
delete oldfirst;
--n;
}

template<class T>
T& Stack<T>::peek() const {
return first->item;
}


## Code Review

I find your placement of & inconsistent with *

    Node(const T & t, Node* link) :item{t}, next{link} { }


And r-value reference declaration stranger still

    Stack(Stack & & );  // I am surprised that compiled. As each & is a separate token
// While && is a single token.


This is all part of the type information. Put it with the type.

    Node(const T& t, Node* link) :item{t}, next{link} { }
Stack(Stack&& rhs);


You provide a push by copy.

void push(const T & );


and you are familiar with move semantics. Why not provide a push by move?

void push(T&& val);


## Very Minor personal preference.

Personally I prefer const on the right of the type. The rule is that const binds left unless it is on the very left hand side then it binds right. There is one obsecure corner case were this makes a difference. But it is obscure so don't worry.

    Node(T const& t, Node* link) :item{t}, next{link} { }


I just find it easier when reading types (as you read them right to left).

    char const * const  x;
// x is "const pointer" to a "const char"

char const *   x;
// x is "pointer" to a "const char"

char * const  x;
// x is "const pointer" to a "char"

• When I first pasted the code, it looks like some of the "and" disappeared or my screenreader did not read them, so I put a space before and after it to make it visible. It's back to original now. – morbidCode Nov 21 '14 at 17:36
• I was curious about the & & thing too! I found an article about forwarding which explains that Stack & & would collapse into Stack&. – flakes Nov 21 '14 at 20:24
• @Calpratt I didn't write the & & in code, I did it here because my screenreader won't read the & if I did not put a space in between or before it. I thought it disappeared. – morbidCode Nov 22 '14 at 1:58

Seeing as you need to make a new stacksize object in the operator[] function, I wouldn't pass the parameter i as a const reference. This way you can use the copied parameter as part of the logic and shorten the code while still not effecting the caller. I would also add error checking here to see if the index is out of range and either throw a std::out_of_range exception or return a dummy value

#include <stdexcept>

T& operator[](stacksize i) const{
if(i < 0 || i >= n) throw std::out_of_range("You dun goofed the range");
Node* traverse = first;
while (i--) traverse = traverse->next;
return traverse->item;
}


You should also be doing this type of error checking in your other functions

• If I want to give a dummy value if the index is out of range, what dummy value can I use? – morbidCode Nov 21 '14 at 17:24
• @morbidCode You could store it in the classes private values and add it as a parameter in the constructor, or maybe a static private the user has to define before using stacks of that type. int Stack<int>::default_ = 0; typedef Stack<int> StackInt – flakes Nov 21 '14 at 20:15

These are some thoughts/questions from a C++ noob trying to learn from your code.

Const correctness

• Shouldn't your peek function return a const reference? Right now it returns a reference, but peek isn't aptly named if it returns something you expect to be able to play with. I think this is especially important since you declare peek const but a const function that returns something to a client that the client can change is not so much a classic const function

Move semantics

• Can't you use move to be explicit here:

template<class T> Stack<T>::Stack(Stack&& s) :first{s.first}, n{s.n} { s.first = nullptr; s.n = 0;

Why not just std::move? You're basically implementing the default move operator, no? Or if not, surely you can implement this template function above in terms of the one that comes after it, the operator=? This would cut down on code redundancy.

Error checking

• Right now your pop() function doesn't seem to have any error checking or special reaction if a client seeks to pop off an empty list.