Comments:
I aim to have a deeper understanding of templates in C++
Good example to use to develop these skills:
I aim to make it look and feel close to the standard library's implementation in terms of memory usage, speed and readability.
That will be harder. You have the same characteristics as std::list while the standard version std::queue uses a std::deque as the underlying container that has very different characteristcs.
See this question for the differences: What are the complexity guarantees of the standard containers?
The standard library performance was twice as better as mine. What may be reasons?
Though they will look very similar. The technique of creating a new node dynamically for every push (std::list) is relatively expensive. This cost is amortized by allocating space for a bunch of objects (std::dequeue) in one go and then using them up as you need them.
The other benefit is locality of reference. In a (std::deque) objects are close to each other and thus likely to more efficiently accessed because of hardware caching that will make sure objects close to each other become available quicker.
I initially didn't want to write the implementation of Queue in its header files, but it resulted to all sort of errors. Can Implementation be seprated from its interface whilst using templates?
It can. But for such a simple class I would not bother.
// LinkeddList.h
#ifndef INCLUDE_GUARD
#define INCLUDE_GUARD
namespace Stuff
{
class LinkedList
{
// STUFF
public:
void push(int);
};
}
#include "LinkedList.tpp"
#endif
// LinkedList.tpp
#ifndef INCLUDE_GUARD
#error "You should include LinkedList.h" not this file.
#endif
inline void Stuff::LinkedList::push(int x)
{
// STUFF
}
....
Overview
You have missed the rule of three.
i.e. CopyConstruction and Copy Assignment does not work.
You have not considered move semantics. Big objects are copied into your queue. You could make this a lot more efficient by moving objects into your queue.
Once you have added move semantics you need to remember the rule of five.
The ListNode type is tightly coupled to the Queue type. There is no benifit to exposing the ListNode to users of your class as this simply locks you into maintaining for all future versions (what happens if you want to change it to doubly linked at some future time). Make this a private member of the Queue class so that your implementation details don't leak.
Code Review
Please add a namespace to wrap your personal stuff.
That is a long line with lots of data:
template< typename T > struct ListNode
Normally I would see this:
template<typename T>
struct ListNode
Sure that's a constructor:
ListNode() : next_ptr( nullptr ) {}
But why not initialize all members?
The problem this causes is that if T does not have a default constructor (A constructor that takes no arguments) you can not create objects of ListNode. So I would add a constructor that allows you to pass the data object.
So you should do:
ListNode(T const& data): data(data), next_ptr( nullptr ) {}
ListNode(T&& data): data(std::move(data), next_ptr( nullptr ) {}
But looking at your code you always set next_ptr just after creating the node. Why not then pass the next pointer as an argument to the constructor to simplify this processes.
ListNode(T const& data, ListNode* next): data(data), next_ptr( next ) {}
ListNode(T&& data, ListNode* next): data(std::move(data), next_ptr( next ) {}
That's great. It now does everything you need. But there is already a constructor that does this that is implemented automatically by the compiler. So why have a constructor. Just use the default implementation and it will do all the work for you.
struct ListNode
{
T data;
ListNode *next_ptr;
};
What is this used for?
ListNode<T> node; // Were you planning on using a sentinel?
OK. head and tail.
ListNode<T> *head, *tail;
Why be lazy and squeeze this on one line. Make it easy to read put it on two. All coding standards you find will also specify the same thing. There is no reason to do this and make it hard to read.
Is size_t always in the global namespace?
size_t queue_size;
Nope. You can force that by including certain headers. But do you want to do that with C++ code where all the other types are in the std namespace? Use std::size_t.
This doe's not delete the queue.
~Queue()
{
delete head, tail;
}
You are missing all elements that are not head/tail.
Don't use inline here.
inline void push( T x )
All method declarations in a class are already inline by default. And inline does not mean inline the code it tells the linker there may be multiple definitions in object files for this function it they can safely be ignored.
The use of inline for inline-ing code is redundant. The compiler already makes the best choices and does it automatically (better than us puny humans). People may argue that there are other keywords for forcing inlining sure. But don't think humans make the choice of adding those compiler specific commands (unless your an idiot human). These are added once you have proved the compiler is making an non optimal choice you want to force it one way or another (that is hard work).
As noted before you should probably pass by const reference or r-value reference for efficiency.
void push(T x) // The parameter is copied here.
// use
void push(T const& x) // pass a reference remvoe one copy.
void push(T&& x) // pass by r-value ref allow move.
I would simplify your push to:
void push(T const& x)
{
head = new ListNode<T>(x, head);
if (tail == nullptr) {
tail = head;
}
++queue_size;
}
void push(T&& x)
{
head = new ListNode<T>(std::move(x), head);
if (tail == nullptr) {
tail = head;
}
++queue_size;
}
Sure you can check the operation is valid.
inline void pop()
{
if( head == nullptr ) throw std::out_of_range( "Queue is empty" );
But the standard libraries don't. They allow you to break the users code here. The logic is there is a a way for them to check externally empty() and they should be using this. Its their fault if they are bad programmers.
In C++ the standard behavior is that code should be optimal in all situations. Consider this situation:
while(!queue.empty()) {
queue.pop();
}
Why are you making me pay the price of a check inside pop() when I have already payed the price externally. Its twice as expensive as it needs to be.
Now we do understand there are beginners out there. So we also provide methods that do check for situations where it would be nice for the interface to perform the check:
Example:
for(int loop = 0;loop < vec.size(); ++loop)
std::cout << "Loop: " << loop << " " << vec[loop] << "\n"; // No check on accesses.
std::cout << "Loop: " << loop << " " << vec.at(15) << "\n"; // Checked accesses.
The std::vector provides two methods to accesses elements. Once is checked you can use this in situations where you have not done the check externally. While the other is not checked and can be used when you know the input is always in range.
T& operator[](int index);
T& at(int index);
Same argument on checking here:
inline T& front()
{
if( head != nullptr ) return head->data;
else throw std::out_of_range( "Queue is empty" );
}
inline T& back()
{
if( tail != nullptr ) return tail->data;
else throw std::out_of_range( "Queue is empty" );
}
Functions that do not change the state of an object should be marked const. Thus when you pass the Queue by const reference to a function you can still accesses functions that don't mutate the object.
The obvious functions here are:
std::size_t size() const { return queue_size;} // No change in state.
bool empty() const; // This never mutates the object.
//
// Should be able to tell if a Queue is empty and
// its size even when you only have a const reference
// to the obejct
Less obvious are the front() and back() methods. Here you can have two modes. There can be a mutating version that allows you to mutate the members in the queue (if you want that functionality (not sure you do in a queue)).
// Mutatable accesses
T& front() {return head->data;}
T& back() {return tail->data;}
// Non Mutatable accesses
T const& front() const {return head->data;}
T const& back() const {return tail->data;}
This is an anti pattern:
if (test) {
return true;
}
else {
return false;
}
You can simplify it to:
return test;
So lets look at empty():
bool empty()
{
if( head == nullptr ) return true;
return false;
}
// Simplify to:
bool empty() const
{
return head == nullptr;
}
HowTo
Queue.h
#ifndef THORSANVIL_QUEUE_H
#define THORSANVIL_QUEUE_H
#include <iostream>
#include <initializer_list>
namespace ThorsAnvilExamples
{
template<typename T>
class Queue
{
struct ListNode
{
T data;
ListNode *next_ptr;
};
template<typename E>
class iteratorBase
{
ListNode* data;
public:
iteratorBase(ListNode* d): data(d) {}
E& operator*() {return data->data;}
E* operator->() {return &data->data;}
iteratorBase& operator++() {data = data->next_ptr;return *this;}
iteratorBase operator++(int) {iterator tmp(*this);++(*this);return tmp;}
bool operator==(iteratorBase const& rhs) {return data == rhs.data;}
bool operator!=(iteratorBase const& rhs) {return data != rhs.data;}
};
private:
ListNode* head = nullptr;
ListNode* tail = nullptr;
std::size_t qsize = 0;
public:
Queue()
{}
Queue(std::initializer_list<T> list)
{
for(T const& item: list) {
push(item);
}
}
Queue(Queue const& copy)
{
for(T const& item: copy) { // Add begin() and end()
push(item);
}
}
Queue& operator=(Queue const& copy)
{
Queue tmp(copy);
swap(tmp);
return *this;
}
Queue(Queue&& move) noexcept
{
swap(move);
}
Queue& operator=(Queue&& copy) noexcept
{
swap(copy);
return *this;
}
void swap(Queue& other) noexcept
{
using std::swap;
swap(head, other.head);
swap(tail, other.tail);
swap(qsize, other.qsize);
}
~Queue()
{
ListNode* old;
while(head != nullptr) {
old = head;
head = head->next_ptr;
delete old;
}
}
friend void swap(Queue& lhs, Queue& rhs)
{
lhs.swap(rhs);
}
using iterator = iteratorBase<T>;
using const_iterator = iteratorBase<T const>;
iterator begin() {return iterator{head};}
const_iterator begin() const {return const_iterator{head};}
const_iterator cbegin()const {return const_iterator{head};}
iterator end() {return iterator{nullptr};}
const_iterator end() const {return const_iterator{nullptr};}
const_iterator cend() const {return const_iterator{nullptr};}
void push(T const& x) {add(new ListNode{x, head});}
void push(T&& x) {add(new ListNode{std::move(x), head});}
template<typename... Args>
void push(Args&&... args) {add(new ListNode{T(std::move(args)...), head});}
void pop()
{
ListNode* old = head;
head = head->next_ptr;
delete old;
--qsize;
}
T const& front() const {return head->data;}
T const& back() const {return tail->data;}
bool empty() const {return head == nullptr;}
std::size_t size() const {return qsize;}
void print(std::ostream& str = std::cout) const
{
if (head) {
str << head->data;
for(ListNode* temp = head->next_ptr; temp != nullptr; temp = temp->next_ptr) {
str << " " << temp->data;
}
}
}
friend std::ostream &operator<<(std::ostream &str, const Queue &q)
{
q.print(str);
return str;
}
private:
void add(ListNode* newhead)
{
head = newhead;
if( tail == nullptr ) {
tail = head;
}
++qsize;
}
};
}
#endif
