5
\$\begingroup\$

I have written Forward List in c++ for learning purpose. There are a few things to be added yet, but do you have any thoughts on the code as for now?

ForwardList.h

#pragma once

#include <assert.h>
#include <iterator>
#include <type_traits>

namespace PrimLibrary
{
    // base node - used as before head node
    template <class T>
    struct ForwardList_NodeBase
    {
        ForwardList_NodeBase* next;

        ForwardList_NodeBase(ForwardList_NodeBase* _next = nullptr) :
            next{ _next }
        {

        }
    };

    template <class T>
    struct ForwardList_Node : public ForwardList_NodeBase<T>
    {
        T data;

        ForwardList_Node(const T& _data, ForwardList_Node* _next = nullptr) :
            ForwardList_NodeBase{ _next },
            data{ _data }
        {

        }
    };

    template <class T, class UnqualifiedType = std::remove_cv_t<T>>
    class ForwardListIterator : public std::iterator<std::forward_iterator_tag, UnqualifiedType, std::ptrdiff_t, T*, T&>
    {
    public:

        explicit ForwardListIterator(ForwardList_NodeBase<UnqualifiedType>* node) :
            _itr{ node }
        {

        }

        ForwardListIterator(const ForwardListIterator&) = default;
        ForwardListIterator(const ForwardListIterator&& rhs) noexcept :
        _itr{ rhs._itr }
        {
            rhs._itr = nullptr;
        }

        ForwardListIterator& operator=(const ForwardListIterator& rhs)
        {
            _itr = rhs._itr;
            return *this;
        }

        ForwardListIterator& operator=(const ForwardListIterator&& rhs) noexcept
        {
            std::swap(_itr, rhs._itr);
            return *this;
        }


        ForwardListIterator& operator++()
        {
            assert(_itr != nullptr && "Iterator out-of-bounds.");
            _itr = static_cast<ForwardList_Node<UnqualifiedType>*>(_itr)->next;
            return *this;
        }

        ForwardListIterator& operator++(int)
        {
            assert(_itr != nullptr && "Iterator out-of-bounds.");
            auto tmp(*this);
            _itr = static_cast<ForwardList_Node<UnqualifiedType>*>(_itr)->next;
            return *this;
        }

        T& operator*() const
        {
            assert(_itr != nullptr && "Iterator out-of-bounds.");
            return static_cast<ForwardList_Node<UnqualifiedType>*>(_itr)->data;
        }

        T& operator->() const
        {
            assert(_itr != nullptr && "Iterator out-of-bounds.");
            return static_cast<ForwardList_Node<UnqualifiedType>*>(_itr)->data;
        }

        bool operator==(const ForwardListIterator& rhs) const
        {
            return _itr == rhs._itr;
        }

        bool operator!=(const ForwardListIterator& rhs) const
        {
            return !(*this == rhs);
        }

        ForwardList_NodeBase<UnqualifiedType>* getNode() const
        {
            return _itr;
        }


    private:
        ForwardList_NodeBase<UnqualifiedType>* _itr;
    };

    template <class T>
    class ForwardList
    {

    public:

        using iterator = ForwardListIterator<T>;
        using const_iterator = ForwardListIterator<const T>;

        ForwardList();
        ~ForwardList();

        ForwardList(std::initializer_list<T> il);

        template<class InputIterator>
        ForwardList(InputIterator begin, InputIterator end);

        ForwardList(const ForwardList& rhs);
        ForwardList(ForwardList&& rhs) noexcept;

        ForwardList& operator=(const ForwardList& rhs);
        ForwardList& operator=(ForwardList&& rhs) noexcept;


        // TODO: operator override;
        // TODO: additional modifiers

        T& front() { assert(_beforeBegin.next != nullptr && "No data to get - empty list"); return static_cast<ForwardList_Node<T>*>(_beforeBegin.next)->data; }
        const T& front() const { assert(_beforeBegin.next != nullptr && "No data to get - empty list");  return static_cast<ForwardList_Node<T>*>(_beforeBegin.next)->data; }

        // Iterators
        iterator begin() { return iterator{ _beforeBegin.next }; }
        iterator end() { return iterator{ nullptr }; }

        const_iterator begin() const { return const_iterator{ _beforeBegin.next }; }
        const_iterator end() const { return const_iterator{ nullptr }; }

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

        iterator before_begin() { return iterator{ &_beforeBegin }; }
        const_iterator before_begin() const { return const_iterator{ &_beforeBegin }; }
        const_iterator cbefore_begin() const { return before_begin(); }

