Doubly-linked list with iterators

Overview

Your class has a limitation that required T to have default constructor.

Your class is not really suitable to hold anything but the most basic of types (like int/float) as removing elements does not guarantee that destructor of the removed element is called at that point. So your list can hold onto resources that will never be used.

The copy constructor does not provide the strong exception guarantee, nor do you provide the standard swap operations nor the move semantics I would expect to see with a container class.

In terms of adding elements I would also expect to see the ability to build objects of type T in place rather than forcing a copy of the object into the container.

Overall a good first try but a few mistakes need to be cleaned up before this is ready.

Please check out the reference implementation I wrote at then end of this answer: https://codereview.stackexchange.com/a/126007/507

Looking at compiler warnings:

bash-5.0$ g++ -std=c++17 -Wall -Wextra -Werror -pedantic dl.cpp
dl.cpp:289:22: error: comparison of integers of different signs: 'int' and 'size_t' (aka 'unsigned long') [-Werror,-Wsign-compare]
dl.cpp:308:22: error: comparison of integers of different signs: 'int' and 'size_t' (aka 'unsigned long') [-Werror,-Wsign-compare]
dl.cpp:13:48: error: field 'left' will be initialized after field 'right' [-Werror,-Wreorder]
dl.cpp:12:80: error: field 'value' will be initialized after field 'right' [-Werror,-Wreorder]
dl.cpp:142:28: error: comparison of integers of different signs: 'int' and 'size_t' (aka 'unsigned long') [-Werror,-Wsign-compare]

5 errors generated.

Nothing major. I would fix them so that more serious warnings are made visible and you can compile your code at the highest warning level and make sure the code compiles with no warnings.

Though in this case error: field 'left' will be initialized after field 'right' is not an issue it can be a serious problem with code. If you are reading the constructor and seeing a specific order of initialization of members that the class may depend on and that is not what is going to happen in reality then you can end up in some serious problems.

CodeReview

Curious why you need these headers. Lets find out.

#include <ctime>
#include <random>

Some vertical spacing to make it easier to read please.

#include <random>
template <typename T>
class QEList

I would add all your code into a namespace for your code.
I have the website ThorsAnvil.com (So I put everything in ThorsAnvil namespace). But something like namespace Qela {} would work just as well.

Interesting constructors:

         Node(Node* left_a,const T& value_a, Node* right_a) : left(left_a), value(value_a), right(right_a) {}

The first constructor has an oddly defined initializer list that implies the value is initialized before right. But the members are initialized in order of declaration. So be careful of using another order as you may confuse people.

Also the compiler would allow this initialization using a simple list initialization without you having to specify it (assuming there were no constructors).

The second constructor:

         Node(Node* left_a,Node* right_a) : left(left_a) , right(right_a) {}

Is odd in that you don't initialize the value. I don't see a situation where you are going to add a node without a value.

There is also the issue that this means the type T must be default constructible. Otherwise this code will fail to compile. This is not a valid assumption for the general case.

Answer to Question: Where is the T default constructor called.

You call the default constructor of T when you create a Node object with explicitly initializing the value member.

  // This constructor you have written:
  Node(Node* left_a,Node* right_a)
     : left(left_a)
     , right(right_a)
  {}

  // This is the same as writting:
  Node(Node* left_a,Node* right_a)
     : left{left_a}
     , right{right_a}
     , value{}          // Even though you do not initialize value
                        // the compiler must initialize this value.
  {}

Now you call this constructor in the QEList constructor when the end_ptr value is initialized.

  // You add the is declaration to `QEList`
  Node *end_ptr = new Node(nullptr,nullptr);
  // This means on construction of the object you will call this.

  // So this declaration:
  QEList() = default;

  // Is equivalent to:
  QEList()
      : m_size{0}
      , end_ptr{new Node(nullptr,nullptr)} // This will call the above
                                           // Node constructor that in
                                           // turn calls the default T
                                           // constructor. 
      , head{end_ptr}
  {}

You can test this all out by trying to add this:

  class X
  {
       public:
           X(int){}       // Because we define a constructor
                          // the compiler will not generate a default
                          // constructor for this class.
                          // And we have not defined one either.
  };


  int main()
  {
       QEList<X>  list;
  }

The above code will fail to compile.

I would simply re-write this as:

struct Node
{
     Node* right;  // Note: putting the '*' next to the name is a C thing
     Node* left;   //       in C++ the '*' goes next to the type (usually).
     T     value;
};

This is now considered old:

        typename iterator::pointer ptr;

The more modern incarnation is:

        using ptr = iterator::pointer;

OK. From this implementation detail that you always have a one past the end node.

friend bool operator==(const iterator& i1, const iterator& i2){ return i1.ptr == i2.ptr; }

Otherwise you could not compare against the end iterator. Which is why you have the node constructor with no value.

That's fine. But your one past the end node still contains an object of type T that will need default construction.

You don't need to create (basically) the same class again. A template here with appropriate parameters should work:

    class const_iterator : public std::iterator<std::bidirectional_iterator_tag,const Node,int,const Node *,const T>
    {
         ... STUFF
    };

Why not write it like this:

    template<typename T, typename N>
    class Iterator: public std::iterator<std::bidirectional_iterator_tag, N, int, N*, T>
    {
       .... STUFF
    }
    using iterator       = Iterator<T, Node>;
    using const_iterator = Iterator<const T, const Node>;

That's a queasy recursive definition:

    template<typename... Types>
    QEList(const T &value,Types&&... values) :  QEList(values...)
    {
        push_front(value);
    }

I suspect you wanted this to support a list of T to initialize the list with.

But it also allows a couple of things I suspect you don't want:

   QEList<int>     list1;
   QEList<int>     list2(5, list1);
   QELIST<int>     list3(5, vec.begin(), vec.end());
   QELIST<int>     list4(5, std::move(list2));

