8
\$\begingroup\$

I'm fairly new to C++ programming. To help I've been writing my own data structures for practice. I'd liked this to be judged as if it was written by a professional, and receive honest feedback. I already have a few concerns.

  1. Am I managing memory correctly? I don't believe I have any leaks. A lot of advice I get when using pointers is to use smart pointers, but raw pointers are fine when the class encapsulates all pointers correct?

  2. I'm unhappy my << operator overload has to call to peekAll inside the class. I feel like I'm going about this in the wrong way. Aside from that should I overload any other operators? I didn't feel arithmetic operators made much sense.

#include <ostream>

template <typename T>
class BBStack {
public:
BBStack(T type) {
    head = new Node(type);
}

virtual ~ BBStack() {
    Node* temp = head;
    while (head != nullptr) {
        temp = head->next;
        delete head;
        head = temp;
    }
    delete temp;
}

void push(T type) {
    Node *newNode = new Node(type, head);
    head = newNode;
}

T peek() const {
    return head->data;
}

T pop() {
    if (head == nullptr) {
        std::cout<<"Error stack is empty"<<std::endl;
        return NULL;
    } else {
        Node *temp = head;
        T result = temp->data;
        head = head->next;
        delete temp;
        return result;
    }
}

std::ostream& peekAll(std::ostream& out) const {
    if (head == nullptr) return out << "Stack is empty";
    Node* temp = head;

    while (temp != nullptr) {
        out << temp->data << " ";
        temp = temp->next;
    }

    delete temp;
    return out;
}

private:
    struct Node {
        Node(T type, Node* _next = nullptr) : data(type), next(_next) {}
        Node(Node* node) : data (node->data), next (node->next) {}

        T data;
        Node* next;
    };
    Node* head;

};

template <typename T>
std::ostream& operator<< (std::ostream& out, const BBStack<T>& stack) {
    return stack.peekAll(out);
}
\$\endgroup\$
5
\$\begingroup\$

In addition to MAG's answer, a couple of points.

You're missing something related to memory management: what happens if someone copies one of your stacks as in:

BBStack<int> s1(1);   
BBStack<int> s2 = s1;
s1.pop();
s2.pop(); // <- What happens here?

Since you didn't provide a copy constructor (or copy-assignment operator), s2's head will will point to the same object as s1's head when it is constructed. The pop() on s1 will destroy that object, but won't magically make s2's pointer null. So the pop() on s2 will access a deleted object, which is undefined behavior. See the Rule of Three for more info on this sort of problems.

To fix it, either provide a copy constructor and copy-assignment operator (and move variants), or make your class non-copyable.


Please provide a constructor that doesn't take an value to push. It is not unusual at all to have to build an empty stack, and fill it in later. Not having one makes your class much less useful.

BBStack() : head{nullptr} {}

And the constructor you have taking a T should probably be marked explicit, because you usually don't want the following to compile:

BBStack<int> s{42};
s = 42;

So:

BBStack() : head{nullptr} {}
explicit BBStack(T type) : head{new Node(type)} {}

A suggestion for your peekAll: replace it with something more generic that traverses the list and calls a caller-provided function on each element.

Example:

#include <functional>

// ...

  void inspect(std::function<void(T const&)>  f) const
  {
    Node *temp = head;
    while (temp != nullptr) {
      f(temp->data);
      temp = temp->next;
    }
  }

// ...

With this, you can implement your output operator with:

template <typename T>
std::ostream &operator<<(std::ostream &out, const BBStack<T> &stack)
{
  stack.inspect([&out](T const &data) { out << data << " "; });
  out << std::endl;
  return out;
}

This allows your users to implement a lot of stuff without touching your code (sum, average, depth, etc.).

\$\endgroup\$
5
\$\begingroup\$

Ownership

Yes raw pointers are fine if you are not transferring ownership (Is the class responsibility to delete them).

Pop function

Also I am not sure if this will compile for any data other than pointers and types convertible to 0 since you return NULL. (Also is better to use nullptr consistently).

 T pop() {
    if (head == nullptr) {
        std::cout<<"Error stack is empty"<<std::endl;
        return NULL;
    } else {
        Node *temp = head;
        T result = temp->data;
        head = head->next;
        delete temp;
        return result;
    }
}

IMO it will be better to throw a underflow exception since is the client responsibility to check that is not empty before. Also avoid returning the data since we will be throwing an exception (For more info on this check out this article http://ptgmedia.pearsoncmg.com/images/020163371x/supplements/Exception_Handling_Article.html)

 void pop() {
    if (head == nullptr) 
        throw std::underflow_error("underflow");

    Node *temp = head;
    head = head->next;
    delete temp;   
 }

So the client will have to call peek before pop to get the same effect.

Parameters:

In most parameter like this (T type) you should change it to (const T& type) to avoid copying. Even better would be to provide an overload for rvalue references like this (T&&)

peekAll function

This function seams kind of weird. Why are you deleting temp? . It seams that after the while loop temp should always be nullptr. And aren't you just writing the stack on the stream. I would just omit this function and move it to the << operator overload.

Also you should implement an empty function.

\$\endgroup\$
2
\$\begingroup\$

In a professional setting, the advice would be: "scrap this entire code and use std::stack<T>".

But suppose std::stack<T> didn't exist in the Standard Library, or suppose you wanted to write some other container-like entity not yet invented. The professional advice would then be: "try and leverage as much existing code as possible". E.g. implement std::stack<T> in terms of an existing container such as std::list<T>, std::vector<T> or std::deque<T>.

This would automatically remove all the memory management issues from your consideration. In professional code, unless carefully documented why it would be absolutely necessary, I wouldn't expect to see raw new or delete, and instead to see either unique_ptr and make_unique or memory managing containers like std::vector or std::string.

BTW, this is also how the Standard Library implements std::stack<T> because it is a container adaptor and not a container. The precise class template is:

template<
    class T,
    class Container = std::deque<T>
> class stack;

It's a good exercise to implement the stack member functions emplace(), push() and pop() in terms of the emplace_back(), push_back() and pop_back() of the underlying container. It's still not entirely trivial, because you have to be careful about perfect forwarding and move semantics. The linked documentation should provide you with enough hints to comlete this.

Note that std::stack does not provide an operator<< and neither does it provide iterators to view its elements. It does however have a protected member c that gives access to the underlying container. You can then write an adaptor that uses the container iterators to show the underlying elements:

#include <iostream>
#include <iterator>
#include <stack>
#include <vector>

template<class Adaptor>
struct container_view
:
    public Adaptor
{
    container_view() = default;
    using Adaptor::Adaptor;
    auto begin() const { return this->c.begin(); }
    auto end() const { return this->c.end(); }
};

int main()
{
    std::vector<int> v = { 1, 2, 3, 4 };
    container_view<std::stack<int, std::vector<int>>> const c(v);
    std::copy(begin(c), end(c), std::ostream_iterator<int>(std::cout, ","));
}

Live Example.

Note that his adaptor also works for the two other Standard Library container adaptors std::priority_queue and std::queue.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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