6
\$\begingroup\$

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

  2. 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(); 
           }
    
  3. 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?

  4. 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.

  1. Should I have implemented anything differently?

  2. 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
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. If you believe that your changes was made without invalidating the current answer, please let me know. \$\endgroup\$ – Simon Forsberg Apr 7 at 7:39
  • \$\begingroup\$ Hey, Simon. I did make a change to my code, by it doesn't reflect answers to my questions. Let me know if you need me to do anything on my end! And thanks for informing me. Moving on, I will keep that rule in mind. \$\endgroup\$ – Rafael Vergnaud Apr 7 at 15:59
2
\$\begingroup\$

At first sight, your code looks consistent and readable. Congrats!

That said, I'll jump into your questions. The assertions are used correctly. Often you'll see them written as assert(I > 0 && "Valid index needed"); That allows adding a comment to it. Especially useful if the code itself ain't 100% understandable from the callers point of view.

You're preconditions are also a very good example of the contracts extensions of C++20 and make them part of your API instead. For now, I would document them at class level.

Jumping into the assert of the copy constructor, that one is useless as you can't ever trigger it. It does make sense in copy assignment, although, it's better to handle that case and return early.

The implementation of queue looks good to me, it leverages existing methods instead of writing it from scratch. Perfect coding on my side.

You do want to consider initializing the members in the class definition, as it is less error prone.

Adding the allocator is adding an extra template argument and member and replacing all new/delete.

I like the east const, however, adding const to the return value if by value doesn't make much sense. I would remove it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.