        bool empty() const noexcept { return _beforeBegin.next == nullptr; }

        // Modifiers
        void push_front(const T& value);
        void push_front(std::initializer_list<T> il);

        void push_back(const T& value);
        void push_back(std::initializer_list<T> il);

        void push_after(const T& value, iterator itr);
        void push_after(std::initializer_list<T> il, iterator itr);

        template <class InputIterator>
        void push_after(iterator itr, InputIterator begin, InputIterator end);

        void pop_front();

        void remove(const T& value);

        template<class Comparator>
        void remove_if(Comparator cmp);

        void erase_after(iterator itr); // (itr, itr+1]
        void erase_after(iterator begin, iterator end); // (begin, end)
        void clear();

        void swap(ForwardList& other);

        void splice_after(iterator position, ForwardList& other);
        void splice_after(iterator position, ForwardList& other, iterator otherIt);
        void splice_after(iterator position, ForwardList& other, iterator otherBegin, iterator otherEnd);

    private:
        ForwardList_NodeBase<T> _beforeBegin;
        ForwardList_NodeBase<T>* _back; // for quick pushback
    };

    template<class T>
    bool operator==(const ForwardList<T>& lhs, const ForwardList<T>& rhs)
    {
        auto lhsIt = lhs.begin();
        auto rhsIt = rhs.begin();

        const auto lhsEnd = lhs.end();
        const auto rhsEnd = rhs.end();

        for (;lhsIt != lhsEnd && rhsIt != rhsEnd; ++lhsIt, ++rhsIt)
        {
            if (*lhsIt != *rhsIt)
            {
                return false;
            }
        }

        // lists have different sizes
        if (lhsIt != lhsEnd || rhsIt != rhsEnd)
        {
            return false;
        }

        return true;
    }

    template<class T>
    bool operator!=(const ForwardList<T>& lhs, const ForwardList<T>& rhs)
    {
        return !(lhs == rhs);
    }
}

ForwardList.cpp

#include "ForwardList.h"

namespace PrimLibrary
{
    template <class T>
    ForwardList<T>::ForwardList() :
        _back{ nullptr }
    {

    }

    template<class T>
    ForwardList<T>::~ForwardList()
    {
        clear();
    }

    template<class T>
    ForwardList<T>::ForwardList(std::initializer_list<T> il) :
        _back{ nullptr }
    {
        ForwardList_NodeBase<T>* lastNewNode = &_beforeBegin;

        for (const T& value : il)
        {
            ForwardList_NodeBase<T>* newNode = new ForwardList_Node<T>{ value };
            lastNewNode->next = newNode;
            lastNewNode = newNode;
        }

        _back = lastNewNode;
    }

    template<class T>
    template<class InputIterator>
    ForwardList<T>::ForwardList(InputIterator begin, InputIterator end) :
        _back{ nullptr }
    {
        ForwardList_NodeBase<T>* lastNewNode = &_beforeBegin;

        while (begin != end)
        {
            ForwardList_NodeBase<T>* newNode = new ForwardList_Node<T>{ *begin };
            lastNewNode->next = newNode;
            lastNewNode = newNode;

            ++begin;
        }

        _back = lastNewNode;
    }

    template<class T>
    ForwardList<T>::ForwardList(const ForwardList& rhs) :
        _back{ nullptr }
    {
        for (const T& nodeData : rhs)
        {
            push_back(nodeData);
        }
    }

    template<class T>
    ForwardList<T>::ForwardList(ForwardList &&rhs) noexcept :
        _back{ nullptr }
    {
        std::swap(_beforeBegin, rhs._beforeBegin);
        std::swap(_back, rhs._back);
    }

    template<class T>
    ForwardList<T>& ForwardList<T>::operator=(const ForwardList & rhs)
    {
        ForwardList safeCopy{ rhs };
        std::swap(*this, safeCopy);
        return *this;
    }

    template<class T>
    ForwardList<T>& ForwardList<T>::operator=(ForwardList && rhs) noexcept
    {
        std::swap(_beforeBegin, rhs._beforeBegin);
        std::swap(_back, rhs._back);
        return *this;
    }

    template<class T>
    void ForwardList<T>::push_front(const T& value)
    {
        ForwardList_NodeBase<T>* newFront = new ForwardList_Node<T>{ value };
        if (_beforeBegin.next == nullptr)
        {
            _beforeBegin.next = _back = newFront;
        }
        else
        {
            newFront->next = _beforeBegin.next;
            _beforeBegin.next = newFront;
        }
    }

