Stack Interview Code methods made from class Node and Smart Pointers
$begingroup$
Mainly looking for feedback on my use of smart pointers to implement a standard stack. For interview level production code I have also include a namespace and asserts to test my class, let me know if that would be appropriate for an interview. I'd like feedback on my pointer management to avoid memory leaks, like how I have the option to use the classic SomeObjectNameHere* pointer to swap data in my swap function or the unique_ptr swap method.
Other than that I have taken feedback from all my previous posts to properly. Let me know what you think
#include <cassert>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
namespace sonsprl
{
class Stack
{
private:
class Node
{ private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
~Node() { m_previous.reset(); }
const int data() { return m_data; }
std::unique_ptr<Node>& previous() { return m_previous; }
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
~Stack() { m_top.reset(); }
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
int top() {
return m_top.get()->data();
}
int size() {
return m_size;
}
bool empty() {
return (m_size == 0) ? true : false;
}
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
};
}
int main()
{
sonsprl::Stack stack;
try {
stack.pop_back();
} catch(const std::out_of_range& e) {
std::cout << e.what() << 'n';
}
assert(stack.empty());
stack.push_back(1);
stack.push_back(2);
stack.push_back(3);
assert(stack.size() == 3);
assert(stack.top() == 3);
stack.pop_back();
stack.pop_back();
assert(stack.size() == 1);
std::cout << stack << 'n';
stack.push_back(4);
stack.push_back(4);
assert(stack.empty() == false);
sonsprl::Stack swap_stack;
swap_stack.push_back(5);
swap_stack.push_back(6);
swap_stack.push_back(7);
swap_stack.push_back(8);
assert(swap_stack.top() == 8);
std::cout << "pre swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
swap_stack.swap(stack);
std::cout << "post swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
assert(stack.top() == 8);
assert(swap_stack.top() == 4);
std::cout << "passed all stack tests :) n";
return 0;
}
c++ c++11 stack pointers namespaces
asked Mar 21 at 16:32
greggreg
39928
$endgroup$
add a comment |
$begingroup$
Mainly looking for feedback on my use of smart pointers to implement a standard stack. For interview level production code I have also include a namespace and asserts to test my class, let me know if that would be appropriate for an interview. I'd like feedback on my pointer management to avoid memory leaks, like how I have the option to use the classic SomeObjectNameHere* pointer to swap data in my swap function or the unique_ptr swap method.
Other than that I have taken feedback from all my previous posts to properly. Let me know what you think
#include <cassert>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
namespace sonsprl
{
class Stack
{
private:
class Node
{ private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
~Node() { m_previous.reset(); }
const int data() { return m_data; }
std::unique_ptr<Node>& previous() { return m_previous; }
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
~Stack() { m_top.reset(); }
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
int top() {
return m_top.get()->data();
}
int size() {
return m_size;
}
bool empty() {
return (m_size == 0) ? true : false;
}
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
};
}
int main()
{
sonsprl::Stack stack;
try {
stack.pop_back();
} catch(const std::out_of_range& e) {
std::cout << e.what() << 'n';
}
assert(stack.empty());
stack.push_back(1);
stack.push_back(2);
stack.push_back(3);
assert(stack.size() == 3);
assert(stack.top() == 3);
stack.pop_back();
stack.pop_back();
assert(stack.size() == 1);
std::cout << stack << 'n';
stack.push_back(4);
stack.push_back(4);
assert(stack.empty() == false);
sonsprl::Stack swap_stack;
swap_stack.push_back(5);
swap_stack.push_back(6);
swap_stack.push_back(7);
swap_stack.push_back(8);
assert(swap_stack.top() == 8);
std::cout << "pre swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
swap_stack.swap(stack);
std::cout << "post swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
assert(stack.top() == 8);
assert(swap_stack.top() == 4);
std::cout << "passed all stack tests :) n";
return 0;
}
c++ c++11 stack pointers namespaces
asked Mar 21 at 16:32
greggreg
39928
$endgroup$
3
$begingroup$
As a quick comment: one thing you should try to pay more attention to is const correctness. Again, there are many member functions that should be const. If the function does not modify the object contents, make it const.
$endgroup$
– Juho
Mar 21 at 18:30
add a comment |
$begingroup$
Mainly looking for feedback on my use of smart pointers to implement a standard stack. For interview level production code I have also include a namespace and asserts to test my class, let me know if that would be appropriate for an interview. I'd like feedback on my pointer management to avoid memory leaks, like how I have the option to use the classic SomeObjectNameHere* pointer to swap data in my swap function or the unique_ptr swap method.
Other than that I have taken feedback from all my previous posts to properly. Let me know what you think
#include <cassert>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
namespace sonsprl
{
class Stack
{
private:
class Node
{ private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
~Node() { m_previous.reset(); }
const int data() { return m_data; }
std::unique_ptr<Node>& previous() { return m_previous; }
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
~Stack() { m_top.reset(); }
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
int top() {
return m_top.get()->data();
}
int size() {
return m_size;
}
bool empty() {
return (m_size == 0) ? true : false;
}
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
};
}
int main()
{
sonsprl::Stack stack;
try {
stack.pop_back();
} catch(const std::out_of_range& e) {
std::cout << e.what() << 'n';
}
assert(stack.empty());
stack.push_back(1);
stack.push_back(2);
stack.push_back(3);
assert(stack.size() == 3);
assert(stack.top() == 3);
stack.pop_back();
stack.pop_back();
assert(stack.size() == 1);
std::cout << stack << 'n';
stack.push_back(4);
stack.push_back(4);
assert(stack.empty() == false);
sonsprl::Stack swap_stack;
swap_stack.push_back(5);
swap_stack.push_back(6);
swap_stack.push_back(7);
swap_stack.push_back(8);
assert(swap_stack.top() == 8);
std::cout << "pre swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
swap_stack.swap(stack);
std::cout << "post swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
assert(stack.top() == 8);
assert(swap_stack.top() == 4);
std::cout << "passed all stack tests :) n";
return 0;
}
c++ c++11 stack pointers namespaces
asked Mar 21 at 16:32
greggreg
39928
$endgroup$
Mainly looking for feedback on my use of smart pointers to implement a standard stack. For interview level production code I have also include a namespace and asserts to test my class, let me know if that would be appropriate for an interview. I'd like feedback on my pointer management to avoid memory leaks, like how I have the option to use the classic SomeObjectNameHere* pointer to swap data in my swap function or the unique_ptr swap method.
Other than that I have taken feedback from all my previous posts to properly. Let me know what you think
#include <cassert>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
namespace sonsprl
{
class Stack
{
private:
class Node
{ private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
~Node() { m_previous.reset(); }
const int data() { return m_data; }
std::unique_ptr<Node>& previous() { return m_previous; }
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
~Stack() { m_top.reset(); }
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
int top() {
return m_top.get()->data();
}
int size() {
return m_size;
}
bool empty() {
return (m_size == 0) ? true : false;
}
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
};
}
int main()
{
sonsprl::Stack stack;
try {
stack.pop_back();
} catch(const std::out_of_range& e) {
std::cout << e.what() << 'n';
}
assert(stack.empty());
stack.push_back(1);
stack.push_back(2);
stack.push_back(3);
assert(stack.size() == 3);
assert(stack.top() == 3);
stack.pop_back();
stack.pop_back();
assert(stack.size() == 1);
std::cout << stack << 'n';
stack.push_back(4);
stack.push_back(4);
assert(stack.empty() == false);
sonsprl::Stack swap_stack;
swap_stack.push_back(5);
swap_stack.push_back(6);
swap_stack.push_back(7);
swap_stack.push_back(8);
assert(swap_stack.top() == 8);
std::cout << "pre swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
swap_stack.swap(stack);
std::cout << "post swapn";
std::cout << stack << 'n';
std::cout << swap_stack << 'n';
assert(stack.top() == 8);
assert(swap_stack.top() == 4);
std::cout << "passed all stack tests :) n";
return 0;
}
c++ c++11 stack pointers namespaces
c++ c++11 stack pointers namespaces
asked Mar 21 at 16:32
greggreg
39928
asked Mar 21 at 16:32
greggreg
39928
edited Mar 21 at 19:08
greg
asked Mar 21 at 16:32
greggreg
39928
asked Mar 21 at 16:32
greggreg
39928
asked Mar 21 at 16:32
greggreg
39928
39928
3
$begingroup$
As a quick comment: one thing you should try to pay more attention to is const correctness. Again, there are many member functions that should be const. If the function does not modify the object contents, make it const.
$endgroup$
– Juho
Mar 21 at 18:30
add a comment |
3
$begingroup$
As a quick comment: one thing you should try to pay more attention to is const correctness. Again, there are many member functions that should be const. If the function does not modify the object contents, make it const.
$endgroup$
– Juho
Mar 21 at 18:30
3
3
$begingroup$
As a quick comment: one thing you should try to pay more attention to is const correctness. Again, there are many member functions that should be const. If the function does not modify the object contents, make it const.
$endgroup$
– Juho
Mar 21 at 18:30
$begingroup$
As a quick comment: one thing you should try to pay more attention to is const correctness. Again, there are many member functions that should be const. If the function does not modify the object contents, make it const.
$endgroup$
– Juho
Mar 21 at 18:30
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Overall
Not sure I agree with the use of std::unique_ptr inside of Node. BUT I can't really argue against it. So I am not going to push the point.
You need to concentrate on your const correctness.
Design
Using a linked list for a stack seems very inefficient way of doing this. Each object that you save required an additional pointer. In this case were your data is a int you are basically doubling the space requirements (that's not including any overhead for memory management imposed by the system libraries).
The standard provides a std::stack class. This uses the std::deque underneath the hood (default) to store the data.
You should think about what it would take to templatize your Stack class. Storing int is good as a test; but there is no reason you could not store any object. Once you have done that there are a couple of extra functions that would be nice:
void push_back(T const& data); // insert by copy.
void push_back(T&& data); // insert by move
template<typename... Args>
void emplace_back(Args&& p...); // construct in place at the back
Code Review
I assume this has some meaning to you?
namespace sonsprl
Passing a std::unqiue_ptr by non-cost referece is a bit strange. I would normally expect that to be passed by r-value reference. When I was reading the Stack class below it confused me that you were passing a std::unique_ptr as a parameter without the std::move.
Node(int data, std::unique_ptr<Node>& previous) {
You are affectively hiding the transfer of ownership that the C++ community has tried very hard to make explicit and visible.
Both your destructors are us-less:
~Node() { m_previous.reset(); }
~Stack() { m_top.reset(); }
I would remove both.
You could mark this function as const. I would not bother marking the int const (but it does not hurt). When you convert this into a template you should return by const reference. T const&.
const int data() { return m_data; }
// I would have written like this:
T const& data() const { return m_data; }
//^^^^^^ ^^^^^
As mentioned above. I don't like the passing of m_top as a parameter (and it being changed inside the Node constructor).
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
I would have written it like this:
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, std::move(m_top)));
++m_size;
}
This way I can explicitly show that I am transferring ownership of m_top into the Node and that the newly created object is taking the place as the new value of m_top.
There is an empty() function that allows users to check if the stack is empty before calling pop_back(). So also checking inside is a waste of time. If you really want to check then you should provide a checked and an unchecked version of pop.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Note: the main use case is going to be something like this:
while(!stack.empty()) {
stack.pop_back(); // I just checked its empty
} // are you going to check again?
If you look at functions in the standard library they tend not to throw (even if this would cause the object to be invalid). Instead the writters provide mechanisms to validate the pre-conditions of method so the user can do the check manually. Sometimes they also provide checked alternatives. That way a user of the functionality does not need to pay an extra cost (for the check) if they have already validate the pre-conditions.
An example of this is:
std::vector::operatorstd::size_t index) // unchecked access into the container.
std::vector::afstd::size_t index) // un-unchecked access into the container.
The top() function should be const. Your return value is inconsistent with the return type from data() (which returns a const). Consistency is king in programming.
Talking about consistency. The pop_back() function checks the state of the container (and throws if it is not valid). To be consistent the top() method should perform a similar check (or both of them should not perform a check).
int top() {
return m_top.get()->data();
}
Do you need to call get() above?
Another couple of function that should be marked const
int size() {
bool empty() {
Swap should be marked noexcept:
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
I don't see you swapping the size!!!!!!
Every part of the swapped object should be exchanged.
The normal pattern for this is to use swap() on each member.
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
It's also nice to add a friend function so others can do the swap naturally as well.
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
When printing. The value being printed is normally marked const (because printing it should not change it).
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
^^^^
Why are you building a string to output?
std::string stack_string = "";
// STUFF
os << stack_string;
Just print each value directly to the stream.
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
os << '|' << current->data() << "|n";
}
One late entry:
return (m_size == 0) ? true : false;
You are using a bool test to decide which bool to return. Simpler to simply return the result of the test.
return m_size == 0;
How I would have written it (apart from keeping the std::unique_ptr in Node).
namespace ThorsAnvil
{
namespace Container
{
template<typename T>
class Stack
{
struct Node;
using Chain = std::unique_ptr<Node>;
struct Node
{
T data;
Chain prev;
Node(Chain&& prev, T const& data)
: data(data)
, prev(std::move(prev))
{}
Node(Chain&& prev, T&& data)
: data(std::move(data))
, prev(std::move(prev))
{}
template<typename... Args>
Node(Chain&& prev, Args&&... p)
: data(std::forward<Args>(p)...)
, prev(std::move(prev))
{}
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
void push_back(T const& data) {
m_top = std::make_unique<Node>(std::move(m_top), data);
++m_size;
}
void push_back(T&& data) {
m_top = std::make_unique<Node>(std::move(m_top), std::move(data));
++m_size;
}
template<typename... Args>
void push_back(Args&&... p) {
m_top = std::make_unique<Node>(std::move(m_top), std::forward<Args>(p)...);
++m_size;
}
void pop_back() {
m_top = std::move(m_top->prev);
--m_size;
}
T const& top() const {return m_top->data;}
int size() const {return m_size;}
bool empty() const {return m_size == 0;}
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
Node* current = stack.m_top.get();
for(; current; current = current->prev.get()) {
os << "|" << current->data << "|n";
}
return os << "---n";
}
};
}
}
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
$endgroup$
1
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote usingstd::unique_ptrin favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.
$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're usingswap(m_top, other.m_top);over theunique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this callnew Node(data, std::move(m_top)in mypush_backfunction? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?
$endgroup$
– greg
Mar 21 at 19:34
1
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to usestd::moveinside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by usingstd::move.
$endgroup$
– Martin York
Mar 21 at 20:04
1
$begingroup$
@greg The rule of zero is why you don't need destructors. Thestd::unique_ptrdestructor will automatically be called and release its resources. You doing it manually is not required.
$endgroup$
– Martin York
Mar 21 at 20:05
1
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
|
show 7 more comments
$begingroup$
swapdoes not swap sizes.If
pop_backthrows on empty stack,topshall also throw.
I see no reason for an
operator<<to build a string.
os << '|' << std::to_string(current->data()) << '|n';
in a loop achieves the same result.
I would also consider letting
Nodeto output itself withNode::operator<<.
answered Mar 21 at 18:32
vnpvnp
40.5k233103
$endgroup$
add a comment |
$begingroup$
class Node {
private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
Since Node is an implementation detail of Stack, you don't need to hide Nodes members data and previous from Stack. Consider using aggregate initialization so that members can be directly manipulated.
~Node() { m_previous.reset(); }
Since the destructor isn't doing anything after std::unique_ptr<T>::reset(), it's equivalent to letting the class call the destructor of your std::unique_ptr<Node> member.
~Node() { }
Now, you have chained your pointers such that the current node is the owner of the previous node which owns the previous node and so on. When we call the destructor, this is essentially what is happening
m_previous.reset() calls
🡒 m_previous->~Node()
🡒 m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->m_previous->~Node()
🡒 and so on
And it's correct in that each node gets cleaned up and all the cleanup happens automatically. Unfortunately, it's also recursive which means its bounded by the stack (memory) depth. To fix this, you'll need to iteratively remove elements.
Whenever you define any of the special member functions (destructor, copy/move constructor, copy/move assignment), you should consider whether your class needs the others. This is commonly known as the rule of five. By providing the destructor, the move operations are not declared. Normally, the copy operations are defaulted, but std::unique_ptr as a data member results in those being implicitly deleted. You'll need to implement the copy and move operations if your stack is to have those value semantics. The general guideline is that if you explicitly declare any of the special member functions, then explicitly declare all of the special member functions and explicitly =default (opt into the implicit behavior), =delete (opt out of the implicit behavior), or user-define each of them.
const int data() { return m_data; }
const as a qualifier on the return type is ignored here.
class Stack {
...
public:
~Stack() { m_top.reset(); }
Same issues as node, from recursive destruction to missing copy/move operations.
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
Avoid new and prefer std::make_unique to make std::unique_ptrs. It cuts down on the duplication and enforces consistency when you need safety in more complex initialization sequences.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Don't use else after language constructs that interrupts control flow (return, break, continue, goto).
int top() {
return m_top.get()->data();
}
Be consistent with the naming. If directionality matters to you, then back() would be consistent with push_back() and pop_back(). top() would go better with functions like push(), and pop().
Be consistent with your exception handling. If you throw on an empty stack pop_back(), then you should throw on an empty stack top().
In order to modify the top value, the user has to pop (deallocate) and push (allocate). Consider allowing the user to access the top element by reference and modify the element in place.
bool empty() {
return (m_size == 0) ? true : false;
}
m_size == 0 will return a boolean that maps to the same exact values in your ternary. The compiler knows that and optimizes it for you, but you could help readers and just do it yourself.
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
You forgot to swap the size.
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
stack is passed in as a reference. operator<< doesn't modify the contents of stack and can be qualified with const.
You don't have to convert data (int) to a std::string to stream into a std::ostream. There is already an overload that does this for you.
Do you even need operator<<()? A stack is a last in-first out container. Inspection only exists on the latest element pushed on the stack that hasn't been popped. This function also requires the inclusion of <iostream>. A static constructor is transparently injected into every translation unit that includes this header, whether IOStreams are used or not in the user application.
Overall, you should read up on const-correctness and noexcept specification. As for the design of your stack, I would consider splitting the management of the nodes (forward_list?) from the interface of stack, which could be adapted over an existing sequence interface.
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215944%2fstack-interview-code-methods-made-from-class-node-and-smart-pointers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Overall
Not sure I agree with the use of std::unique_ptr inside of Node. BUT I can't really argue against it. So I am not going to push the point.
You need to concentrate on your const correctness.
Design
Using a linked list for a stack seems very inefficient way of doing this. Each object that you save required an additional pointer. In this case were your data is a int you are basically doubling the space requirements (that's not including any overhead for memory management imposed by the system libraries).
The standard provides a std::stack class. This uses the std::deque underneath the hood (default) to store the data.
You should think about what it would take to templatize your Stack class. Storing int is good as a test; but there is no reason you could not store any object. Once you have done that there are a couple of extra functions that would be nice:
void push_back(T const& data); // insert by copy.
void push_back(T&& data); // insert by move
template<typename... Args>
void emplace_back(Args&& p...); // construct in place at the back
Code Review
I assume this has some meaning to you?
namespace sonsprl
Passing a std::unqiue_ptr by non-cost referece is a bit strange. I would normally expect that to be passed by r-value reference. When I was reading the Stack class below it confused me that you were passing a std::unique_ptr as a parameter without the std::move.
Node(int data, std::unique_ptr<Node>& previous) {
You are affectively hiding the transfer of ownership that the C++ community has tried very hard to make explicit and visible.
Both your destructors are us-less:
~Node() { m_previous.reset(); }
~Stack() { m_top.reset(); }
I would remove both.
You could mark this function as const. I would not bother marking the int const (but it does not hurt). When you convert this into a template you should return by const reference. T const&.
const int data() { return m_data; }
// I would have written like this:
T const& data() const { return m_data; }
//^^^^^^ ^^^^^
As mentioned above. I don't like the passing of m_top as a parameter (and it being changed inside the Node constructor).
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
I would have written it like this:
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, std::move(m_top)));
++m_size;
}
This way I can explicitly show that I am transferring ownership of m_top into the Node and that the newly created object is taking the place as the new value of m_top.
There is an empty() function that allows users to check if the stack is empty before calling pop_back(). So also checking inside is a waste of time. If you really want to check then you should provide a checked and an unchecked version of pop.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Note: the main use case is going to be something like this:
while(!stack.empty()) {
stack.pop_back(); // I just checked its empty
} // are you going to check again?
If you look at functions in the standard library they tend not to throw (even if this would cause the object to be invalid). Instead the writters provide mechanisms to validate the pre-conditions of method so the user can do the check manually. Sometimes they also provide checked alternatives. That way a user of the functionality does not need to pay an extra cost (for the check) if they have already validate the pre-conditions.
An example of this is:
std::vector::operatorstd::size_t index) // unchecked access into the container.
std::vector::afstd::size_t index) // un-unchecked access into the container.
The top() function should be const. Your return value is inconsistent with the return type from data() (which returns a const). Consistency is king in programming.
Talking about consistency. The pop_back() function checks the state of the container (and throws if it is not valid). To be consistent the top() method should perform a similar check (or both of them should not perform a check).
int top() {
return m_top.get()->data();
}
Do you need to call get() above?
Another couple of function that should be marked const
int size() {
bool empty() {
Swap should be marked noexcept:
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
I don't see you swapping the size!!!!!!
Every part of the swapped object should be exchanged.
The normal pattern for this is to use swap() on each member.
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
It's also nice to add a friend function so others can do the swap naturally as well.
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
When printing. The value being printed is normally marked const (because printing it should not change it).
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
^^^^
Why are you building a string to output?
std::string stack_string = "";
// STUFF
os << stack_string;
Just print each value directly to the stream.
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
os << '|' << current->data() << "|n";
}
One late entry:
return (m_size == 0) ? true : false;
You are using a bool test to decide which bool to return. Simpler to simply return the result of the test.
return m_size == 0;
How I would have written it (apart from keeping the std::unique_ptr in Node).
namespace ThorsAnvil
{
namespace Container
{
template<typename T>
class Stack
{
struct Node;
using Chain = std::unique_ptr<Node>;
struct Node
{
T data;
Chain prev;
Node(Chain&& prev, T const& data)
: data(data)
, prev(std::move(prev))
{}
Node(Chain&& prev, T&& data)
: data(std::move(data))
, prev(std::move(prev))
{}
template<typename... Args>
Node(Chain&& prev, Args&&... p)
: data(std::forward<Args>(p)...)
, prev(std::move(prev))
{}
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
void push_back(T const& data) {
m_top = std::make_unique<Node>(std::move(m_top), data);
++m_size;
}
void push_back(T&& data) {
m_top = std::make_unique<Node>(std::move(m_top), std::move(data));
++m_size;
}
template<typename... Args>
void push_back(Args&&... p) {
m_top = std::make_unique<Node>(std::move(m_top), std::forward<Args>(p)...);
++m_size;
}
void pop_back() {
m_top = std::move(m_top->prev);
--m_size;
}
T const& top() const {return m_top->data;}
int size() const {return m_size;}
bool empty() const {return m_size == 0;}
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
Node* current = stack.m_top.get();
for(; current; current = current->prev.get()) {
os << "|" << current->data << "|n";
}
return os << "---n";
}
};
}
}
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
$endgroup$
1
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote usingstd::unique_ptrin favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.
$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're usingswap(m_top, other.m_top);over theunique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this callnew Node(data, std::move(m_top)in mypush_backfunction? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?
$endgroup$
– greg
Mar 21 at 19:34
1
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to usestd::moveinside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by usingstd::move.
$endgroup$
– Martin York
Mar 21 at 20:04
1
$begingroup$
@greg The rule of zero is why you don't need destructors. Thestd::unique_ptrdestructor will automatically be called and release its resources. You doing it manually is not required.
$endgroup$
– Martin York
Mar 21 at 20:05
1
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
|
show 7 more comments
$begingroup$
Overall
Not sure I agree with the use of std::unique_ptr inside of Node. BUT I can't really argue against it. So I am not going to push the point.
You need to concentrate on your const correctness.
Design
Using a linked list for a stack seems very inefficient way of doing this. Each object that you save required an additional pointer. In this case were your data is a int you are basically doubling the space requirements (that's not including any overhead for memory management imposed by the system libraries).
The standard provides a std::stack class. This uses the std::deque underneath the hood (default) to store the data.
You should think about what it would take to templatize your Stack class. Storing int is good as a test; but there is no reason you could not store any object. Once you have done that there are a couple of extra functions that would be nice:
void push_back(T const& data); // insert by copy.
void push_back(T&& data); // insert by move
template<typename... Args>
void emplace_back(Args&& p...); // construct in place at the back
Code Review
I assume this has some meaning to you?
namespace sonsprl
Passing a std::unqiue_ptr by non-cost referece is a bit strange. I would normally expect that to be passed by r-value reference. When I was reading the Stack class below it confused me that you were passing a std::unique_ptr as a parameter without the std::move.
Node(int data, std::unique_ptr<Node>& previous) {
You are affectively hiding the transfer of ownership that the C++ community has tried very hard to make explicit and visible.
Both your destructors are us-less:
~Node() { m_previous.reset(); }
~Stack() { m_top.reset(); }
I would remove both.
You could mark this function as const. I would not bother marking the int const (but it does not hurt). When you convert this into a template you should return by const reference. T const&.
const int data() { return m_data; }
// I would have written like this:
T const& data() const { return m_data; }
//^^^^^^ ^^^^^
As mentioned above. I don't like the passing of m_top as a parameter (and it being changed inside the Node constructor).
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
I would have written it like this:
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, std::move(m_top)));
++m_size;
}
This way I can explicitly show that I am transferring ownership of m_top into the Node and that the newly created object is taking the place as the new value of m_top.
There is an empty() function that allows users to check if the stack is empty before calling pop_back(). So also checking inside is a waste of time. If you really want to check then you should provide a checked and an unchecked version of pop.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Note: the main use case is going to be something like this:
while(!stack.empty()) {
stack.pop_back(); // I just checked its empty
} // are you going to check again?
If you look at functions in the standard library they tend not to throw (even if this would cause the object to be invalid). Instead the writters provide mechanisms to validate the pre-conditions of method so the user can do the check manually. Sometimes they also provide checked alternatives. That way a user of the functionality does not need to pay an extra cost (for the check) if they have already validate the pre-conditions.
An example of this is:
std::vector::operatorstd::size_t index) // unchecked access into the container.
std::vector::afstd::size_t index) // un-unchecked access into the container.
The top() function should be const. Your return value is inconsistent with the return type from data() (which returns a const). Consistency is king in programming.
Talking about consistency. The pop_back() function checks the state of the container (and throws if it is not valid). To be consistent the top() method should perform a similar check (or both of them should not perform a check).
int top() {
return m_top.get()->data();
}
Do you need to call get() above?
Another couple of function that should be marked const
int size() {
bool empty() {
Swap should be marked noexcept:
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
I don't see you swapping the size!!!!!!
Every part of the swapped object should be exchanged.
The normal pattern for this is to use swap() on each member.
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
It's also nice to add a friend function so others can do the swap naturally as well.
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
When printing. The value being printed is normally marked const (because printing it should not change it).
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
^^^^
Why are you building a string to output?
std::string stack_string = "";
// STUFF
os << stack_string;
Just print each value directly to the stream.
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
os << '|' << current->data() << "|n";
}
One late entry:
return (m_size == 0) ? true : false;
You are using a bool test to decide which bool to return. Simpler to simply return the result of the test.
return m_size == 0;
How I would have written it (apart from keeping the std::unique_ptr in Node).
namespace ThorsAnvil
{
namespace Container
{
template<typename T>
class Stack
{
struct Node;
using Chain = std::unique_ptr<Node>;
struct Node
{
T data;
Chain prev;
Node(Chain&& prev, T const& data)
: data(data)
, prev(std::move(prev))
{}
Node(Chain&& prev, T&& data)
: data(std::move(data))
, prev(std::move(prev))
{}
template<typename... Args>
Node(Chain&& prev, Args&&... p)
: data(std::forward<Args>(p)...)
, prev(std::move(prev))
{}
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
void push_back(T const& data) {
m_top = std::make_unique<Node>(std::move(m_top), data);
++m_size;
}
void push_back(T&& data) {
m_top = std::make_unique<Node>(std::move(m_top), std::move(data));
++m_size;
}
template<typename... Args>
void push_back(Args&&... p) {
m_top = std::make_unique<Node>(std::move(m_top), std::forward<Args>(p)...);
++m_size;
}
void pop_back() {
m_top = std::move(m_top->prev);
--m_size;
}
T const& top() const {return m_top->data;}
int size() const {return m_size;}
bool empty() const {return m_size == 0;}
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
Node* current = stack.m_top.get();
for(; current; current = current->prev.get()) {
os << "|" << current->data << "|n";
}
return os << "---n";
}
};
}
}
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
$endgroup$
1
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote usingstd::unique_ptrin favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.
$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're usingswap(m_top, other.m_top);over theunique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this callnew Node(data, std::move(m_top)in mypush_backfunction? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?
$endgroup$
– greg
Mar 21 at 19:34
1
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to usestd::moveinside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by usingstd::move.
$endgroup$
– Martin York
Mar 21 at 20:04
1
$begingroup$
@greg The rule of zero is why you don't need destructors. Thestd::unique_ptrdestructor will automatically be called and release its resources. You doing it manually is not required.
$endgroup$
– Martin York
Mar 21 at 20:05
1
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
|
show 7 more comments
$begingroup$
Overall
Not sure I agree with the use of std::unique_ptr inside of Node. BUT I can't really argue against it. So I am not going to push the point.
You need to concentrate on your const correctness.
Design
Using a linked list for a stack seems very inefficient way of doing this. Each object that you save required an additional pointer. In this case were your data is a int you are basically doubling the space requirements (that's not including any overhead for memory management imposed by the system libraries).
The standard provides a std::stack class. This uses the std::deque underneath the hood (default) to store the data.
You should think about what it would take to templatize your Stack class. Storing int is good as a test; but there is no reason you could not store any object. Once you have done that there are a couple of extra functions that would be nice:
void push_back(T const& data); // insert by copy.
void push_back(T&& data); // insert by move
template<typename... Args>
void emplace_back(Args&& p...); // construct in place at the back
Code Review
I assume this has some meaning to you?
namespace sonsprl
Passing a std::unqiue_ptr by non-cost referece is a bit strange. I would normally expect that to be passed by r-value reference. When I was reading the Stack class below it confused me that you were passing a std::unique_ptr as a parameter without the std::move.
Node(int data, std::unique_ptr<Node>& previous) {
You are affectively hiding the transfer of ownership that the C++ community has tried very hard to make explicit and visible.
Both your destructors are us-less:
~Node() { m_previous.reset(); }
~Stack() { m_top.reset(); }
I would remove both.
You could mark this function as const. I would not bother marking the int const (but it does not hurt). When you convert this into a template you should return by const reference. T const&.
const int data() { return m_data; }
// I would have written like this:
T const& data() const { return m_data; }
//^^^^^^ ^^^^^
As mentioned above. I don't like the passing of m_top as a parameter (and it being changed inside the Node constructor).
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
I would have written it like this:
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, std::move(m_top)));
++m_size;
}
This way I can explicitly show that I am transferring ownership of m_top into the Node and that the newly created object is taking the place as the new value of m_top.
There is an empty() function that allows users to check if the stack is empty before calling pop_back(). So also checking inside is a waste of time. If you really want to check then you should provide a checked and an unchecked version of pop.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Note: the main use case is going to be something like this:
while(!stack.empty()) {
stack.pop_back(); // I just checked its empty
} // are you going to check again?
If you look at functions in the standard library they tend not to throw (even if this would cause the object to be invalid). Instead the writters provide mechanisms to validate the pre-conditions of method so the user can do the check manually. Sometimes they also provide checked alternatives. That way a user of the functionality does not need to pay an extra cost (for the check) if they have already validate the pre-conditions.
An example of this is:
std::vector::operatorstd::size_t index) // unchecked access into the container.
std::vector::afstd::size_t index) // un-unchecked access into the container.
The top() function should be const. Your return value is inconsistent with the return type from data() (which returns a const). Consistency is king in programming.
Talking about consistency. The pop_back() function checks the state of the container (and throws if it is not valid). To be consistent the top() method should perform a similar check (or both of them should not perform a check).
int top() {
return m_top.get()->data();
}
Do you need to call get() above?
Another couple of function that should be marked const
int size() {
bool empty() {
Swap should be marked noexcept:
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
I don't see you swapping the size!!!!!!
Every part of the swapped object should be exchanged.
The normal pattern for this is to use swap() on each member.
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
It's also nice to add a friend function so others can do the swap naturally as well.
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
When printing. The value being printed is normally marked const (because printing it should not change it).
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
^^^^
Why are you building a string to output?
std::string stack_string = "";
// STUFF
os << stack_string;
Just print each value directly to the stream.
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
os << '|' << current->data() << "|n";
}
One late entry:
return (m_size == 0) ? true : false;
You are using a bool test to decide which bool to return. Simpler to simply return the result of the test.
return m_size == 0;
How I would have written it (apart from keeping the std::unique_ptr in Node).
namespace ThorsAnvil
{
namespace Container
{
template<typename T>
class Stack
{
struct Node;
using Chain = std::unique_ptr<Node>;
struct Node
{
T data;
Chain prev;
Node(Chain&& prev, T const& data)
: data(data)
, prev(std::move(prev))
{}
Node(Chain&& prev, T&& data)
: data(std::move(data))
, prev(std::move(prev))
{}
template<typename... Args>
Node(Chain&& prev, Args&&... p)
: data(std::forward<Args>(p)...)
, prev(std::move(prev))
{}
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
void push_back(T const& data) {
m_top = std::make_unique<Node>(std::move(m_top), data);
++m_size;
}
void push_back(T&& data) {
m_top = std::make_unique<Node>(std::move(m_top), std::move(data));
++m_size;
}
template<typename... Args>
void push_back(Args&&... p) {
m_top = std::make_unique<Node>(std::move(m_top), std::forward<Args>(p)...);
++m_size;
}
void pop_back() {
m_top = std::move(m_top->prev);
--m_size;
}
T const& top() const {return m_top->data;}
int size() const {return m_size;}
bool empty() const {return m_size == 0;}
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
Node* current = stack.m_top.get();
for(; current; current = current->prev.get()) {
os << "|" << current->data << "|n";
}
return os << "---n";
}
};
}
}
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
$endgroup$
Overall
Not sure I agree with the use of std::unique_ptr inside of Node. BUT I can't really argue against it. So I am not going to push the point.
You need to concentrate on your const correctness.
Design
Using a linked list for a stack seems very inefficient way of doing this. Each object that you save required an additional pointer. In this case were your data is a int you are basically doubling the space requirements (that's not including any overhead for memory management imposed by the system libraries).
The standard provides a std::stack class. This uses the std::deque underneath the hood (default) to store the data.
You should think about what it would take to templatize your Stack class. Storing int is good as a test; but there is no reason you could not store any object. Once you have done that there are a couple of extra functions that would be nice:
void push_back(T const& data); // insert by copy.
void push_back(T&& data); // insert by move
template<typename... Args>
void emplace_back(Args&& p...); // construct in place at the back
Code Review
I assume this has some meaning to you?
namespace sonsprl
Passing a std::unqiue_ptr by non-cost referece is a bit strange. I would normally expect that to be passed by r-value reference. When I was reading the Stack class below it confused me that you were passing a std::unique_ptr as a parameter without the std::move.
Node(int data, std::unique_ptr<Node>& previous) {
You are affectively hiding the transfer of ownership that the C++ community has tried very hard to make explicit and visible.
Both your destructors are us-less:
~Node() { m_previous.reset(); }
~Stack() { m_top.reset(); }
I would remove both.
You could mark this function as const. I would not bother marking the int const (but it does not hurt). When you convert this into a template you should return by const reference. T const&.
const int data() { return m_data; }
// I would have written like this:
T const& data() const { return m_data; }
//^^^^^^ ^^^^^
As mentioned above. I don't like the passing of m_top as a parameter (and it being changed inside the Node constructor).
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
I would have written it like this:
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, std::move(m_top)));
++m_size;
}
This way I can explicitly show that I am transferring ownership of m_top into the Node and that the newly created object is taking the place as the new value of m_top.
There is an empty() function that allows users to check if the stack is empty before calling pop_back(). So also checking inside is a waste of time. If you really want to check then you should provide a checked and an unchecked version of pop.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Note: the main use case is going to be something like this:
while(!stack.empty()) {
stack.pop_back(); // I just checked its empty
} // are you going to check again?
If you look at functions in the standard library they tend not to throw (even if this would cause the object to be invalid). Instead the writters provide mechanisms to validate the pre-conditions of method so the user can do the check manually. Sometimes they also provide checked alternatives. That way a user of the functionality does not need to pay an extra cost (for the check) if they have already validate the pre-conditions.
An example of this is:
std::vector::operatorstd::size_t index) // unchecked access into the container.
std::vector::afstd::size_t index) // un-unchecked access into the container.
The top() function should be const. Your return value is inconsistent with the return type from data() (which returns a const). Consistency is king in programming.
Talking about consistency. The pop_back() function checks the state of the container (and throws if it is not valid). To be consistent the top() method should perform a similar check (or both of them should not perform a check).
int top() {
return m_top.get()->data();
}
Do you need to call get() above?
Another couple of function that should be marked const
int size() {
bool empty() {
Swap should be marked noexcept:
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
I don't see you swapping the size!!!!!!
Every part of the swapped object should be exchanged.
The normal pattern for this is to use swap() on each member.
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
It's also nice to add a friend function so others can do the swap naturally as well.
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
When printing. The value being printed is normally marked const (because printing it should not change it).
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
^^^^
Why are you building a string to output?
std::string stack_string = "";
// STUFF
os << stack_string;
Just print each value directly to the stream.
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
os << '|' << current->data() << "|n";
}
One late entry:
return (m_size == 0) ? true : false;
You are using a bool test to decide which bool to return. Simpler to simply return the result of the test.
return m_size == 0;
How I would have written it (apart from keeping the std::unique_ptr in Node).
namespace ThorsAnvil
{
namespace Container
{
template<typename T>
class Stack
{
struct Node;
using Chain = std::unique_ptr<Node>;
struct Node
{
T data;
Chain prev;
Node(Chain&& prev, T const& data)
: data(data)
, prev(std::move(prev))
{}
Node(Chain&& prev, T&& data)
: data(std::move(data))
, prev(std::move(prev))
{}
template<typename... Args>
Node(Chain&& prev, Args&&... p)
: data(std::forward<Args>(p)...)
, prev(std::move(prev))
{}
};
int m_size{0};
std::unique_ptr<Node> m_top;
public:
void push_back(T const& data) {
m_top = std::make_unique<Node>(std::move(m_top), data);
++m_size;
}
void push_back(T&& data) {
m_top = std::make_unique<Node>(std::move(m_top), std::move(data));
++m_size;
}
template<typename... Args>
void push_back(Args&&... p) {
m_top = std::make_unique<Node>(std::move(m_top), std::forward<Args>(p)...);
++m_size;
}
void pop_back() {
m_top = std::move(m_top->prev);
--m_size;
}
T const& top() const {return m_top->data;}
int size() const {return m_size;}
bool empty() const {return m_size == 0;}
void swap(Stack& other) noexcept {
using std::swap;
swap(m_top, other.m_top);
swap(m_size, other.m_size);
}
friend void swap(Stack& lhs, Stack& rhs) {
lhs.swap(rhs);
}
friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
Node* current = stack.m_top.get();
for(; current; current = current->prev.get()) {
os << "|" << current->data << "|n";
}
return os << "---n";
}
};
}
}
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
edited Mar 22 at 17:40
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
answered Mar 21 at 18:53
Martin YorkMartin York
74.1k488272
74.1k488272
1
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote usingstd::unique_ptrin favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.
$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're usingswap(m_top, other.m_top);over theunique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this callnew Node(data, std::move(m_top)in mypush_backfunction? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?
$endgroup$
– greg
Mar 21 at 19:34
1
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to usestd::moveinside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by usingstd::move.
$endgroup$
– Martin York
Mar 21 at 20:04
1
$begingroup$
@greg The rule of zero is why you don't need destructors. Thestd::unique_ptrdestructor will automatically be called and release its resources. You doing it manually is not required.
$endgroup$
– Martin York
Mar 21 at 20:05
1
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
|
show 7 more comments
1
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote usingstd::unique_ptrin favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.
$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're usingswap(m_top, other.m_top);over theunique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this callnew Node(data, std::move(m_top)in mypush_backfunction? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?
$endgroup$
– greg
Mar 21 at 19:34
1
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to usestd::moveinside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by usingstd::move.
$endgroup$
– Martin York
Mar 21 at 20:04
1
$begingroup$
@greg The rule of zero is why you don't need destructors. Thestd::unique_ptrdestructor will automatically be called and release its resources. You doing it manually is not required.
$endgroup$
– Martin York
Mar 21 at 20:05
1
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
1
1
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote using
std::unique_ptr in favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Just curious, independent of whether a redoing a list here is a good solution or not. These days I would promote using
std::unique_ptr in favor over raw pointers. Is there a case to be made against the use of one over the other ? This is not meant as flame bait, we all make technical decisions and this one still seems to have people a little bit puzzled.$endgroup$
– Harald Scheirich
Mar 21 at 19:16
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're using
swap(m_top, other.m_top); over the unique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this call new Node(data, std::move(m_top) in my push_back function? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?$endgroup$
– greg
Mar 21 at 19:34
$begingroup$
Thanks I've modified my code! In your swap is there a reason you're using
swap(m_top, other.m_top); over the unique_ptr<...>::swap? In my Node constructor I am calling move internally, do I need to still need to have this call new Node(data, std::move(m_top) in my push_back function? I can not seem to get this new implementation to work with move used as a function parameter. Why do I not need my destructors?$endgroup$
– greg
Mar 21 at 19:34
1
1
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to use
std::move inside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by using std::move.$endgroup$
– Martin York
Mar 21 at 20:04
$begingroup$
@greg In the constructor. I would use std::move to pass the m_top into the constructor. But this is because I would also make the underlying node take an r-value reference. Yes you still need to use
std::move inside the constructor because even though the parameter is bound as an r-value reference a named value itself is not an r-value reference and must be made one by using std::move.$endgroup$
– Martin York
Mar 21 at 20:04
1
1
$begingroup$
@greg The rule of zero is why you don't need destructors. The
std::unique_ptr destructor will automatically be called and release its resources. You doing it manually is not required.$endgroup$
– Martin York
Mar 21 at 20:05
$begingroup$
@greg The rule of zero is why you don't need destructors. The
std::unique_ptr destructor will automatically be called and release its resources. You doing it manually is not required.$endgroup$
– Martin York
Mar 21 at 20:05
1
1
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
$begingroup$
@greg Update to show how I would do it (so you can see everything in context).
$endgroup$
– Martin York
Mar 21 at 20:38
|
show 7 more comments
$begingroup$
swapdoes not swap sizes.If
pop_backthrows on empty stack,topshall also throw.
I see no reason for an
operator<<to build a string.
os << '|' << std::to_string(current->data()) << '|n';
in a loop achieves the same result.
I would also consider letting
Nodeto output itself withNode::operator<<.
answered Mar 21 at 18:32
vnpvnp
40.5k233103
$endgroup$
add a comment |
$begingroup$
swapdoes not swap sizes.If
pop_backthrows on empty stack,topshall also throw.
I see no reason for an
operator<<to build a string.
os << '|' << std::to_string(current->data()) << '|n';
in a loop achieves the same result.
I would also consider letting
Nodeto output itself withNode::operator<<.
answered Mar 21 at 18:32
vnpvnp
40.5k233103
$endgroup$
add a comment |
$begingroup$
swapdoes not swap sizes.If
pop_backthrows on empty stack,topshall also throw.
I see no reason for an
operator<<to build a string.
os << '|' << std::to_string(current->data()) << '|n';
in a loop achieves the same result.
I would also consider letting
Nodeto output itself withNode::operator<<.
answered Mar 21 at 18:32
vnpvnp
40.5k233103
$endgroup$
swapdoes not swap sizes.If
pop_backthrows on empty stack,topshall also throw.
I see no reason for an
operator<<to build a string.
os << '|' << std::to_string(current->data()) << '|n';
in a loop achieves the same result.
I would also consider letting
Nodeto output itself withNode::operator<<.
answered Mar 21 at 18:32
vnpvnp
40.5k233103
answered Mar 21 at 18:32
vnpvnp
40.5k233103
answered Mar 21 at 18:32
vnpvnp
40.5k233103
answered Mar 21 at 18:32
vnpvnp
40.5k233103
40.5k233103
add a comment |
add a comment |
$begingroup$
class Node {
private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
Since Node is an implementation detail of Stack, you don't need to hide Nodes members data and previous from Stack. Consider using aggregate initialization so that members can be directly manipulated.
~Node() { m_previous.reset(); }
Since the destructor isn't doing anything after std::unique_ptr<T>::reset(), it's equivalent to letting the class call the destructor of your std::unique_ptr<Node> member.
~Node() { }
Now, you have chained your pointers such that the current node is the owner of the previous node which owns the previous node and so on. When we call the destructor, this is essentially what is happening
m_previous.reset() calls
🡒 m_previous->~Node()
🡒 m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->m_previous->~Node()
🡒 and so on
And it's correct in that each node gets cleaned up and all the cleanup happens automatically. Unfortunately, it's also recursive which means its bounded by the stack (memory) depth. To fix this, you'll need to iteratively remove elements.
Whenever you define any of the special member functions (destructor, copy/move constructor, copy/move assignment), you should consider whether your class needs the others. This is commonly known as the rule of five. By providing the destructor, the move operations are not declared. Normally, the copy operations are defaulted, but std::unique_ptr as a data member results in those being implicitly deleted. You'll need to implement the copy and move operations if your stack is to have those value semantics. The general guideline is that if you explicitly declare any of the special member functions, then explicitly declare all of the special member functions and explicitly =default (opt into the implicit behavior), =delete (opt out of the implicit behavior), or user-define each of them.
const int data() { return m_data; }
const as a qualifier on the return type is ignored here.
class Stack {
...
public:
~Stack() { m_top.reset(); }
Same issues as node, from recursive destruction to missing copy/move operations.
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
Avoid new and prefer std::make_unique to make std::unique_ptrs. It cuts down on the duplication and enforces consistency when you need safety in more complex initialization sequences.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Don't use else after language constructs that interrupts control flow (return, break, continue, goto).
int top() {
return m_top.get()->data();
}
Be consistent with the naming. If directionality matters to you, then back() would be consistent with push_back() and pop_back(). top() would go better with functions like push(), and pop().
Be consistent with your exception handling. If you throw on an empty stack pop_back(), then you should throw on an empty stack top().
In order to modify the top value, the user has to pop (deallocate) and push (allocate). Consider allowing the user to access the top element by reference and modify the element in place.
bool empty() {
return (m_size == 0) ? true : false;
}
m_size == 0 will return a boolean that maps to the same exact values in your ternary. The compiler knows that and optimizes it for you, but you could help readers and just do it yourself.
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
You forgot to swap the size.
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
stack is passed in as a reference. operator<< doesn't modify the contents of stack and can be qualified with const.
You don't have to convert data (int) to a std::string to stream into a std::ostream. There is already an overload that does this for you.
Do you even need operator<<()? A stack is a last in-first out container. Inspection only exists on the latest element pushed on the stack that hasn't been popped. This function also requires the inclusion of <iostream>. A static constructor is transparently injected into every translation unit that includes this header, whether IOStreams are used or not in the user application.
Overall, you should read up on const-correctness and noexcept specification. As for the design of your stack, I would consider splitting the management of the nodes (forward_list?) from the interface of stack, which could be adapted over an existing sequence interface.
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
$endgroup$
add a comment |
$begingroup$
class Node {
private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
Since Node is an implementation detail of Stack, you don't need to hide Nodes members data and previous from Stack. Consider using aggregate initialization so that members can be directly manipulated.
~Node() { m_previous.reset(); }
Since the destructor isn't doing anything after std::unique_ptr<T>::reset(), it's equivalent to letting the class call the destructor of your std::unique_ptr<Node> member.
~Node() { }
Now, you have chained your pointers such that the current node is the owner of the previous node which owns the previous node and so on. When we call the destructor, this is essentially what is happening
m_previous.reset() calls
🡒 m_previous->~Node()
🡒 m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->m_previous->~Node()
🡒 and so on
And it's correct in that each node gets cleaned up and all the cleanup happens automatically. Unfortunately, it's also recursive which means its bounded by the stack (memory) depth. To fix this, you'll need to iteratively remove elements.
Whenever you define any of the special member functions (destructor, copy/move constructor, copy/move assignment), you should consider whether your class needs the others. This is commonly known as the rule of five. By providing the destructor, the move operations are not declared. Normally, the copy operations are defaulted, but std::unique_ptr as a data member results in those being implicitly deleted. You'll need to implement the copy and move operations if your stack is to have those value semantics. The general guideline is that if you explicitly declare any of the special member functions, then explicitly declare all of the special member functions and explicitly =default (opt into the implicit behavior), =delete (opt out of the implicit behavior), or user-define each of them.
const int data() { return m_data; }
const as a qualifier on the return type is ignored here.
class Stack {
...
public:
~Stack() { m_top.reset(); }
Same issues as node, from recursive destruction to missing copy/move operations.
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
Avoid new and prefer std::make_unique to make std::unique_ptrs. It cuts down on the duplication and enforces consistency when you need safety in more complex initialization sequences.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Don't use else after language constructs that interrupts control flow (return, break, continue, goto).
int top() {
return m_top.get()->data();
}
Be consistent with the naming. If directionality matters to you, then back() would be consistent with push_back() and pop_back(). top() would go better with functions like push(), and pop().
Be consistent with your exception handling. If you throw on an empty stack pop_back(), then you should throw on an empty stack top().
In order to modify the top value, the user has to pop (deallocate) and push (allocate). Consider allowing the user to access the top element by reference and modify the element in place.
bool empty() {
return (m_size == 0) ? true : false;
}
m_size == 0 will return a boolean that maps to the same exact values in your ternary. The compiler knows that and optimizes it for you, but you could help readers and just do it yourself.
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
You forgot to swap the size.
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
stack is passed in as a reference. operator<< doesn't modify the contents of stack and can be qualified with const.
You don't have to convert data (int) to a std::string to stream into a std::ostream. There is already an overload that does this for you.
Do you even need operator<<()? A stack is a last in-first out container. Inspection only exists on the latest element pushed on the stack that hasn't been popped. This function also requires the inclusion of <iostream>. A static constructor is transparently injected into every translation unit that includes this header, whether IOStreams are used or not in the user application.
Overall, you should read up on const-correctness and noexcept specification. As for the design of your stack, I would consider splitting the management of the nodes (forward_list?) from the interface of stack, which could be adapted over an existing sequence interface.
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
$endgroup$
add a comment |
$begingroup$
class Node {
private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
Since Node is an implementation detail of Stack, you don't need to hide Nodes members data and previous from Stack. Consider using aggregate initialization so that members can be directly manipulated.
~Node() { m_previous.reset(); }
Since the destructor isn't doing anything after std::unique_ptr<T>::reset(), it's equivalent to letting the class call the destructor of your std::unique_ptr<Node> member.
~Node() { }
Now, you have chained your pointers such that the current node is the owner of the previous node which owns the previous node and so on. When we call the destructor, this is essentially what is happening
m_previous.reset() calls
🡒 m_previous->~Node()
🡒 m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->m_previous->~Node()
🡒 and so on
And it's correct in that each node gets cleaned up and all the cleanup happens automatically. Unfortunately, it's also recursive which means its bounded by the stack (memory) depth. To fix this, you'll need to iteratively remove elements.
Whenever you define any of the special member functions (destructor, copy/move constructor, copy/move assignment), you should consider whether your class needs the others. This is commonly known as the rule of five. By providing the destructor, the move operations are not declared. Normally, the copy operations are defaulted, but std::unique_ptr as a data member results in those being implicitly deleted. You'll need to implement the copy and move operations if your stack is to have those value semantics. The general guideline is that if you explicitly declare any of the special member functions, then explicitly declare all of the special member functions and explicitly =default (opt into the implicit behavior), =delete (opt out of the implicit behavior), or user-define each of them.
const int data() { return m_data; }
const as a qualifier on the return type is ignored here.
class Stack {
...
public:
~Stack() { m_top.reset(); }
Same issues as node, from recursive destruction to missing copy/move operations.
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
Avoid new and prefer std::make_unique to make std::unique_ptrs. It cuts down on the duplication and enforces consistency when you need safety in more complex initialization sequences.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Don't use else after language constructs that interrupts control flow (return, break, continue, goto).
int top() {
return m_top.get()->data();
}
Be consistent with the naming. If directionality matters to you, then back() would be consistent with push_back() and pop_back(). top() would go better with functions like push(), and pop().
Be consistent with your exception handling. If you throw on an empty stack pop_back(), then you should throw on an empty stack top().
In order to modify the top value, the user has to pop (deallocate) and push (allocate). Consider allowing the user to access the top element by reference and modify the element in place.
bool empty() {
return (m_size == 0) ? true : false;
}
m_size == 0 will return a boolean that maps to the same exact values in your ternary. The compiler knows that and optimizes it for you, but you could help readers and just do it yourself.
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
You forgot to swap the size.
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
stack is passed in as a reference. operator<< doesn't modify the contents of stack and can be qualified with const.
You don't have to convert data (int) to a std::string to stream into a std::ostream. There is already an overload that does this for you.
Do you even need operator<<()? A stack is a last in-first out container. Inspection only exists on the latest element pushed on the stack that hasn't been popped. This function also requires the inclusion of <iostream>. A static constructor is transparently injected into every translation unit that includes this header, whether IOStreams are used or not in the user application.
Overall, you should read up on const-correctness and noexcept specification. As for the design of your stack, I would consider splitting the management of the nodes (forward_list?) from the interface of stack, which could be adapted over an existing sequence interface.
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
$endgroup$
class Node {
private:
int m_data;
std::unique_ptr<Node> m_previous;
public:
Node(int data, std::unique_ptr<Node>& previous) {
m_data = data;
m_previous = std::move(previous);
}
Since Node is an implementation detail of Stack, you don't need to hide Nodes members data and previous from Stack. Consider using aggregate initialization so that members can be directly manipulated.
~Node() { m_previous.reset(); }
Since the destructor isn't doing anything after std::unique_ptr<T>::reset(), it's equivalent to letting the class call the destructor of your std::unique_ptr<Node> member.
~Node() { }
Now, you have chained your pointers such that the current node is the owner of the previous node which owns the previous node and so on. When we call the destructor, this is essentially what is happening
m_previous.reset() calls
🡒 m_previous->~Node()
🡒 m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->m_previous->~Node()
🡒 and so on
And it's correct in that each node gets cleaned up and all the cleanup happens automatically. Unfortunately, it's also recursive which means its bounded by the stack (memory) depth. To fix this, you'll need to iteratively remove elements.
Whenever you define any of the special member functions (destructor, copy/move constructor, copy/move assignment), you should consider whether your class needs the others. This is commonly known as the rule of five. By providing the destructor, the move operations are not declared. Normally, the copy operations are defaulted, but std::unique_ptr as a data member results in those being implicitly deleted. You'll need to implement the copy and move operations if your stack is to have those value semantics. The general guideline is that if you explicitly declare any of the special member functions, then explicitly declare all of the special member functions and explicitly =default (opt into the implicit behavior), =delete (opt out of the implicit behavior), or user-define each of them.
const int data() { return m_data; }
const as a qualifier on the return type is ignored here.
class Stack {
...
public:
~Stack() { m_top.reset(); }
Same issues as node, from recursive destruction to missing copy/move operations.
void push_back(int data) {
m_top = std::unique_ptr<Node>(new Node(data, m_top));
++m_size;
}
Avoid new and prefer std::make_unique to make std::unique_ptrs. It cuts down on the duplication and enforces consistency when you need safety in more complex initialization sequences.
void pop_back() {
if(!m_top) {
throw std::out_of_range("ERROR: Can not pop. Stack empty.");
}
else {
m_top = std::move(m_top->previous());
--m_size;
}
}
Don't use else after language constructs that interrupts control flow (return, break, continue, goto).
int top() {
return m_top.get()->data();
}
Be consistent with the naming. If directionality matters to you, then back() would be consistent with push_back() and pop_back(). top() would go better with functions like push(), and pop().
Be consistent with your exception handling. If you throw on an empty stack pop_back(), then you should throw on an empty stack top().
In order to modify the top value, the user has to pop (deallocate) and push (allocate). Consider allowing the user to access the top element by reference and modify the element in place.
bool empty() {
return (m_size == 0) ? true : false;
}
m_size == 0 will return a boolean that maps to the same exact values in your ternary. The compiler knows that and optimizes it for you, but you could help readers and just do it yourself.
void swap(Stack& other_stack) {
m_top.swap(other_stack.m_top);
// Node* other_top = other_stack.m_top.release();
// other_stack.m_top = std::move(m_top);
// m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
}
You forgot to swap the size.
friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
std::string stack_string = "";
Node* current = stack.m_top.get();
for(; current; current = current->previous().get()) {
stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + 'n';
}
os << stack_string;
os << "---n";
return os;
}
stack is passed in as a reference. operator<< doesn't modify the contents of stack and can be qualified with const.
You don't have to convert data (int) to a std::string to stream into a std::ostream. There is already an overload that does this for you.
Do you even need operator<<()? A stack is a last in-first out container. Inspection only exists on the latest element pushed on the stack that hasn't been popped. This function also requires the inclusion of <iostream>. A static constructor is transparently injected into every translation unit that includes this header, whether IOStreams are used or not in the user application.
Overall, you should read up on const-correctness and noexcept specification. As for the design of your stack, I would consider splitting the management of the nodes (forward_list?) from the interface of stack, which could be adapted over an existing sequence interface.
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
edited Mar 22 at 4:36
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
answered Mar 22 at 4:30
SnowhawkSnowhawk
5,55611229
5,55611229
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215944%2fstack-interview-code-methods-made-from-class-node-and-smart-pointers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
As a quick comment: one thing you should try to pay more attention to is const correctness. Again, there are many member functions that should be const. If the function does not modify the object contents, make it const.
$endgroup$
– Juho
Mar 21 at 18:30