No appropriate default constructor

Question

This is a learning project so please give any additional advice that comes to mind.

I am trying to learn data structures by re-implementing some STL containers/algorithms and I've started with linked lists. If I try to make a list of a class lacking a default constructor I would get a compiler error of "no appropriate default constructor":

#include "list.h"
#include <list>

class testA
{
private:
    int mInt;
public:
    testA(int i) : mInt(i) {}
};

int _tmain(int argc, _TCHAR* argv[])
{
    std::list<testA> wS; // Fine
    wS.push_back(1);     // Fine

    MTL::list<testA> wM; // 'testA' has no appropriate default constructor
    wM.push_back(1); 

    return 0;
}

The problem is I'm using a dummy node in the list to store a link to the beginning and the end of the list. I use this mainly to get the .end() function to work properly and give a decrement-able iterator to one past the end of the list. When I declare an empty list one of the functions wants the default constructor for the templated type so it can make my dummy node! If no default constructor exists, it gives the error message.

On the positive side, it looks like a couple of STL implementations actually use the dummy head node idea. On the negative side, it looks like they pull some nasty tricks to get around this issue. My visual studio 2010 STL implementation eventually calls raw operator new and delete without calling the constructor. I've basically copied what it has (look for ::operator new and delete) and I get it to compile. Here is the full code:

#include <cassert>
#include <iostream>

namespace MTL
{
    template< typename T >
    class list
    {
    private:
        // If ListNode is in the private part of list, clients
        // can't mess around with ListNodes.
        template <typename T>
        class ListNode
        {
        private:
            ListNode<T>* p_mNextNode;
            ListNode<T>* p_mPreviousNode;

            T mNodeVal;

        public:
//          ListNode() : 
//              p_mNextNode(0),
//              p_mPreviousNode(0) {}

            ListNode(T const & aVal) : 
                p_mNextNode(0),
                p_mPreviousNode(0),
                mNodeVal(aVal) {}

            ListNode<T>* GetNextNode() {return p_mNextNode;}
            ListNode<T>* GetPreviousNode() {return p_mPreviousNode;}

            void SetNextNode(ListNode<T>* const aNode) {p_mNextNode = aNode;}
            void SetPreviousNode(ListNode<T>* const aNode) {p_mPreviousNode = aNode;}

            T& GetNodeVal() {return mNodeVal;}
        };

    public:
        class iterator
        {
        private:
            ListNode<T>* mIteratorNode;

        public:
            iterator() : mIteratorNode(0) {}
            iterator(ListNode<T>* aListNode) {mIteratorNode = aListNode;}

            T& operator*() {return mIteratorNode->GetNodeVal();}

            iterator& operator++() {mIteratorNode = mIteratorNode->GetNextNode(); return *this;}
            iterator& operator--() {mIteratorNode = mIteratorNode->GetPreviousNode();   return *this;}

            bool operator==(iterator const& aIterator) {return mIteratorNode==aIterator.mIteratorNode;}
            bool operator!=(iterator const& aIterator) {return !(mIteratorNode==aIterator.mIteratorNode);}

            ListNode<T>* GetNode() {return mIteratorNode;}
            ListNode<T>* GetNextNode() {return mIteratorNode->GetNextNode();}
            ListNode<T>* GetPreviousNode() {return mIteratorNode->GetPreviousNode();}
        };

    private:
        ListNode<T>* p_mHeadNode;

        void insert(ListNode<T>* const aNewNode, iterator& aIterator)
        {
            ListNode<T>* currentNode = aIterator.GetNode();
            ListNode<T>* currentsPreviousNode = currentNode->GetPreviousNode();
            currentsPreviousNode->SetNextNode(aNewNode);
            aNewNode->SetPreviousNode(currentsPreviousNode);
            aNewNode->SetNextNode(currentNode);
            currentNode->SetPreviousNode(aNewNode);
        }

        void eraseNode(ListNode<T>* aListNode)
        {
            ListNode<T>* previousNode = aListNode->GetPreviousNode();
            ListNode<T>* nextNode     = aListNode->GetNextNode();

            previousNode->SetNextNode(aListNode->GetNextNode());
            nextNode->SetPreviousNode(aListNode->GetPreviousNode());

            if (p_mHeadNode != aListNode)
            {
                delete aListNode;
            }
        }

    protected:

    public:
        list() : p_mHeadNode(static_cast<ListNode<T>*>(::operator new (sizeof(ListNode<T>))))
        {
            // To get .begin or .end to work immediately after construction
            p_mHeadNode->SetNextNode(p_mHeadNode);
            p_mHeadNode->SetPreviousNode(p_mHeadNode);
        }
        list(list const& aList) : p_mHeadNode(static_cast<ListNode<T>*>(::operator new (sizeof(ListNode<T>))))
        {
            p_mHeadNode->SetNextNode(p_mHeadNode);
            p_mHeadNode->SetPreviousNode(p_mHeadNode);
            ListNode<T>* pCurrent = (aList.p_mHeadNode)->GetNextNode();

            while (pCurrent != aList.p_mHeadNode)
            {
                this->push_back(pCurrent);
                pCurrent = pCurrent->GetNextNode();
            }
        }

        void push_front(T const& aNewVal)
        {
            ListNode<T>* newNode = new ListNode<T>(aNewVal);
            this->insert(newNode,this->begin());
        }

