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;
}

• πάντα ῥεῖ: I've got some serious doubts your peek() function even compiles when it's used. NULL is unlikely to be convertible to T (e.g. when T is int or std::string).
• Richard Hodges: implementation in terms of shared_ptr implies the "shared handle" idiom. Is this the behaviour you want? If so, you might want to rename the class "shared_queue". Then you might want to consider simultaneous access by multiple threads. Having done that, you might conclude that this is a bad idea.
• user49428: @RichardHodges the shared implementation was done in order to make the multiple pointers be able to cope with the _first and _last node. This was purely an exercise on data structures, without worrying about concurrency. I'll try to think about possible implementations for multiple threads!
• user49428: @πάνταῥεῖ actually I used NULL exactly because I was doing a main() with T as int. If that is the case, nullptr cannot be used b/c the compiler cannot convert nullptr to const int
• πάντα ῥεῖ: @user49428 As mentioned when you use some class T that cannot be constructed with a 0 argument, that function will fail to compile.

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).

• Richard Hodges: "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." - what? The rules are very simple. Don't do it in the global namespace. The use of leading underscore to denote member variables is as good as trailing underscore, leading m_ or any other scheme. Code reviews should be solely about correctness and clarity, not personal styling preferences.
• πάντα ῥεῖ: @Richard I think leading underscore rules are a bit more than stylistic preference. IIRC it's explicitly preserved for use in C++ standard implementations.
• Richard Hodges: @πάνταῥεῖ firstly, stylistic preferences have no place in code reviews, which are there to detect logic errors, premature pessimisation and unclear code. Secondly, the c++ standard rules out underscore_prefixed names and types in the global namespace. Nowhere else.
• user49428: @LokiAstari Thanks a lot for your tips, I'll try to make a number of fixes and add them to the implementation! ;-)
• Loki Astari: @RichardHodges: As I said they are more complex than you think. Even you got it wrong (and I bet you think you know). See: What are the rules about using an underscore in a C++ identifier? Code review should be about training people to avoid habits that can cause issues. Leading underscore is a bad habit that should definitely be avoided as there are situations that it will cause you issues without you actually knowing. Especially because most people don't know the rules.