I have attempted to implement a queue. I have copied the code below for reference.
I have several questions:
-
I used the template described on cppreference.com to guide me in the implementation of some of the functions, such as push() (enqueue() in my case). On cppreference.com, the following templates are given:
(a) push(const value_type & value); (b) push(value_type && value);
https://en.cppreference.com/w/cpp/container/queue/push
Since (a) takes a reference, how is it that literals are added to the queue?
Moreover, if I implement a function
enqueue(Queue const & other)
using the function
enqueue(T const & value)
by iterating through "other" and enqueuing every value in "other," will this not add "deep" copies of the values in "other?" And, therefore, I should not pass a reference to other, but a copy?
-
Moreover, what is the meaning of "&&"?
-
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 assert? Should I throw exceptions instead? Or should I do things differently?
-
Would you implement the copy constructor and the destructor differently?
Queue(Queue const & other) : m_front(nullptr), m_back(nullptr), m_size(0), m_cap(other.m_cap) { assert(this != &other); this->enqueue(other); } ~Queue() { this->clear(); }
The following questions are welcomed as well. 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?
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;
size_t m_cap;
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);
swap(a.m_cap, b.m_cap);
}
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), m_cap(INT_MAX) {}
Queue(size_t const cap) : m_front(nullptr), m_back(nullptr), m_size(0), m_cap(cap)
{
assert(cap > 0);
}
Queue(Queue const & other) : m_front(nullptr), m_back(nullptr), m_size(0), m_cap(other.m_cap)
{
assert(this != &other);
this->enqueue(other);
}
~Queue()
{
this->clear();
}
//capacity
size_t const size() const;
bool const empty() const;
size_t const capacity() const;
bool const at_capacity() const;
//element access
T & front();
T const & front() const;
T & back();
T const & back() const;
bool const has(T const & val) const;
T & at(size_t index);
T const & at(size_t index) const;
T & operator [] (size_t index);
T const & operator [] (size_t index) const;
T const * const data() const;
//modifiers
T const dequeue();
T const enqueue(T const & val);
T const 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;
}
template <class T>
size_t const Queue<T>::capacity() const
{
return m_cap;
}
template <class T>
bool const Queue<T>::at_capacity() const
{
return m_size == m_cap;
}
//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 & Queue<T>::at(size_t index)
{
assert(index > -1 && index < m_size);
QueueItem *item = m_front;
while(index-- > 0)
item = item->next;
return item->val;
}
template <class T>
T const & Queue<T>::at(size_t index) const
{
assert(index > -1 && index < m_size);
QueueItem *item = m_front;
while(index-- > 0)
item = item->next;
return item->val;
}
template <class T>
T & Queue<T>::operator [] (size_t index)
{
return at(index);
}
template <class T>
T const & Queue<T>::operator [] (size_t index) const
{
return at(index);
}
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>
T const Queue<T>::enqueue(T const & val)
{
T const give;
if(m_size == m_cap)
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>::enqueue(T && val)
{
T const give;
if(m_size == m_cap)
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>::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
Aucun commentaire:
Enregistrer un commentaire