2
\$\begingroup\$

I'm currently working on implementing overloaded operators for simplifying pop() and push() operations. Check out the //how can avoid this? comments. I've had some troubles understanding how to return a certain value without causing memory leaks due to unassigned free space: so far the only dirty and inelegant idea I've had was to create a temporary empty value of T type, so in case the top pointer contained nullptr I could return this empty value.

But how can I avoid this? Or is this actually necessary in a template type for a function with return statements?

#include <iostream>
#include <memory>
#include <string>
#include <vector>

template <typename V> using ptr = std::shared_ptr<V>;

template <typename T>
class Stack
{
private:

    class Node
    {
    private:

        T data;
        ptr<Node> next;

    public:
        Node(T _data):data{_data}, next{} {}
        T getData(){
            return data;
        }

        ptr<Node>& getNext(){
            return this->next;
        }

    };

    ptr<Node> top;

public:

    Stack() : top{} {}
    Stack(const std::shared_ptr<std::vector<T>>& vec) : top{} {
        for (auto vElement : *vec){
            push(vElement);
        }
    }

    void push(T _data){
        auto _tmp = std::make_shared<Node>(_data);
        if(top!= nullptr){
            _tmp->getNext() = top;
        }
        top = _tmp;
    }


    T pop(){

        T forSafety{}; //how can I avoid this?
        if(isEmpty()) return forSafety;
        else {
            auto _tmp = top;
            top = top->getNext();
            return _tmp->getData();
        }
    }

    T peek(){

        T forSafety{}; //how can I avoid this?
        if(!isEmpty()){
            return top->getData();
        } else return forSafety;
    }

    bool isEmpty(){
        if(top==nullptr) return true;
        else return false;
    }

    void display(){
        auto _tmp = top;
        while(_tmp!=nullptr){
            std::cout << _tmp->getData() << std::endl;
            _tmp = _tmp->getNext();
        }
    }
};


int main(int argc, char** argv)
{
    std::shared_ptr<std::vector<std::string>> names{new std::vector<std::string>{"Julia","Bob","Angela","fSociety"}};
    auto s = std::make_shared<Stack<std::string>>(names);
    s->display();
    std::cout << s->peek() << std::endl;

    while(!s->isEmpty()){
        std::cout << "Popping -> " << s->pop() << std::endl;
    }

    s->display();
    s->peek();


    return 0;
}
\$\endgroup\$

migrated from stackoverflow.com Sep 10 '16 at 14:58

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ if(isEmpty()) return {}; Does the same thing, just more compactly written. \$\endgroup\$ – Igor Tandetnik Sep 1 '16 at 16:16
  • \$\begingroup\$ With your default constructor, you could explicitly set top to nullptr. \$\endgroup\$ – Arnav Borborah Sep 1 '16 at 16:19
  • \$\begingroup\$ @ArnavBorborah I've done that : Stack() : top{} {} \$\endgroup\$ – Oleg Nykolyn Sep 1 '16 at 16:24
  • \$\begingroup\$ Oh ok, I thought empty brackets didn't mean nullptr, @OlegNykolyn thanks for pointing that out \$\endgroup\$ – Arnav Borborah Sep 1 '16 at 16:25
  • \$\begingroup\$ @ArnavBorborah I've tested the constructor without the top {} and it caused a memory leak, so I guess empty braces for smart pointers cause them to be set to null. I'm no ENTIRELY sure of this though, someone else might correct me. \$\endgroup\$ – Oleg Nykolyn Sep 1 '16 at 16:27
1
\$\begingroup\$
template <typename V> using ptr = std::shared_ptr<V>;

Class specific details like aliases should be kept in the class or wrapped in a namespace to prevent global namespace pollution.

Why std::shared_ptr? std::shared_ptr is typically reserved for shared-ownership resource management and that has a cost associated to it. They are twice the size of a raw pointer as the std::shared_ptr object stores both the raw pointer to the resource and a raw pointer to the reference count. Reference counting must also be atomic to handle multiple reader/writers, resulting in slower increments and decrements. If you want to use a smart pointer, C++ provides std::unique_ptr for exclusive-resource management and should typically be the default smart pointer unless you need std::shared_ptr.


    class Node {
    // ...
    }

Node contains some payload data. We can read data through getData(). How do we write to data? Why return a copy of data? Since your Node class is an internal implementation detail that isn't used outside of your Stack, consider making Node an aggregate.

    struct Node {
        T data;
        ptr<Node> next;
    }

    Stack() : top{} {}

If your constructors are initializing data members with constant initialization values, explicitly initialize your data members using in-class initializers.

    ptr<Node> top{};        // default initializes top to nullptr
public:
    Stack() = default;      // don't suppress compiler generated def-ctor
    Stack(const std::shared_ptr<std::vector<T>>& vec) { 
        // ...
    }

    ptr<Node> top;
public:
    // omitted destructor

On destruction, smart pointers are great because they clean themselves up. Unfortunately, recursive destructions are not optimized. If you had a deep linear hierarchy of smart pointers, there is going to come a point where you overflow the stack due to too many destruction calls. If you used a smart pointer for a stack, you still need to implement a destructor which requires the rule of five. The rule of five says that if you provide any of the copy assignment/constructor, move assignment/constructor, or destructor special member functions, you must provide the others.


