Gfrktyl

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