        void push_back(T const& aNewVal)
        {
            ListNode<T>* newNode = new ListNode<T>(aNewVal);
            this->insert(newNode,this->end());
        }

        void push_back(ListNode<T>* const aListNode)
        {
            this->push_back(aListNode->GetNodeVal());
        }

        void push_front(ListNode<T>* const aListNode)
        {
            this->push_front(aListNode->GetNodeVal());
        }

        T& front(){ return p_mHeadNode->GetNextNode()->GetNodeVal(); }

        T& back(){ return p_mHeadNode->GetPreviousNode()->GetNodeVal(); }

        void pop_front() {this->eraseNode(p_mHeadNode->GetNextNode());}

        void pop_back() {this->eraseNode(p_mHeadNode->GetPreviousNode());}

        const T& front() const { return (p_mHeadNode->GetNextNode())->GetNodeVal(); }

        const T& back() const { return (p_mHeadNode->GetPreviousNode())->GetNodeVal(); }

        iterator begin() {return iterator(p_mHeadNode->GetNextNode());}
        iterator end()   {return iterator(p_mHeadNode);}

        iterator insert(iterator aPosition, const T& aVal)
        {
            assert(0);
            return iterator();
        }

        iterator insert(iterator aPosition, unsigned int n, const T& aVal)
        {
            ListNode<T>* newNode = 0;
            for (unsigned int i = 0; i < n; ++i)
            {
                newNode = new ListNode<T>(aVal);
                this->insert(newNode,aPosition);
                ++aPosition;
            }

            return iterator(newNode->GetNextNode());
        }

        iterator insert(iterator aPosition, iterator aFirst, iterator aLast)
        {
            assert(0);
            return iterator();
        }

        unsigned int size()
        {
            unsigned int counter = 0;
            ListNode<T>* pCurrent = p_mHeadNode->GetNextNode();

            while (pCurrent != p_mHeadNode)
            {
                ++counter;
                pCurrent = pCurrent->GetNextNode();
            }

            return counter;
        }

        ~list()
        {
            this->clear();
            ::operator delete(p_mHeadNode);
        }

        void clear()
        {
            ListNode<T>* pCurrent = p_mHeadNode->GetNextNode();
            ListNode<T>* pNext = pCurrent->GetNextNode();

            while (pNext != p_mHeadNode)
            {
                this->eraseNode(pCurrent);
                pCurrent = pNext;
                pNext = pCurrent->GetNextNode();
            }

            // All but the last has been deleted
            this->eraseNode(pCurrent);
        }

        bool empty() {return (p_mHeadNode->GetNextNode() != p_mHeadNode);}

        friend std::ostream& operator<<(std::ostream& os, list<T> const& aList)
        {
            ListNode<T>* pCurrent = (aList.p_mHeadNode)->GetNextNode();
            std::cout << "List Contents are:\n";
            std::cout << "{";
            while (pCurrent != aList.p_mHeadNode)
            {
                std::cout << pCurrent->GetNodeVal();
                pCurrent = pCurrent->GetNextNode();
                if (pCurrent != aList.p_mHeadNode)
                {
                     std::cout << ",";
                }
            }
            std::cout << "}\n";

            return os;
        }
    };
};

Surely, there must be a cleaner way to get this to work. I can't seem to split my ListNode into a base class of just previous and next pointers and a derived class of the contained data because GetNodeVal() needs a return type of the templated value. So again I would need at least an appropriate constructor to get a dummy value in the base class. I could not make this pure virtual because then my dummy node can not be instantiated as a base class.

This: http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-3.3/stl__list_8h-source.html version is using static casts which seem to be less nasty but I haven't been able to apply it to my code.

So, how can I get this code to work without calling raw operator new/deletes? And will it be any cleaner?

Answer 1

One option for delayed/optional construction of the value could be:

    template <typename T>
    class ListNode
    {
    private:
        ListNode<T>* p_mNextNode;
        ListNode<T>* p_mPreviousNode;

        union {
            char dummy;
            T mNodeVal;
        };

        ListNode() : 
            p_mNextNode(0),
            p_mPreviousNode(0),
            dummy() {}

        ListNode(T const & aVal) : 
            p_mNextNode(0),
            p_mPreviousNode(0),
            mNodeVal(aVal) {}
        ...
   };

You will need to explicitly call its destructor, however, since the compiler no longer knows which of the variant members is active.

---

But it's better to do this for the dummy ListNode inside the List. I guess that the implementation with ::operator new was also special-casing the dummy. Something like this:

template< typename T >
class List
{
private:
    class ListNode
    {
    private:
        ListNode* p_mNextNode;
        ListNode* p_mPreviousNode;
        T mNodeVal;
    };

    class DummyListNode
    {
    public:
        ListNode* p_mNextNode;
        ListNode* p_mPreviousNode;
    };

These are both "standard-layout", and by 9.2:

If a standard-layout union contains two or more standard-layout structs that share a common initial sequence, and if the standard-layout union object currently contains one of these standard-layout structs, it is permitted to inspect the common initial part of any of them.

Let's take advantage of that now:

    union {
        DummyListNode dummy_head_tail;
        ListNode head_tail
    };

    // ... iterators and stuff, using &head_tail as the first and last ListNode*

public:
    List() : dummy_head_tail{ nullptr, nullptr } {  }

    ~List() { /* free all nodes, then */ dummy_head_tail->~DummyListNode(); }
};