List implementation

Question

Appreciate your thoughts and feedback on my simple list implementation.

I have the code on github with list and some googletests here (not sure why github changes the spacing to be so big)

Some points to keep in mind..

1. I have chosen to have two separate functions for assignment and move operators. As oppose to one that takes its argument by value.

2. Best course of action if my clear() function throws? (T's destructor could be set to noecept(false)) Should i stop the exception from propogating and try to continue and delete as many nodes as possible from my list? Or is an exception a fail condition for the whole program and i let it propogate even if it causes terminate to be called?

3. I have chosen to implement my own swap for practice despite, in the case of my list, the standard swap is probable more effcient.

4. I will add iterators, i know its a pretty useless list without traversal but i wanted to get the basics working first.

List.h

#ifndef H_UTILS_STORAGE_LIST_H
#define H_UTILS_STORAGE_LIST_H


//  includes
#include <initializer_list>
#include <utility>

namespace utils {
    namespace storage {

        template <typename T>
        class List {

            friend void swap(List<T>& lhs, List<T>& rhs) noexcept
            {
                Node* tempHead(lhs.mHead);
                lhs.mHead = rhs.mHead;
                rhs.mHead = tempHead;

                std::size_t tempSize(lhs.mSize);
                lhs.mSize = rhs.mSize;
                rhs.mSize = tempSize;
            }

        private:
            //  Node
            struct Node {
                T mData;
                Node* mNext = nullptr;
            };

        public:
            List() = default;
            explicit List(const std::size_t size);
            explicit List(const std::initializer_list<T>& il);
            List(const List& rhs);
            List(List&& rhs) noexcept;
            ~List();

            List& operator=(const List& rhs);
            List& operator=(List&& rhs);

            template<typename ...Args>
            void emplace(Args&&... args);

            void insert(const T& t);
            void insert(T&& t);

            void remove(const T& t);
            void clear();

            std::size_t getSize() const { return mSize; }

        private:
            Node* mHead = nullptr;
            std::size_t mSize = 0;
        };

        //  custom constructor - create a list of N size
        template <typename T>
        List<T>::List(const std::size_t size)
        {
            //  empty list?
            if (size == 0) return;

            //  create head
            mHead = new Node{};

            //  create a temporary pointer to the head of the list
            Node* node = mHead;
            for (int i = 0; i < size - 1; ++i) {
                //  this is a valid node
                //  create a new node
                //  link it to the list
                node->mNext = new Node{};

                //  iterate to the next node
                node = node->mNext;
            }

            mSize = size;
        }

        //  custom constructor - create a list populated with data
        template <typename T>
        List<T>::List(const std::initializer_list<T>& il)
        {
            //  empty list?
            if (il.size() == 0) return;

            //  get first element in list and make the head node
            auto it = il.begin();
            mHead = new Node{ (*it), nullptr };
            ++it;

            //  create a temporary pointer to the head of the list
            Node* node = mHead;
            for (; it != il.end(); ++it) {
                //  this is a valid node
                //  create a new node
                //  link it to the list
                node->mNext = new Node{ (*it), nullptr };

                //  iterate to the next node
                node = node->mNext;
            }

            mSize = il.size();
        }

        template <typename T>
        List<T>::List(const List<T>& rhs)
        {
            Node* lhsNode = nullptr;
            Node* rhsNode = rhs.mHead;

            //  create the head node
            if (rhsNode) {                              
                lhsNode = new Node{ rhsNode->mData, nullptr };
                mHead = lhsNode;

                //  iterate to next rhs node
                rhsNode = rhsNode->mNext;
            }

            //  create rest of list
            while (rhsNode && lhsNode) {

                //  create a copy of the rhs node
                //  link it to lhs list
                lhsNode->mNext = new Node{ rhsNode->mData, nullptr };

                //  iterate to next lhs node
                lhsNode = lhsNode->mNext;

                //  iterate to next rhs node
                rhsNode = rhsNode->mNext;
            }

            mSize = rhs.mSize;
        }

        template <typename T>
        List<T>::List(List<T>&& rhs) noexcept
        {
            using std::swap;
            swap(*this, rhs);
        }

        template <typename T>
        List<T>::~List()
        {
            try {
                clear();
            } catch (...) {
                //  T's destructor could be set to noexcept(false) and throw during the delete call
                //  do not allow any exceptions to propogate from a destructor
            }
        }

        template <typename T>
        List<T>& List<T>::operator=(const List<T>& rhs)
        {
            //  check for self assignment
            if (this != &rhs) {

                //  make a copy of rhs
                List<T> rhsCopy(rhs);

                //  swap
                using std::swap;
                swap(*this, rhsCopy);
            }

            return *this;
        }

        template <typename T>
        List<T>& List<T>::operator=(List<T>&& rhs)
        {
            //  check for self move
            if (this != &rhs) {

                //  swap
                using std::swap;
                swap(*this, rhs);
            }

            return *this;
        }

        template<typename T>
        template<typename ...Args>
        void List<T>::emplace(Args&&... args)
        {
            //  forward to the relevant insert
            insert(std::forward<Args>(args)...);
        }

        template <typename T>
        void List<T>::insert(const T& t)
        {
            Node* tail = mHead;

            //  find the tail of the list
            while (tail && tail->mNext) {
                tail = tail->mNext;
            }

            if (tail) {
                //  list has a tail
                //  append this node to the end of the list
                tail->mNext = new Node{ t, nullptr };
            } else {
                //  empty list
                //  append to head
                mHead = new Node{ t, nullptr };
            }

            ++mSize;
        }

        template <typename T>
        void List<T>::insert(T&& t)
        {
            Node* tail = mHead;

            //  find the tail of the list
            while (tail && tail->mNext) {
                tail = tail->mNext;
            }

            if (tail) {
                //  list has a tail
                //  append this node to the end of the list
                tail->mNext = new Node{ std::move(t), nullptr };
            } else {
                //  empty list
                //  append to head
                mHead = new Node{ std::move(t), nullptr };
            }

            ++mSize;
        }

        template <typename T>
        void List<T>::remove(const T& t)
        {
            Node* node = mHead;
            Node* prev = nullptr;

            while (node) {
                //  found?
                if (node->mData == t) {
                    if (prev) {
                        //  unlink from list, delete and decrease size of list
                        Node* next = node->mNext;
                        delete node;
                        node = nullptr;
                        prev->mNext = next;                     
                        --mSize;
                    } else {
                        //  remove head
                        //  decrease size of list
                        delete node;
                        node = nullptr;
                        mHead = nullptr;
                        --mSize;
                    }
                } else {
                    //  data not found
                    //  iterate to next node
                    prev = node;
                    node = node->mNext;
                }
            }
        }

        template<typename T>
        void List<T>::clear()
        {
            Node* node = mHead;
            while (node) {
                //  store the pointer to the next node
                Node* next = node->mNext;

                //  delete current node
                delete node;

                //  T's destructor could be set to noexcept(false) and throw
                //  could wrap "delete node" in a try/catch to suppress any exceptions
                //  and continue deleting the rest of the nodes else there could be leaked memory
                //

                //  iterate to next node
                node = next;
            }

            mHead = nullptr;
            mSize = 0;
        }
    }
}

#endif

Answer 1

Comment

Overall a very good piece of code.

I only spotted one bug (removing from the head).
In my opinion your code can be DRY'ed up in a couple of places, and the premature optimization in the assignment is unnecessary (but does not break anything).

The one thing I would note is to write self-documenting code. This means breaking functionality into small named functions. So rather than tracing all the code I can see what it is supposed to be doing by reading the name of the function call.

Rather than:

 Node<T>* next = mHead;
 while(next->mNext != nullptr) {
     next = next->mNext;
 }
 next->mNext = new Node(t);

I would split this into a function and write:

 Node<T>* next = getTailNode();
 next->mNext = new Node(t);

The intent of the code now becomes clear.

Basic Review

Why not use std::swap() to swap the members?

            friend void swap(List<T>& lhs, List<T>& rhs) noexcept
            {
                Node* tempHead(lhs.mHead);
                lhs.mHead = rhs.mHead;
                rhs.mHead = tempHead;

                std::size_t tempSize(lhs.mSize);
                lhs.mSize = rhs.mSize;
                rhs.mSize = tempSize;
            }

I would write like this:

            friend void swap(List<T>& lhs, List<T>& rhs) noexcept
            {
                using std::swap;
                swap(lhs.mHead, rhs.mHead);
                swap(lhs.mSize, rhs.mSize);
            }

When you are creating a list of a set size:

        //  custom constructor - create a list of N size
        template <typename T>
        List<T>::List(const std::size_t size)

What are in the members of the list? Currently you can only support types of T that are POD or default constructible. But if they are POD they are in an indeterminate state and reading them is UB. Personally, along with the size I would define a default value to place in each member (the default member can use a default value).

        template <typename T>
        List<T>::List(const std::size_t size, T const& defaultValue = T())

In this initializer (using the list)

        //  custom constructor - create a list populated with data
        template <typename T>
        List<T>::List(const std::initializer_list<T>& il)

There seems to be a lot of commonality with the first constructor. Can you DRY up the code a bit?

The same applies to the copy constructor. Also some of those comments are superfluous. You don't need to comment every line. Comments should be used to describe WHY the code is doing something (or a description and reference to an algorithm). Let the code describe HOW.

        template <typename T>
        List<T>::List(const List<T>& rhs)

This copy assignment works. But I don't see the need to test for self-assignment. The copy and swap idiom is safe to use in the presence of self-assignment.

You are looking at this as an optimization to prevent excessive copying. I look at this as pessimizing the most common case. Yes the pessimization is small, but self-assignment is exceedingly rare.

        template <typename T>
        List<T>& List<T>::operator=(const List<T>& rhs)
        {
            //  check for self assignment
            if (this != &rhs) {

                //  make a copy of rhs
                List<T> rhsCopy(rhs);

                //  swap
                using std::swap;
                swap(*this, rhsCopy);
            }

            return *this;
        }

Same comment on the move. Swap is self-assignment safe. Pessimization of the most common case for something that happens vanishingly rarely. It is much much worse here as the benefit of the test is vanishingly small (as a self-move is not that expensive, being a swap).

        template <typename T>
        List<T>& List<T>::operator=(List<T>&& rhs)
        {
            //  check for self move
            if (this != &rhs) {

                //  swap
                using std::swap;
                swap(*this, rhs);
            }

            return *this;
        }

You are wasting the benefits of the emplace here.

        template<typename T>
        template<typename ...Args>
        void List<T>::emplace(Args&&... args)
        {
            //  forward to the relevant insert
            insert(std::forward<Args>(args)...);
        }

You are basically creating an element that then needs to be copied into a node object. It would have been better to create a Node object directly then insert that into the list to prevent a copy.

In fact I would DRY up all the inserts to use an internal insert that is passed a pre-created Node object (as these two inserts are basically the same).

        template<typename ...Args>
        void List<T>::emplace(Args&&... args)
        {
            //  forward to the relevant insert
            doInsert(new Node(std::forward<Args>(args)...));  // Need a new node constructor 
        }

        void List<T>::insert(T const& val)
        {
            doInsert(new Node(val));
        }

        void List<T>::insert(T&& val)
        {
            doInsert(new Node(std::move(val))); // Need another node constructor.
        }

        void doInsert(Node<T>* ptr)
        {
            if (!mHead) {
                mHead = ptr;
            }
            else {
                Node<T>* tail = getTail();
                tail->mNext = ptr;
            }
        }

OK. This remove() can be vastly simplified. Also there is a definite bug in removing the head element, as you always assign nullptr to mHead.

        template <typename T>
        void List<T>::remove(const T& t)
        {
            Node* node = mHead;
            Node* prev = nullptr;

            while (node) {
                //  found?
                if (node->mData == t) {
                    if (prev) {
                        //  unlink from list, delete and decrease size of list
                        Node* next = node->mNext;
                        delete node;
                        node = nullptr;
                        prev->mNext = next;                     
                        --mSize;
                    } else {
                        //  remove head
                        //  decrease size of list
                        delete node;
                        node = nullptr;
                        mHead = nullptr;
                        --mSize;
                    }
                } else {
                    //  data not found
                    //  iterate to next node
                    prev = node;
                    node = node->mNext;
                }
            }
        }

An iterative simplification:

        void List<T>::remove(const T& t)
        {
            Node<T>* prev = nullptr;
            for(Node<T>* loop = mHead; loop != nullptr; prev = loop, loop = loop->mNext) {
                if (loop->mData == t) {
                    if (prev == nullptr) {
                         mHead = loop->mNext;
                    }
                    else {
                         prev->next = loop->mNext;
                    }
                    delete loop;
                    return;
                }
            }
        }

But I don't like that. Its still very chunky. Which is one reason I like use a sentinel value. If you use a sentinel value your code becomes vastly simplified as you don't have to special case the head and all those tests for nullptr simply vanish.

But I also like the recursive version (If I don't have a sentinel). Its not as clumsy or blocky as the iterative approach. An elegant solution... for a more civilized age.

            void List<T>::remove(const T& t)
            {
                mHead = doRemove(mHead, t);
            }
            void List<T>::doRemove(Node<T>* current, const T& t)
            {
                if (current == nullptr) {
                    return nullptr;
                }

                if (current->mData == t) {
                    Node<T>* result = current->mNext;
                    delete current;
                    return result;
                }

                current->mNext = doRemove(current->mNext, t);
                return current;
            }

How I usually implement swap

 class MyClass
 {
    public:
        void swap(MyClass& rhs) noexcept {
            using std::swap;
            // call swap on each member.
        }
        friend void swap(MyClass& lhs, MyClass& rhs) noexcept {
            lhs.swap(rhs);
        }
 };

Answer 2

First, about your points:

1. Separate move- and copy-assignment, instead of assignment from pass-by-value: Meh, the list class itself isn't big enough to worry about it, really, and when it gets inlined - it should - there shouldn't be a difference.

2. A potentially throwing dtor is in nearly every case pathological. Trying to deal with it in any useful way is a supremely frustrating exercise in futility.

3. Well, std::swap() uses the move-ctor, move-assignment, and the dtor. As your move-ctor is properly implemented with swap(a, b), what would you expect to happen if you didn't implement your own swap(a, b)? (As an aside, using std::swap; there isn't very sensible, and rings a big alarm for any reader.)

   Or are you referring to not using using std::swap; swap(x, y); in the implementation of your custom swap()? In that case, I really have to extol the value of conciseness and using the appropriate abstractions, all else being equal.

4. Nice to hear you will add iterator-support. Anyway, that will lead to a total re-design of: Copy-ctor, initializer_list-ctor, and .remove().

Now, other things:

5. In the definition of the template-class List<T>, you can refer to the current template-instantiation without mentioning the template-argument with a simple List.

6. Embrace auto. No checking required to know whether you remembered to use the right type, or fix it in hundreds of places when you decide to change it for any reason.

7. Personally, I always put the pointers before the data-member, but that may just be me.

8. Remember that you can make a pointer to any member, even if that is of pointer-type. This one point has to be applied over and over and over again, to remove lots of special cases and the concomittant duplication.

   Another way to achieve the same is using a sentinel. You have to take care with it to avoid a dummy T though, or any spurious additional allocation. Might want to move the pointer from the node into a base-class for that.

9. It's curious to implement the dtor in terms of .clear(), instead of the other way around. That might potentially lead to the former being less efficient due to favoring the latter, which is less than ideal...

10. Don't test for self-assignment. While self-copy-assignment must work, there's no need to pessimize the case that matters by going out of your way to optimize for an extreme edge-case.

11. Don't test for self-move-assignment. Nearly the same as for self-copy-assignment applies, though self-move-assignment is pathological, and you might want to stick an assert(this != &rhs); in there.

12. .emplace() should construct the value in-place, emplacing it. That's what it says on the tin.
    Aside from that, the two .insert()s should delegate to the single .emplace() for all the work, not the other way around, to reduce needless code-duplication.