Which smart pointer to use in Stack implementation?

Question

From what I've understood correctly:

scoped_ptr: no overhead, cannot be copied or moved.

unique_ptr: no overhead, cannot be copied, can be moved.

shared_ptr: some overhead (reference counting), can be copied.

Having said that, if there is a need for several owners, then shared_ptr should be used.

Now, in this program below which is a simple implementation of stack in C++. I don't understand which type of smart pointer should be used.

The reason I'm asking this question because both unique_ptr as well as shared_ptr cannot be copied and that is exactly what I'm doing in this implementation of simple stack. I've commented out //HERE in the program where I'm using C++ pointers and if you read the program properly you'll see how the data is getting copied in pretty much all the functions.

GameStateStack.h

#ifndef _H_GAMESTATE_
#define _H_GAMESTATE_

#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/scoped_ptr.hpp>
#include <memory>

class node
{
public:
    std::string gameState;
    node * nextGameState;    // HERE
};

class GameStateStack
{
private:
    node * _topState;    // HERE
    void Destory();

public:
    int gameStatesCount;
    void PushGameState(std::string element);
    void PopGameState();
    std::string CurrentGameState();
    GameStateStack();
    ~GameStateStack();
};

extern GameStateStack state;

#endif

GameStateStack.cpp

#include <iostream>
#include <stdlib.h>
#include <string>
#include <boost/scoped_ptr.hpp>
#include <boost/shared_ptr.hpp>
#include <memory>
#include "GameStateStack.h"
#include "template.h"

GameStateStack state;

GameStateStack::GameStateStack()
{
    _topState = NULL;
    gameStatesCount = 0;
}

GameStateStack::~GameStateStack()
{

}

void GameStateStack::PushGameState(std::string gameStateName)
{
    node *newTopState = new node;  // HERE
    if (_topState == NULL)
    {
        newTopState->gameState = gameStateName;
        newTopState->nextGameState = NULL;
        _topState = newTopState;
        gameStatesCount++;
    }

    else
    {
        newTopState->gameState = gameStateName;
        newTopState->nextGameState = _topState;
        _topState = newTopState;
        gameStatesCount++;
    }
}

void GameStateStack::PopGameState()
{
    if (_topState == NULL)
        std::cout << "Error: no gamestates available to pop";
    else
    {
        node * old = _topState;  // HERE
        _topState = _topState->nextGameState;
        delete(old);
        gameStatesCount--;
    }
}

std::string GameStateStack::CurrentGameState()
{
    node *temp;    // HERE
    temp = _topState;
    return temp->gameState;
}

void GameStateStack::Destory()
{
    node *abc;    // HERE
    delete _topState;
    delete abc->nextGameState;
}

Galik · Accepted Answer · 2015-06-01T07:58:02.387

Here is how your stack could be implemented using a std::unique_ptr. Note the use of std::move() to re-assign the std::unique_ptr leaving the original pointing at nothing.

Also, instead of if(topState == NULL) I have used the more idiomatic if(topState). A std::unique_ptr returns true if it points somewhere or false if it does not.

Also standard C++ dictates that we should not begin variable names with a leading _.

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

struct node
{
    std::string gameState;
    std::unique_ptr<node> nextGameState;

    ~node()
    {
        std::cout << "deleting: " << gameState << '\n';
    }
};

class GameStateStack
{
    // should not use _ to begin variable names in std C++
    std::unique_ptr<node> topState;
    int gameStatesCount;

public:
    GameStateStack();
    void PushGameState(std::string gameStateName);
    void PopGameState();
    std::string CurrentGameState();
    void Destory();
};

GameStateStack::GameStateStack()
: gameStatesCount(0) // initialize here
{
    //topState = NULL; // no need to initialize unique_ptr
    //gameStatesCount = 0; // not here
}

void GameStateStack::PushGameState(std::string gameStateName)
{
    std::unique_ptr<node> newTopState(new node);
    newTopState->gameState = gameStateName;

    newTopState->nextGameState = std::move(topState);
    topState = std::move(newTopState);

    gameStatesCount++;
}

void GameStateStack::PopGameState()
{
    if(!topState)
        std::cout << "Error: no gamestates available to pop";
    else
    {
        topState = std::move(topState->nextGameState);
        gameStatesCount--;
    }
}

std::string GameStateStack::CurrentGameState()
{
    if(topState)
        return topState->gameState;
    return "error: nothing on stack"; // error
}

void GameStateStack::Destory()
{
    // deleting topState will first destroy the pointed to
    // node's own unique_ptr<node> nextGameState
    // which in turn will first delete its own nextGameState etc...
    topState.reset();
}

int main()
{
    GameStateStack stack;

    std::cout << "\ndestroy test" << '\n';

    stack.PushGameState("a");
    stack.PushGameState("b");
    stack.PushGameState("c");
    stack.PushGameState("d");
    stack.PushGameState("e");
    stack.PushGameState("f");

    stack.Destory();

    std::cout << "\npush-pop test" << '\n';

    stack.PushGameState("a");
    stack.PushGameState("b");
    stack.PushGameState("c");

    std::cout << stack.CurrentGameState() << '\n';

    stack.PopGameState();

    stack.PushGameState("d");
    stack.PushGameState("e");

    std::cout << stack.CurrentGameState() << '\n';

    stack.PopGameState();

    std::cout << stack.CurrentGameState() << '\n';

    stack.PopGameState();

    std::cout << stack.CurrentGameState() << '\n';

    stack.PopGameState();

    std::cout << stack.CurrentGameState() << '\n';

    stack.PopGameState();

    std::cout << stack.CurrentGameState() << '\n';

    stack.PopGameState();
}

This works so well! Thank you so much. I've learned a lot and now I can use the same concept in other implementations! about not beginning variable names with a leading _ I've been using it for private members as mentioned here: http://stackoverflow.com/questions/3136594/naming-convention-underscore-in-c-c-variables — Daqs, Jun 01 '15 at 08:26
at the same time I can also see the backdrops of using underscores. I'll make the necessary changes. Thanks! — Daqs, Jun 01 '15 at 08:28
Other acceptable conventions to use for identifying member variables would be a `m_variable` prefix a `myVariable` prefix or a `variable_` suffix. Also I'm not sure why you are taking a `std::string` by value and then assigning it when a const reference would be better. — sjdowling, Jun 01 '15 at 08:35
@sjdowling I am just keeping the code as close to the original as possible focusing on `std::unique_ptr` usage. — Galik, Jun 01 '15 at 08:50

score 0 · Answer 2 · answered Jun 01 '15 at 02:26

0

Here an unique_ptr is perfectly fine, especially if you return the CurrentGameState by value as you are doing.

Your top should be a unique_ptr<node>& but since there will be no state at the beginning you could use a std::reference_wrapper to wrap it.

Of course if you plan to return a game state by reference or pointer things will change, because popping a state would invalidate the contained state (unless it's dynamically allocated and then set).

answered Jun 01 '15 at 02:26

Jack

131,802
30
241
343

Thanks for the reply. When you say top, what exactly are you referring it? – Daqs Jun 01 '15 at 02:45
The top node is (uniquely) owned by the `GameStateStack` so a `unique_ptr` seems appropriate. Why do you think it should be a reference? – Chris Drew Jun 01 '15 at 07:46

Which smart pointer to use in Stack implementation?

2 Answers2