Implementation of deque

Question

What can be simplified, altered, or implemented differently? I would like to know if there's a way to further improve this code.

#ifndef _DEQUE_H_
#define _DEQUE_H_
//-------------------------------------------------------------------------
template <typename Type>
class Deque
{
private:
    struct Node
    {
        Type element = {};
        Node* prev = nullptr;
        Node* next = nullptr;
    };
    size_t count;
    Node* head;
    Node* tail;
public:
    //Member functions
    Deque();
    Deque(const Deque & deq);
    Deque(Deque && deq);
    Deque & operator = (const Deque & deq);
    Deque & operator = (Deque && deq);
    ~Deque();

    //Element access
    //const Type & at(Deque pos) const; Not implemented
    //template <typename Type>
    //const Type & operator[](size_type pos) const; Not implemented
    const Type & front() const;
    const Type & back() const;

    //Iterators
    //TODO: Implement in the near future 

    //Capacity
    bool empty() const;
    size_t size() const;
    //size_t max_size() const noexcept; Not implemented

    //Modifiers
    void push_front(const Type & tp);
    void push_back(const Type & tp);

    //void emplace_front(); Not implemented
    //void emplace_back(); Not implemented

    void pop_front();
    void pop_back();

    void clear() noexcept;
    void swap(Deque & deq) noexcept;
};
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque() : count(0), head(nullptr), tail(nullptr)
{
    //Body of the constructor class
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque(const Deque & deq) : count(deq.count), head(nullptr), tail(nullptr)
{
    for (const Node* n_ptr = deq.head; n_ptr != nullptr; n_ptr = n_ptr->next)
    {
        Node* n_ptr_new = new Node;
        n_ptr_new->element = n_ptr->element;
        if (head == nullptr && tail == nullptr)
        {
            head = n_ptr_new;
            tail = head;
        }
        else
        {
            tail->next = n_ptr_new;
            n_ptr_new->prev = tail;
            n_ptr_new->next = nullptr;
            tail = n_ptr_new;
        }
    }
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque(Deque && deq) : count(deq.count), head(deq.head), tail(deq.tail)
{
    deq.count = 0;
    deq.head = nullptr;
    deq.tail = nullptr;
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type> & Deque<Type>::operator = (const Deque & deq)
{
    if (this == &deq)
    {
        return *this;
    }

    Deque tmp(deq);
    std::swap(count, tmp.count);
    std::swap(head, tmp.head);
    std::swap(tail, tmp.tail);
    return *this;
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type> & Deque<Type>::operator = (Deque && deq)
{
    if (this == &deq)
    {
        return *this;
    }

    std::swap(count, deq.count);
    std::swap(head, deq.head);
    std::swap(tail, deq.tail);
    return *this;
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::~Deque()
{
    while (head)
    {
        Node* n_ptr_del = head;
        head = head->next;
        delete n_ptr_del;
    }
    count = 0;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::push_front(const Type & tp)
{
    Node* n_ptr_new = new Node;
    n_ptr_new->element = tp;
    if (head == nullptr && tail == nullptr)
    {
        head = n_ptr_new;
        tail = head;
    }
    else
    {
        n_ptr_new->next = head;
        n_ptr_new->prev = nullptr;
        head->prev = n_ptr_new;
        head = n_ptr_new;
    }
    ++count;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::push_back(const Type & tp)
{
    Node* n_ptr_new = new Node;
    n_ptr_new->element = tp;
    if (head == nullptr && tail == nullptr)
    {
        head = n_ptr_new;
        tail = head;
    }
    else
    {
        tail->next = n_ptr_new;
        n_ptr_new->prev = tail;
        n_ptr_new->next = nullptr;
        tail = n_ptr_new;
    }
    ++count;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::pop_front()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        --count;
        head = nullptr;
        tail = nullptr;
        return;
    }

    Node* n_ptr_del = head;
    head = head->next;
    head->prev = nullptr;
    --count;
    delete n_ptr_del;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::pop_back()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        --count;
        head = nullptr;
        tail = nullptr;
        return;
    }

    Node* n_ptr_del = tail;
    tail = tail->prev;
    tail->next = nullptr;
    --count;
    delete n_ptr_del;
}
//--------------------------------------------------------------------------
template <typename Type>
bool Deque<Type>::empty() const
{
    return head == nullptr;
}
//--------------------------------------------------------------------------
template <typename Type>
const Type & Deque<Type>::front() const
{
    if (empty())
    {
        throw std::out_of_range("List<Type>::top: empty stack");
    }
    return head->element;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
const Type & Deque<Type>::back() const
{
    if (empty())
    {
        throw std::out_of_range("List<Type>::top: empty stack");
    }
    return tail->element;
}
//--------------------------------------------------------------------------
template <typename Type>
size_t Deque<Type>::size() const
{
    return count;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::clear() noexcept
{
    while (count)
    {
        pop_back();
    }
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::swap(Deque & deq) noexcept
{
    Deque temp(deq);
    deq = std::move(*this);
    *this = std::move(temp);
}
//--------------------------------------------------------------------------
#endif // _DEQUE_H_

Answer 1

Here are some things that may help you improve your code.

Use appropriate #includes

The code refers to a number of things, such as std::size_t and std::swap which do not have the corresponding #includes. The code should have the following:

#include <cstddef>
#include <utility>
#include <stdexcept>

Don't define the default constructor

The default constructor for the Deque does nothing except for initializing members. Instead, you should use in-class member initializers and let the constructor be generated by the compiler as you have with Node. See CppCoreGuidelines C.45.

Don't use leading underscores in names

Anything with a leading underscore is a reserved name in C++ (and in C). See this question for details. In this case it applies to your chosen name for the include guard.

Simplify your code

The code for push_back and push_front and a number of other functions can be simplified considerably. In the case of push_back, for example, by using the autogenerated constructor for Node:

template <typename Type>
void Deque<Type>::push_back(const Type & tp)
{
    if (tail) {
        tail = tail->next = new Node{tp, tail, nullptr};
    } else {
        head = tail = new Node{tp, nullptr, nullptr};
    }
    ++count;
}

Fix the error messages

Some of the error messages don't seem to match what they're signalling very well. For example, if we attempt to use back() on an empty Deque, it says

throw std::out_of_range("List<Type>::top: empty stack");

This would be a very confusing and unhelpful error message!

Use your own functions

In some cases, the code uses count to determine when the deque is empty, in others it checks if head == nullptr and still others it uses empty(). I'd recommend choosing one mechanism and using it exclusively. Likewise, if you use your own functions, the copy could be as simple as this:

template <typename Type>
Deque<Type>::Deque(const Deque & deq) {
    for (auto curr = deq.head; curr; curr = curr->next) {
        push_back(curr->element);
    }
}

Consider supporting list initialization

At the moment, a construction like this is not supported:

Deque<std::string> d3{"alpha", "beta", "gamma"};

It's easy to do, however. Here's how I'd do it:

template <typename Type>
Deque<Type>::Deque(std::initializer_list<Type> list) {
    for (auto& item : list) {
        push_back(item);
    }
}

Answer 2

• Node wants a constructor

  Node(const Type& tp, Node * prev = nullptr, Node * next = nullptr)
     : element(tp)
     , prev(prev)
     , next(next)
  {}
  

• What can be simplified

  pushs and pops. There is common functionality between a special and common cases. Consider for example push_front: after the push a new node would become head, no matter what:

  push_front(const Type& tp) {
      node = new Node(tp, nullptr, head);
      if (head == 0) {
          tail = node;
      } else {
          head->prev = node;
      }
      head = node;
  }
  

  Other three function can be similarly streamlined.

• A copy constructor shares too much code with push_back. Consider consolidating the common base. Ditto for a destructor and clear.

• You may want to assert your invariants: if you have, say, head == nullptr, you must also have tail == nullptr and count == 0.