Im trying to teach myself some computer science (and c++). I am relatively new to this (and to code review).
I have attempted to implement a queue. I have copied the code below for reference.
QUESTIONS:
I have used assertions in many instances: I assert that the size must be non-zero when accessing the front or the back and when popping (or, dequeueing in my case); I assert that an index must be between 0 and one less than the size when implementing the function
T const & at(size_t index)and I assert that "this != other" in the copy constructor. Are these appropriate uses of assertion? Should I throw exceptions instead? Or should I do things differently? What is the standard practice with respect to error checking? Should I simply allow for undefined behavior?
Would you implement the copy constructor and the destructor differently?
Queue(Queue const & other) : m_front(nullptr), m_back(nullptr), m_size(0), { assert(this != &other); this->enqueue(other); } ~Queue() { this->clear(); }I noticed that cppreference mentioned something about an "Allocator." Would it be difficult to incorporate into my code? Is it only for array-based implementations? I have implemented queues via arrays. If it is not difficult to incorporate, how would I go about doing so?
Is there any way to pass a generic "Container" object into the constructor to to initialize the queue? So, for example, the user has the option of passing in an array, or a vector, to have the values in that container copied into the queue.
The following questions are welcome. However, I realize they are non specific, and if I should remove them, please let me know. I will do so, and restrict the code I posted to reflect only my questions prior.
Should I have implemented anything differently?
Any stylistic advice?
MY CODE (FOR REFERENCE):
Queue.h:
#ifndef QUEUE_H
#define QUEUE_H
#include <algorithm>
#include <climits>
template <class T>
class Queue
{
private:
struct QueueItem
{
T val;
QueueItem *next;
QueueItem() : next(nullptr) {}
QueueItem(T const & val, QueueItem *next) : val(val), next(next) {}
QueueItem(T const & val) : val(val), next(nullptr) {}
QueueItem(QueueItem *next) : next(next) {}
};
QueueItem *m_front;
QueueItem *m_back;
size_t m_size;
public:
//friends
friend void swap(Queue & a, Queue & b)
{
using std::swap;
swap(a.m_front, b.m_front);
swap(a.m_back, b.m_back);
swap(a.m_size, b.m_size);
}
friend void concatenate(Queue & a, Queue & b)
{
a.m_back->next = b.m_front;
a.m_back = b.m_back;
}
//constructors and deconstructor
Queue() : m_front(nullptr), m_back(nullptr), m_size(0) {}
Queue(Queue const & other) : m_front(nullptr), m_back(nullptr), m_size(0)
{
assert(this != &other);
this->enqueue(other);
}
~Queue()
{
this->clear();
}
//capacity
size_t const size() const;
bool const empty() const;
//element access
T & front();
T const & front() const;
T & back();
T const & back() const;
bool const has(T const & val) const;
T const * const data() const;
//modifiers
T const dequeue();
void enqueue(T const & val);
void enqueue(T && val);
void enqueue(Queue const & other);
T const deenqueue(T const & val);
T const deenqueue(T && val);
void reverse();
void clear();
Queue & operator + (Queue const & other);
Queue & operator += (Queue const & other);
Queue & operator = (Queue const other);
//comparators
bool const operator == (Queue const & other);
bool const operator != (Queue const & other);
};
#include "Queue.hpp"
#endif // QUEUE_H
List.hpp
#ifndef QUEUE_HPP
#define QUEUE_HPP
//capacity
template <class T>
size_t const Queue<T>::size() const
{
return m_size;
}
template <class T>
bool const Queue<T>::empty() const
{
return m_size == 0;
}
//element access
template <class T>
T & Queue<T>::front()
{
assert(m_size > 0);
return m_front->val;
}
template <class T>
T const & Queue<T>::front() const
{
assert(m_size > 0);
return m_front->val;
}
template <class T>
T & Queue<T>::back()
{
assert(m_size > 0);
return m_back->val;
}
template <class T>
T const & Queue<T>::back() const
{
assert(m_size > 0);
return m_back->val;
}
template <class T>
bool const Queue<T>::has(T const & val) const
{
QueueItem *item = m_front;
while(item)
{
if(item->val == val)
return true;
item = item->next;
}
return false;
}
template <class T>
T const * const Queue<T>::data() const
{
if(m_size == 0)
return nullptr;
T const * const data = new T[m_size];
QueueItem *item = m_front;
for(size_t i = 0; item; item = item->next)
data[i++] = item->val;
return data;
}
//modifiers
template <class T>
T const Queue<T>::dequeue()
{
assert(m_size > 0);
T const give = m_front->val;
QueueItem *item = m_front->next;
delete m_front;
m_front = item;
--m_size;
if(m_size == 0)
m_back = nullptr;
return give;
}
template <class T>
void Queue<T>::enqueue(T const & val)
{
QueueItem *item = new QueueItem(val);
if(m_size == 0)
m_front = m_back = item;
else
{
m_back->next = item;
m_back = item;
}
++m_size;
}
template <class T>
void Queue<T>::enqueue(T && val)
{
QueueItem *item = new QueueItem(val);
if(m_size == 0)
m_front = m_back = item;
else
{
m_back->next = item;
m_back = item;
}
++m_size;
}
template <class T>
void Queue<T>::enqueue(Queue<T> const & other)
{
QueueItem *item = other.m_front;
while(item)
{
this->enqueue(item->val);
item = item->next;
}
}
template <class T>
T const Queue<T>::deenqueue(T const & val)
{
T const give = dequeue();
QueueItem *item = new QueueItem(val);
if(m_size == 0)
m_front = m_back = item;
else
{
m_back->next = item;
m_back = item;
}
++m_size;
return give;
}
template <class T>
T const Queue<T>::deenqueue(T && val)
{
T const give = dequeue();
QueueItem *item = new QueueItem(val);
if(m_size == 0)
m_front = m_back = item;
else
{
m_back->next = item;
m_back = item;
}
++m_size;
return give;
}
template <class T>
void Queue<T>::reverse()
{
using std::swap;
QueueItem *first = nullptr,
*second = m_front,
*save;
while(second)
{
save = second->next;
second->next = first;
first = second;
second = save;
}
swap(m_front, m_back);
}
template <class T>
void Queue<T>::clear()
{
while(m_front)
{
QueueItem *item = m_front->next;
delete m_front;
m_front = item;
}
m_back = nullptr;
m_size = 0;
}
template <class T>
Queue<T> & Queue<T>::operator + (Queue<T> const & other)
{
this->enqueue(other);
return *this;
}
template <class T>
Queue<T> & Queue<T>::operator += (Queue<T> const & other)
{
this->enqueue(other);
return *this;
}
template <class T>
Queue<T> & Queue<T>::operator = (Queue<T> const other)
{
swap(*this, other);
return *this;
}
//comparators
template <class T>
bool const Queue<T>::operator == (Queue<T> const & other)
{
if(m_size != other.m_size)
return false;
QueueItem *thsitem = m_front,
*othitem = other.m_front;
while(thsitem)
{
if(thsitem->val != othitem->val)
return false;
thsitem = thsitem->next;
othitem = othitem->next;
}
return true;
}
template <class T>
bool const Queue<T>::operator != (Queue<T> const & other)
{
return !(*this == other);
}
#endif // QUEUE_HPP