T pop() {
    T forSafety{}; //how can I avoid this?

The problem with returning from pop is what do you return? Returning by value is inefficient for expensive types. Your other option is to return by reference, but pop is a destructive operation that would result in returning a dangling pointer. A third option is to separate the concerns. Make pop a non-value returning function that simply removes the top element. peek already provides access to the top element.


T peek(){
    T forSafety{}; //how can I avoid this?
    if(!isEmpty()){
        return top->getData();
    } else return forSafety;
}

Member functions that inspect but do not mutate the object should be marked with a const suffix. Mutations can happen internally through direct access and externally through references, so marking functions as const (read-only) prevents mutation. Strive for const-correctness.

Return by value is inefficient and doesn't allow for external mutation of the value. As stated in the review of pop, you don't want to return a dangling pointer. The simplest solution is to delegate construction of a static variable to be referenced.

   T& peek() {
        if (top) {
            return top->getData();
        }
        return failed_range_check();
    }

    const T& peek() const {
        if (top) {
            return top->getData();
        }
        return failed_range_check();
    }

private:
    T& failed_range_check() {
        static T placeholder{};
        return placeholder;
    }

It works but it's still terrible. The callee has no idea an error occurred and the function returns a value that looks to be valid. A better solution is to use one of the many error handling techniques that already exist. The simplest is to throw an exception.

    T& peek() {
        return do_peek();
    }

    const T& peek() const {
        return do_peek();
    }

private:
    T& do_peek() {
        if (!top) {
            throw std::range_error("Stack<>::peek(): Cannot peek empty stack.");
        }
        return top->getData();
    }

Other options include using typesafe std::error_condition with containers like Alexandrescu's Expected<T>, variant<T>, or classic struct/std::tuple result types. If you don't care about the error type, you could use an optional<T>.


    if(top==nullptr) return true;
    else return false;

You don't have to explicitly compare to nullptr as the bool conversion for nullptr results in false.

4.12 Boolean conversions [conv.bool]

\$^1\$ A prvalue of arithmetic, unscoped enumeration, pointer, or pointer to member type can be converted to a prvalue of type bool. A zero value, null pointer value, or null member pointer value is converted to false; any other value is converted to true. For direct-initialization (8.5), a prvalue of type std::nullptr_t can be converted to a prvalue of type bool; the resulting value is false.

Continue to strive for const-correctness.

    bool isEmpty() const {
        return !top;
    }

void display(){
    auto _tmp = top;
    while(_tmp!=nullptr){
        std::cout << _tmp->getData() << std::endl;
        _tmp = _tmp->getNext();
    }
}

Stacks only provide access to the last element inserted, so a function that displays the content of the stack is unnecessary. If you need to verify data is being entered and stored correctly, use testing and a debugger.

Be aware that <iostream> statically initializes the standard streams (std::cin, std::cout, std::cerr). Rather than directly including <iostream> in headers and incurring the initialization costs on users. Consider including <iosfwd> and pass streams through referencing parameters.

Be aware that

std::cout << std::endl;

is equivalent to

std::cout << '\n' << std::flush;

The call to std::flush may have an effect on stream efficiency. Rather than researching which streams behave poorly with flushing, explicitly state your intent in code that you want a new line.

std::cout << '\n';                 // Explicit EOL char.
std::cout << std::flush;           // Explicit flush the stream.
std::cout << '\n' << std::flush;   // Explicit both

When there is an obvious loop variable, prefer for loops over while loops.

void display(std::ostream& out) {
    for( auto& curr = top; curr; curr = curr->next) {
        out << curr->getData() << '\n';
    }
}

int main(int argc, char** argv) {

main is a special function. The standard allows main to take 2 forms.

3.6.1 Main function [basic.start.main]

An implementation shall allow both

\$^{(2.1)}\$ — a function of () returning int and

\$^{(2.2)}\$ — a function of (int, pointer to pointer to char) returning int

If you do not plan to use the parameters, explicitly convey your intent by omitting them.

int main() {

std::shared_ptr<std::vector<std::string>> names{new std::vector<std::string>{"Julia","Bob","Angela","fSociety"}};
auto s = std::make_shared<Stack<std::string>>(names);

Don't use smart pointers or dynamic allocation when you do not need it.

auto names = std::vector<std::string>{"Julia","Bob","Angela","fSociety"};
auto s = Stack<std::string>(names);        // conv ctor needs to be updated
s.display();
// ...

How is this designed so far?

You are missing some basic methods.

  • std::size_t size() const;
  • T& emplace(Args...); (requires Node emplacement support)
  • void push(T&&);
  • void swap(T&);

As for design, applying the adaptor pattern would have been a much better choice. A stack provides specialized access (last-in, first-out) that can be mapped to an underlying container. push does an insert on one of the ends. top provides direct access to the same end. pop removes the element at that end. std::stack is designed this way. The underlying container could be any sequence container that provides the required interface (push_back, pop_back, back).

The best part of composing with an existing container class is that it naturally provides the rule of zero. Your adaptor class has nothing to do with ownership as it simply maps its interface on the underlying container.

\$\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.