Vwwxrf

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:

1. 
   

   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?

2. Moreover, what is the meaning of "&&"?



3. 
   

   How are the two functions

   
   
   

    (a) const T & front() const
    (b) T & front()
   

   
   

differentiated by the compiler? Moreover, that (a) has a const after the function's name means that an outside user will not be able to modify the front variable? Would you even want to modify the front (or end) variable of a queue?

4. 
   

   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?

5. 
   

   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(); 
    
   

   
   



6. 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?

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.

7. Should I have implemented anything differently?


8. 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;

 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