I would re-write to use std::initalizaer_list

    QEList(std::initializer_list<T> const& list)
    {
        for(value: list) {
           push_back(value);
        }
    }

    ....
    // now you can do:
    QEList  list{1,2,3,4,5,6};

You are writing the copy constructor in terms of the assignment operator.

    QEList(const QEList &QEL) { *this = QEL; }

Normally it is the other way around. You write the assignment operator in terms of the copy constructor (See Copy and Swap Idiom).

Looking the assignment operator (which I found all the way at the bottom and private). Normally this would be public otherwise just make it a named function.

    void operator=(const QEList &QEL)
    {
        this->clear();
        auto iter = QEL.cbegin();
        for(;iter != QEL.cend();iter++)
        {
            this->push_back(*iter);
        }
    }

This method does not provide the strong exception guarantee that I would expect from a copy constructor. So I would normally write these two methods like this:

   QEList(const QEList& copy)
   {
       for(auto const& value: copy) {
            push_back(value);
       }
   }
   QEList& operator=(QEList const& copy)
   {
       QEList temp(copy);
       swap(temp);
       return *this;
   }
   void swap(QEList& other) noexcept
   {
       using std::swap;
       swap(head,    other.head);
       swap(end_ptr, other.end_ptr);
       swap(m_size,  other.m_size);
   }
   friend void swap(QEList& lhs, QEList& rhs)
   {
       lhs.swap(rhs);
   }

In the destructor you use this->

    ~QEList()
    {
        this->clear();
        delete end_ptr;
    }

This is a code smell. The only reason to use this->x over simply x is that you have an issue with shadowing the member x with a local variable. The compiler can not detect incorrect access to the local variable and thus can not warn you about it. This means this type of error is hard to spot and detect. It is better to never have shadowed variables (and get your compiler to warn you about variable shadowing). That way your code is easy to read and you always know what variable you are referring to as they have distinct names.

Sure you are deleting the last element in the list correctly.

    void pop_back()//deletes the last node
    {
        Node* temp = end_ptr;
        end_ptr = end_ptr->left;
        end_ptr->right = nullptr;
        delete temp;
        m_size--;
    }

But you are not deleting the object it contains. What happens if that object contains a DB cursor. You are now holding open a resource that will never be used.

When I delete the last element from a list I expect the associated object to also be destroyed so that all its resources are cleanup.

Same issue as pop_back().

    void pop_front()//deletes the first node

    void push_back(const T &value_a)//adds the value to the end of the list
    {
        end_ptr = new Node(end_ptr,nullptr);
        end_ptr->left->value = value_a;
        if(m_size > 0) end_ptr->left->left->right = end_ptr->left;
        end_ptr->left->right = end_ptr;
        m_size++;
    }

I think this can be simplified:

    void push_back(const T &value_a)
    {
        Node* node = new Node(end_ptr->left, endptr, value_a);
        if(node->left) {
            node->left->right = node;
        }
        else {
            head = node;
        }
        node->right->left = node;
        ++m_size;
    }

    void clear()
    {
        ...
        // If this is not already true then you fucked up.
        // rather than explicityl throwing away a potential error
        // I would validate that this is true.
        head = end_ptr;
        m_size = 0;
    }

    void erase(const_iterator position)//deletes the node that the iterator points to (the iterator itself becomes hung)
    {

        // Is `end_ptr->left` always `nullptr`?????
        // I think you mean `position.ptr != end_ptr`
        if(position.ptr != head && position.ptr != end_ptr->left)

OK. This is logically correct.

    void erase(const_iterator begin_pos,const const_iterator end_pos)//deletes everything from begin_pos to end_pos (end_pos itself is not deleted)
    {
        while(begin_pos != end_pos)
        {
            // You will see that most erase functions in the
            // standard return the next element after deleting.
            this->erase(begin_pos++);

            // The problem here is that this code is very brittle.
            // If we moved that `++` to the front it would easily
            // break the code (I think it would be undefined behavior).
            // Since the standard recomendation for C++ is to use
            // prefix ++ operations I can see a maintainer coming
            // along in a few years and potentially changing this
            // to the wrong version.
            //
            // I would change it so either.
            //    A: Write a good comment why you can change the ++
            //    B: Change erase() to return the next value to be
            //       removed.
        }
    }

But could we not do it more effeciently?

    void erase(const_iterator begin,const const_iterator end)
    {
        if (begin == end) {
            return;
        }
        if (begin.pos == head && end.pos == end_ptr) {
            clear();
        }
        else
        {
            if (begin.pos == head) {
                head                   = end.pos;
            }
            else {
                begin.pos->left->right = end.pos;
            }
            end.pos->left          = begin.pos->left;

            Temp* next
            for(loop = begin.pos; loop != end.pos; loop = next) {
                next = loop->right;
                delete loop;
            }
        }   
    }

That's a good start:

    iterator begin() { return iterator(head); }
    const_iterator cbegin() const { return const_iterator(head); }
    iterator end() { return iterator(end_ptr); }
    const_iterator cend() const { return const_iterator(end_ptr); }

But you are missing a few definitions:

     const_iterator begin() const    { return const_iterator(head); }
     const_iterator end()   const    { return const_iterator(end_ptr); }

What about reverse iterator?

     rbegin(), rend(), rbegin() const, rend() const

You can return a value by index.

    T& operator[](unsigned const int &index) const

But that function should not be marked const unless you return a const reference to T or return T by value.

Alternatively your would normally provide two versions of this method:

    T&       operator[](unsigned const int &index);
    T const& operator[](unsigned const int &index) const;

The qsort/selection sort should be a separate code reviews. There is a lot to fix above first.