    template<class T>
    void ForwardList<T>::push_front(std::initializer_list<T> il)
    {
        ForwardList_NodeBase<T>* firstAfterPush = _beforeBegin.next;
        ForwardList_NodeBase<T>* lastNewNode = &_beforeBegin;

        for (const T& value : il)
        {
            ForwardList_NodeBase<T>* newNode = new ForwardList_Node<T>{ value };
            lastNewNode->next = newNode;
            lastNewNode = newNode;
        }

        if (firstAfterPush == nullptr)
        {
            _back = lastNewNode;
        }
        else
        {
            lastNewNode->next = firstAfterPush;
        }
    }

    template<class T>
    void ForwardList<T>::push_back(const T& value)
    {
        ForwardList_NodeBase<T>* newBack = new ForwardList_Node<T>{ value,  nullptr };

        if (_beforeBegin.next == nullptr)
        {
            _beforeBegin.next = _back = newBack;
        }
        else
        {
            _back->next = newBack;
            _back = newBack;
        }
    }

    template<class T>
    void ForwardList<T>::push_back(std::initializer_list<T> il)
    {
        ForwardList_NodeBase<T>* lastNewNode = _back ? _back : &_beforeBegin;

        for (const T& value : il)
        {
            ForwardList_NodeBase<T>* newNode = new ForwardList_Node<T>{ value };
            lastNewNode->next = newNode;
            lastNewNode = newNode;
        }

        _back = lastNewNode;
    }

    template<class T>
    void ForwardList<T>::push_after(const T& value, iterator itr)
    {
        ForwardList_NodeBase<T>* newBack = new ForwardList_Node<T>(value);
        newBack->next = itr.getNode()->next;
        itr.getNode()->next = newBack;
    }

    template<class T>
    void ForwardList<T>::push_after(std::initializer_list<T> il, iterator itr)
    {
        assert(itr.getNode() != nullptr && "Iterator out of bounds");

        ForwardList_NodeBase<T>* firstAfterPush = itr.getNode()->next;
        ForwardList_NodeBase<T>* lastNewNode = itr.getNode();

        for (const T& value : il)
        {
            ForwardList_NodeBase<T>* newNode = new ForwardList_Node<T>{ value };
            lastNewNode->next = newNode;
            lastNewNode = newNode;
        }

        if (firstAfterPush == nullptr)
        {
            _back = firstAfterPush;
        }
        else
        {
            lastNewNode->next = firstAfterPush;
        }
    }

    template<class T>
    template<class InputIterator>
    void ForwardList<T>::push_after(iterator itr, InputIterator begin, InputIterator end)
    {
        ForwardList_NodeBase<T>* firstAfterPush = itr.getNode()->next;
        ForwardList_NodeBase<T>* lastNewNode = itr.getNode();

        while (begin != end)
        {
            ForwardList_NodeBase<T>* newNode = new ForwardList_Node<T>{ *begin };
            lastNewNode->next = newNode;
            lastNewNode = newNode;
            ++begin;
        }

        if (firstAfterPush == nullptr)
        {
            _back = firstAfterPush;
        }
        else
        {
            lastNewNode->next = firstAfterPush;
        }
    }

    template<class T>
    void ForwardList<T>::pop_front()
    {
        if (_beforeBegin.next)
        {
            ForwardList_NodeBase<T>* oldFront = _beforeBegin.next;
            _beforeBegin.next = oldFront->next;
            delete oldFront;

            // do i need this? we wont be accessing back when front is nullptr
            if (_beforeBegin.next == nullptr)
            {
                _back = nullptr;
            }
        }
    }

    template<class T>
    void ForwardList<T>::remove(const T& value)
    {
        ForwardList_NodeBase<T>* previous = &_beforeBegin;
        while (previous->next != nullptr)
        {
            ForwardList_Node<T>* current = static_cast<ForwardList_Node<T>*>(previous->next);
            if (current->data == value)
            {
                previous->next = current->next;
                delete current;
                current = nullptr;
            }
            else
            {
                previous = current;
            }
        } 

        // in case last element was removed
        _back = previous;
    }


    template<class T>
    template<class Comparator>
    void ForwardList<T>::remove_if(Comparator cmp)
    {
        ForwardList_NodeBase<T>* previous = &_beforeBegin;
        while (previous->next != nullptr)
        {
            ForwardList_Node<T>* current = static_cast<ForwardList_Node<T>*>(previous->next);
            if (cmp(current->data))
            {
                previous->next = current->next;
                delete current;
                current = nullptr;
            }
            else
            {
                previous = current;
            }
        }

        // in case last element was removed
        _back = previous;
    }

