Smart Pointers Queue Implementation

Question

To practice around with C++11 smart pointers I was trying to implement a simple Queue to go beyond a simple Linked List. The fact that the _first and _last nodes are pointed to twice at runtime made me decide to implement them as shared_ptr. I was wondering if this was the correct way to implement the data structure.

#include <iostream>
#include <memory>

template <class T>
class Queue
{
private:
    class Node
    {
    public:
        const T _data;
        std::shared_ptr<Node> _next;
        Node(const T& t) : _data{ t } {}
    };

    std::shared_ptr<Node> _first;
    std::shared_ptr<Node> _last;
    unsigned _size;
public:
    Queue() : _size{ 0 }, _first { nullptr }, _last{ nullptr } {}
    ~Queue() {}
    void add(const T& item);
    const T remove();
    const unsigned size();
    const T peek();
    bool isEmpty();
};

template <class T>
bool Queue<T>::isEmpty()
{
    return _first == nullptr;
}

template <class T>
void Queue<T>::add(const T& item)
{
    std::shared_ptr<Node> new_end = std::make_shared<Node>(item);
    if (_last)
    {
        _last->_next = new_end;
    }
    _last = new_end;
    if (!_first)
    {
        _first = _last;
    }
    ++_size;
}

template <class T>
const T Queue<T>::remove()
{
    if (_first == nullptr) return NULL;
    auto ptr = std::move(_first);
    _first = ptr->_next;
    if (!_first)
    {
        _last.reset();
    }
    T val = ptr->_data;
    ptr.reset();
    --_size;
    return val;
}

template <class T>
const unsigned Queue<T>::size()
{
    return _size;
}

template <class T>
const T Queue<T>::peek()
{
    if (_first) return _first->_data;

    return NULL;
}

Answer 1

Consistency

Always use the same technique when doing the same thing. Do use multiple ways to do the same thing.

You use nullptr in half your code and NULL in the other half. Be consistent and move to the modern nullptr.

Design

Not sure I agree with creating a container by using a smart pointer. These are both types of memory management. Using one to implement the other seems a bit counterproductive. But others have done it so why not.

Design Semantics

Your design does not do what I would expect on a copy.

Queue<int>  q1;
q1.add(1);
Queue<int>  q2(q1);
q1.add(2);


// In the case I would expect q2 to be a copy of q1 before we add 2.
// I would expect the two lists to be independent (If I wanted the
// to represent the same queue I would have used a reference).
// Your class both objects refer to the same underlying list. Thus
// at the end both lists have two elements in them.

Note: You basically relied on the rule of zero. When you need to implement the rule of five (three).

Rule of Zero: You don't do resource management because that is done by a resource class you use (in your case std::shared_ptr). The default constructors/assignment/destructors use the members versions automatically and thus save you from doing work.

Rule of Five: You override the default constructor/assignment/destructors to handle resource management and define the copy/move semantics of your class.

Leading Underscore.

Your use of leading underscore is technically fine. BUT the rules for using a leading underscore are more complex than most people know so prefer to avoid its use.

Also it looks ugly as hell. If you are trying to separate local variables from member variables a better technique is to give the variables obvious descriptive names.

Error:

const T Queue<T>::remove()
{
    if (_first == nullptr) return NULL;

This only works if the type T can be constructed by passing NULL (since NULL can be converted to 0 anything that takes an integer can also be constructed).

If you there is nothing to remove from the Queue then your code (that calls the Queue) has an error in it so in this case you should be throwing an exception of something along these lines.

Overkill

This is a lot of extra work:

T val = ptr->_data;
ptr.reset();
--_size;
return val;

You can replace this with:

--_size;
return ptr->_data;
// The destructor of ptr (which is a smart  pointer) will be called
// and tidy up the data and resources).