#pragma once
If you plan on writing portable code, prefer #include
guards over #pragma once
. While most compilers provide support for #pragma once
, there is no guarantee every implementation behaves the same. Be aware of the pitfalls of #pragma once
if you decide to use them.
~Stack();
Follow the rule of five. If you define, =default
or =delete
any of the special member functions, you should consider if the behavior of the other special member functions are appropriate. In C++11, the special member functions are the destructor, copy constructor, move constructor, copy assignment operator, and move assignment operator.
~Stack();
Stack(Stack const&);
Stack(Stack &&);
Stack& operator=(Stack const&);
Stack& operator=(Stack &&);
You already realize that you need a destructor to clean up the Node
s on destruction. Do you need a user-defined copy constructor? The copy ctor value copies your data members. So, copying top
only copies the pointer, not the pointed to Node<T>
. Copying a populated Stack<T>
results in two stacks, both with pointers pointing at the same data. You'll get undefined behavior when you double delete this list.
{
Stack<int> s1;
s1.push(1);
s2.push(2);
{
Stack<int> s2(s1); // Copy-construct. Fine!
s2.pop(); // Fine!
//auto v = s1.pop(); // double free/delete = undefined behavior, Fire everywhere
} // or go out of scope with s2, destroying all data
} // then s1 goes out of scope... UB happens again.
The general advice is to avoid defining any of the special member functions if you can (rule of zero). If you need to define any of the special member functions, then =default
, =delete
, or provide a user definition for them all (rule of five).
template<typename T>
inline Stack<T>::Stack() :
numElements(0),
top(nullptr) {}
When you have constant initializers, prefer the in-class initializers.
struct Stack {
// Stack() = default;
private:
unsigned numElements {0};
Node<T>* top {nullptr};
};
In this context, all of your data is set to constant initializers, so you can just use the compiler generated default constructor. You can explicitly default it (uncomment above) or implicitly default it (delete the commented line). Note - The default constructor is only implicitly auto-generated if there is no other user-declared constructor.
template<typename T>
inline Stack<T>::~Stack()
{
while (!isEmpty())
{
pop();
}
}
In your pop()
, you do a lot of work. pop()
has its own boundary check (on top of the destructor boundary check), an element copy, a delete, a pointer copy, and a decrement on each call. ~Stack()
just needs the delete and pointer copy. Consider factoring out that portion that removes the top
node and have both ~Stack
and pop()
call that.
template <typename T>
inline void Stack<T>::unchecked_pop() {
Node<T>* temp = top;
top = temp-> prev;
delete temp;
}
template<typename T>
inline Stack<T>::~Stack()
{
while (!isEmpty())
{
unchecked_pop();
}
}
template <typename T>
inline T& Stack<T>::pop() {
if (numElements > 1) {
returnT = top->data;
unchecked_pop();
num_elements--;
return returnT;
}
// ...
}
Avoid calling new
and delete
explicitly. In your code, you'll notice a pattern of creating a new Node<T>
followed by copying some T
(which could throw).
Node<T>* tempNode = new Node<T>;
tempNode->data = rhs; // if this throws
top = tempNode; // then this is never reached, memory leaks
// and not cleaned up until OS reclaims
If you need to take ownership of a pointer, use std::unique_ptr
/std::make_unique
. C++14 adds std::make_unique
, but you can use it C++11. Note - Don't add make_unique to std
like shown in the linked answer.
DRY (don't repeat yourself) up your push
and pop
. The two statement bodies for each function essentially does the same work. In push
, you trade away a pointer copy for a branch.
template <typename T>
inline void Stack<T>::push(const T& rhs) {
if (numElements == max_size) {
throw std::overflow_error("Stack Overflow");
}
auto temp = std::make_unique<Node<int>>();
tempNode->data = rhs;
tempNode->prev = top;
top = temp.release(); // pass ownership of the new top to Stack
numElements++;
}
In pop()
, a single-element stack has a Node
whose prev
points to nullptr
. You don't need the special case for 1 element.
template <typename T>
inline T & Stack<T>::pop() {
if (empty()) {
// TODO: what do I do here?
}
returnT = top->data;
unchecked_pop();
numElements--;
return returnT;
}
You don't provide any other access to top
. Perhaps you should just return by value?
Is this enough functionality for a Stack? Or should I implement more functions?
Does it meet your needs? At the very least, I would expect C++11 and beyond containers to support move operations (move construct, move assign, data emplacement, swap by move), comparisons, and perhaps even allocators. I would start by looking at std::stack
.
When I pop from an empty Stack I simply return nothing. Is there something else I should do?
If you tell others "I'm returning T&
from pop
, it better return a T&
. Consider the following:
Stack<int> s;
auto top = s.pop(); // BOOM!
You could return an optional
from pop()
. C++11 versions exist in Boost, Abseil, and Mnmlstc.
Or you could do it the standard way and not return anything. This was adopted from SGI and annotated in their documentation:
[3] One might wonder why pop()
returns void
, instead of value_type
. That is, why must one use top()
and pop()
to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop()
returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop()
to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top()
to inspect the value at the top of the stack.
My IDE added inline
. Is this actually an appropriate use?
Yes.
General design notes - Utilize the adapter pattern.
I brought up the rule of zero earlier (If you can avoid defining the default operations, do). How could we accomplish that with a Stack
? Well, a Stack
is an abstract data type (an interface) over a collection of data that provides operations on a single end. The standard library provides us a bunch of collection types. We have sequence types that have front operations (std::deque
, std::list
, std::forward_list
). We have sequence types that have back operations (std::deque
, std::list
, std::vector
).
For the interface, it's very simple. We adapt the stack interface to the interface of a container that supports modifying operations on its back.
template <typename T, typename Container = std::deque<T>>
struct Stack {
public:
void push(T const& value) { data.push_back(value); }
void pop() { data.pop_back(); }
T & top(); { return data.back(); }
T const& top() const; { return data.back(); }
bool empty() const { return data.empty(); }
std::size_t size() const { return data.size(); }
// etc...
private:
Container data;
};
Note - Each member function should instead call a non-member free-standing function, but this review is getting pretty long and I'm trying to keep this example simple.
By using a container type to automatically manage the memory, I don't have to provide a destructor, copy operations, or move operations. The compiler-generated special member functions all work correct by construction. Think about how you would implement a queue using the adapter pattern.
Follow-up:
If you didn't remove the destructor would you = delete the copy constructor?
Do you want your Stack
to be copyable? If not, they go ahead and =delete
it. I'm going to assume you do want a copyable Stack
. Since you are manually managing memory, you need to provide your own copy constructor.
Stack(Stack&) = default;
is essentially
Stack(Stack const& other) :
numElements{other.numElements},
top{other.top}, // Simple pointer copy, both stacks own same Node<T>
returnT{other.returnT}
{}
Your provided copy constructor needs to deep copy every Node
by traversing the linked list.
Stack(Stack const& other) :
numElements{other.numElements},
returnT{other.returnT}
{
// Actually deep copy other's linked list
}
If I take the return out of pop() and put it in top() I still need to deal with an empty stack. Return nothing?
It depends. Some believe in programming-by-contract, which would require the user to ensure that the container is not empty on pop()
and top()
T& top() const {
return top->data; // UB if empty. User's fault for not checking size.
}
I would use exceptions or Expects()
from the GSL.
T& top() const {
Expects(!empty()); // if empty, either throw or fail fast
return top->data;
}
You have to decide what tradeoffs you are willing to make for defined behavior and safety.
Would a shared_ptr be needed here since Node->prev and top point to the same thing, albeit for 1 LoC?
Internally, std::unique_ptr
would be better to represent the ownership semantics. Stack
is the only owner of top
. top
is the only owner of the previous Node<T>
. And so on. Smart pointers are great for conveying ownership, but their behavior with the special members in the rule of five isn't helpful. std::unique_ptr
implementations still need a user-defined destructor (stack overflow from recursive destruction) and copy ops (not copyable). std::shared_ptr
is similar, but performs a shallow copy like the raw pointer. I recommend Herb Sutter's talk on "Leak-Freedom in C++... By Default".
I also wish to say I was intentionally avoiding the STL. After all why use an underlying data structure that provides more functionality than I do when I could also just use std::stack
That's fine. I was just pointing out how to use the adaptor pattern. In my example, I could use any container with push_back
, pop_back
, etc (like plf::list).
Stack<int, plf::list<int>> stk;
In your Stack, it would be better to move all of the linked list management into its own container and have Stack use that container. That way, when you move to the next common abstract data type, a queue, you'll have a linked list container that can be reused.