    template<class T>
    void ForwardList<T>::erase_after(iterator itr)
    {
        assert(itr.getNode()->next != nullptr);
        ForwardList_NodeBase<T>* toPop = itr.getNode()->next;
        itr.getNode()->next = toPop->next;
        delete toPop;

        if (itr.getNode()->next == nullptr)
        {
            _back = itr.getNode();
        }
    }

    template<class T>
    void ForwardList<T>::erase_after(iterator begin, iterator end)
    {
        ForwardList_NodeBase<T>* current = begin.getNode()->next;
        while (current != end.getNode())
        {
            auto tmp = current->next;
            delete current;
            current = tmp;
        }

        begin.getNode()->next = end.getNode();
    }

    template<class T>
    void ForwardList<T>::clear()
    {
        while (!empty())
        {
            pop_front();
        }
    }
    template<class T>
    void ForwardList<T>::swap(ForwardList &other)
    {
        std::swap(_beforeBegin.next, other._beforeBegin.next);
        std::swap(_back, other._back);
    }

    template<class T>
    void ForwardList<T>::splice_after(iterator position, ForwardList& other)
    {
        ForwardList_NodeBase<T>* firstAfterPush = position.getNode()->next;

        position.getNode()->next = other._beforeBegin.next;
        other._back->next = firstAfterPush;

        if (firstAfterPush == nullptr)
        {
            _back = other._back;
        }

        other._beforeBegin.next = other._back = nullptr;
    }

    template<class T>
    void ForwardList<T>::splice_after(iterator position, ForwardList & other, iterator otherIt) // range (otherIt, ++otherIt]
    {
        ForwardList_NodeBase<T>* firstAfterPush = position.getNode()->next;
        ForwardList_NodeBase<T>* nodeToMove = otherIt.getNode()->next;

        otherIt.getNode()->next = nodeToMove->next;

        position.getNode()->next = nodeToMove;
        nodeToMove->next = firstAfterPush;

        if (firstAfterPush == nullptr)
        {
            _back = nodeToMove;
        }
    }
    template<class T>
    void ForwardList<T>::splice_after(iterator position, ForwardList & other, iterator otherBegin, iterator otherEnd) // (otherBegin, otherLast) range
    {
        ForwardList_NodeBase<T>* firstAfterPush = position.getNode()->next;

        position.getNode()->next = otherBegin.getNode()->next;

        iterator lastNodeToMove{ otherBegin };
        while (lastNodeToMove.getNode()->next != otherEnd.getNode())
        {
            ++lastNodeToMove;
        }
        lastNodeToMove.getNode()->next = firstAfterPush;

        if(firstAfterPush == nullptr)
        {
            _back = otherBegin.getNode();
        }

        otherBegin.getNode()->next = otherEnd.getNode();
    }
}
\$\endgroup\$
  • \$\begingroup\$ You'll get linker errors with current file management. \$\endgroup\$ – Incomputable Sep 5 '17 at 19:27
  • \$\begingroup\$ @Incomputable thanks, so I guess I should have left the implementation in the header file. \$\endgroup\$ – Dawid Wdowiak Sep 5 '17 at 19:42
2
\$\begingroup\$

A few comments (on top of the obvious file management issue mentioned in the comments):

  1. I would switch to std::unique_ptr<> instead of raw pointers and new/delete.

  2. I'm not sure I see the purpose of ForwardList_NodeBase. Why not just have a pointer to ForwardList_Node as the head? You could also get rid of all these nasty static_cast<> if you did that.

  3. Since you have a push_back(), I would have added a pop_back() for API consistency, even if it would be slow.

  4. You have a bunch of _beforeBegin.next == nullptr in the code, yet you use empty() in a few places. Be consistent! (empty() is much better)

  5. Avoid putting multiple statements on the same line (see T& front()), it makes debugging a pain. It also makes your code lines too long.

  6. I would be in favor of nulling out _back when the list becomes empty, even if you have an invariant protecting it. Ask yourself: "Why is it initialized to null at construction?". Keeping dangling pointers around is never good.

  7. ForwardList_Node and ForwardListIterator should be in a sub-namespace to avoid poluting the user-facing one. It's also nice for people who use IDEs with code completion.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your insight. 2. Was thinking of using just ForwardList_Node as the head, but since it is singly-likned list I wanted to have before_head node for methods like splice_after since it takes preceding iterator to the node that will be moved. \$\endgroup\$ – Dawid Wdowiak Sep 6 '17 at 8:33

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.