Итераторы и элементы после последнего

#ifndef LIST_H
 
#define LIST_H
 
#pragma warning (disable : 4544)
 
#include <initializer_list>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <type_traits>
#include <tuple>
 
namespace my
{
//=============================================================================
// List
//=============================================================================
    namespace lst
    {
        template <typename T>
        struct List
        {
            T data = T();
            List* next = nullptr;
            List* prev = nullptr;
 
            //************************************
            List () = default;
 
            List (T t, List* n, List* p): data(t),
                                          next(n),
                                          prev(p)
            {  }
        };
    }
 
//=============================================================================
// Iterator
//=============================================================================
    template <typename T>
    class Iterator
    {
    private:
    // данные
        lst::List<T>* ptr = nullptr;
        bool endFlag = false;
 
    //**************************************
 
    public:
    // конструкторы
        Iterator () = default;
 
        Iterator (lst::List<T>* p, bool b = false): ptr(p),
                                                    endFlag(b)
        {  }
 
    // функции интерфейса
        std::pair<lst::List<T>*, bool> getInfo () const
        { return std::make_pair(ptr, endFlag); }
 
        Iterator& operator ++ ();
        Iterator operator ++ (int);
        Iterator& operator -- ();
        Iterator operator -- (int);
 
        T& operator * () const;
        T* operator -> () const;
 
        void swap (Iterator&);
    };
 
    ////////////////////////////////////
    // определение функций интерфейса
    template <typename T>
    Iterator<T>& Iterator<T>::operator ++ ()
    {
        if (!(ptr -> next) && endFlag)
            throw std::logic_error("increment on end iterator");
 
        if (!(ptr -> next))
            endFlag = true;
        else
            ptr = ptr -> next;
 
        return *this;
    }
 
    template <typename T>
    Iterator<T> Iterator<T>::operator ++ (int)
    {
        Iterator ret = *this;
        ++*this;
        return ret;
    }
 
    template <typename T>
    Iterator<T>& Iterator<T>::operator -- ()
    {
        if (!(ptr -> prev))
            throw std::logic_error("decrement on first iterator");
 
        if (endFlag)
            endFlag = false;
        else
            ptr = ptr -> prev;
 
        return *this;
    }
 
    template <typename T>
    Iterator<T> Iterator<T>::operator -- (int)
    {
        Iterator ret = *this;
        --*this;
        return ret;
    }
 
    template <typename T>
    T& Iterator<T>::operator * () const
    {
        if (endFlag)
            throw std::logic_error("dereference past end");
        return ptr -> data;
    }
 
    template <typename T>
    inline T* Iterator<T>::operator -> () const
    { return &(this -> operator *()); }
 
    template <typename T>
    void Iterator<T>::swap (Iterator& it)
    {
        using std::swap;
        swap(ptr, it.ptr);
        swap(endFlag, it.endFlag);
    }
 
    // определение внешних функций взаимодействующих с Iterator
    template <typename T>
    inline void swap (Iterator<T>& it1, Iterator<T>& it2)
    { it1.swap(it2); }
 
    template <typename T>
    inline bool operator == (Iterator<T> it1, Iterator<T> it2)
    { return it1.getInfo().first == it2.getInfo().first &&
             it1.getInfo().second == it2.getInfo().second; }
 
    template <typename T>
    inline bool operator != (Iterator<T> it1, Iterator<T> it2)
    { return !(it1 == it2); }
 
    template <typename T>
    bool operator < (Iterator<T> it1, Iterator<T> it2)
    {
        if (it1 != it2)
        {
            while (true)
            {
                if (it1.getInfo().second)
                    return false;
                ++it1;
                if (it1 == it2)
                    return true;
            }
        }
        return false;
    }
 
    template <typename T>
    inline bool operator > (Iterator<T> it1, Iterator<T> it2)
    { return it2 < it1; }
 
    template <typename T>
    inline bool operator <= (Iterator<T> it1, Iterator<T> it2)
    { return !(it2 < it1); }
 
    template <typename T>
    inline bool operator >= (Iterator<T> it1, Iterator<T> it2)
    { return !(it1 < it2); }
 
//=============================================================================
// Const_Iterator
//=============================================================================
    template <typename T>
    class Const_Iterator
    {
    private:
    // данные
        lst::List<T>* ptr = nullptr;
        bool endFlag = false;
 
    //*************************************
 
    public:
    // конструкторы
        Const_Iterator () = default;
 
        Const_Iterator (lst::List<T>* l, bool b = false): ptr(l),
                                                          endFlag(b)
        {  }
 
    // функции интерфейса
        std::pair<const lst::List<T>*, bool> getInfo () const
        { return std::make_pair(ptr, endFlag); }
 
        Const_Iterator& operator ++ ();
        Const_Iterator operator ++ (int);
        Const_Iterator& operator -- ();
        Const_Iterator operator -- (int);
 
        const T& operator * () const;
        const T* operator -> () const;
 
        void swap (Const_Iterator&);
    };
 
    /////////////////////////////////////
    // определение функций интерфейса
    template <typename T>
    Const_Iterator<T>& Const_Iterator<T>::operator ++ ()
    {
        if (!(ptr -> next) && endFlag)
            throw std::logic_error("increment on end iterator");
 
        if (!(ptr -> next))
            endFlag = true;
        else
            ptr = ptr -> next;
 
        return *this;
    }
 
    template <typename T>
    Const_Iterator<T> Const_Iterator<T>::operator ++ (int)
    {
        Const_Iterator ret = *this;
        ++*this;
        return ret;
    }
 
    template <typename T>
    Const_Iterator<T>& Const_Iterator<T>::operator -- ()
    {
        if (!(ptr -> prev))
            throw std::logic_error("decrement on first iterator");
 
        if (endFlag)
            endFlag = false;
        else
            ptr = ptr -> prev;
 
        return *this;
    }
 
    template <typename T>
    Const_Iterator<T> Const_Iterator<T>::operator -- (int)
    {
        Const_Iterator ret = *this;
        --*this;
        return ret;
    }
 
    template <typename T>
    const T& Const_Iterator<T>::operator * () const
    {
        if (endFlag)
            throw std::logic_error("dereference past end");
        return ptr -> data;
    }
 
    template <typename T>
    inline const T* Const_Iterator<T>::operator -> () const
    { return &(this -> operator *()); }
 
    template <typename T>
    void Const_Iterator<T>::swap (Const_Iterator& ci)
    {
        using std::swap;
        swap(ptr, ci.ptr);
        swap(endFlag, ci.endFlag);
    }
 
    // определение внешних функций взаимодействующих с Const_Iterator
    template <typename T>
    inline void swap (Const_Iterator<T>& ci1, Const_Iterator<T>& ci2)
    { ci1.swap(ci2); }
 
    template <typename T>
    inline bool operator == (Const_Iterator<T> ci1, Const_Iterator<T> ci2)
    { return ci1.getInfo().first == ci2.getInfo().first &&
             ci1.getInfo().second == ci2.getInfo().second; }
 
    template <typename T>
    inline bool operator != (Const_Iterator<T> ci1, Const_Iterator<T> ci2)
    { return !(ci1 == ci2); }
 
    template <typename T>
    bool operator < (Const_Iterator<T> ci1, Const_Iterator<T> ci2)
    {
        if (ci1 != ci2)
        {
            while (true)
            {
                if (ci1.getInfo().second)
                    return false;
                ++ci1;
                if (ci1 == ci2)
                    return true;
            }
        }
        return false;
    }
 
    template <typename T>
    inline bool operator > (Const_Iterator<T> ci1, Const_Iterator<T> ci2)
    { return ci2 < ci1; }
 
    template <typename T>
    inline bool operator <= (Const_Iterator<T> ci1, Const_Iterator<T> ci2)
    { return !(ci2 < ci1); }
 
    template <typename T>
    inline bool operator >= (Const_Iterator<T> ci1, Const_Iterator<T> ci2)
    { return !(ci1 < ci2); }

//=============================================================================
// List
//=============================================================================
    template <typename T>
    class List
    {
    private:
    // данные 
        lst::List<T>* frst = nullptr;
        lst::List<T>* lst = nullptr;
        size_t sz = 0;
 
    // функции реализации
        void free();
        std::pair<lst::List<T>*, size_t> getLastBeforeNullptr (lst::List<T>*) const;
        std::tuple<lst::List<T>*, lst::List<T>*, size_t> createSmallListN (size_t, const T&) const;
        void copyN(size_t, const T&);
 
        Iterator<T> insertDiapOrN (Iterator<T>,
                                   std::tuple<lst::List<T>*, lst::List<T>*, size_t>);
 
        template <typename Y>
        std::tuple<lst::List<T>*, lst::List<T>*, size_t> createSmallListDiap (Y, Y) const;
 
        template <typename Y>
        void copyDiap (Y, Y);
    //**********************************************
 
    public:
    // стандартный конструктор и функции управления копированием
        List () = default;
 
        List (const List&);
        List (List&&) noexcept;
        List& operator = (const List&);
        List& operator = (List&&) noexcept;
 
        ~List()
        { free(); }
 
    // другие конструкторы и операторы присваивания
        template <typename Y,
                  typename = typename std::enable_if<!(std::is_integral<Y>::value)>::type>
        List (Y, Y);
 
        List (std::initializer_list<T>);
        List (size_t, const T& = T());
        List& operator = (std::initializer_list<T>);
 
    // функции присваивания и обмена
        template <typename Y,
                  typename = typename std::enable_if<!(std::is_integral<Y>::value)>::type>
        void assign (Y, Y);
 
        void assign (size_t, const T& = T());
        void assign (std::initializer_list<T>);
 
        void swap (List&);
 
    // функции доступа к элементам
        Iterator<T> begin ()
        { return Iterator<T>(frst); }
 
        Const_Iterator<T> begin () const
        { return Const_Iterator<T>(frst); }
 
        Const_Iterator<T> cbegin () const
        { return Const_Iterator<T>(frst); }
 
        Iterator<T> end ()
        { return Iterator<T>(lst, true); }
 
        Const_Iterator<T> end () const
        { return Const_Iterator<T>(lst, true); }
 
        Const_Iterator<T> cend () const
        { return Const_Iterator<T>(lst, true); }
 
        T& front ();
        const T& front () const;
        T& back ();
        const T& back () const;
 
    // функции связанные с размером
        bool empty () const
        { return !sz; }
 
        size_t size () const
        { return sz; }
 
        void resize(size_t, const T& = T());
 
    // функции добавления элементов
        void push_back (const T&);
        void push_front (const T&);
 
        Iterator<T> insert (Iterator<T>, const T&);
        Iterator<T> insert (Iterator<T>, size_t, const T&);
        Iterator<T> insert (Iterator<T>, std::initializer_list<T>);
 
        template <typename Y,
                  typename = typename std::enable_if<!(std::is_integral<Y>::value)>::type>
        Iterator<T> insert (Iterator<T>, Y, Y);
 
        template <typename ... Args>
        void emplace_front (Args&&...);
 
        template <typename ... Args>
        void emplace_back (Args&&...);
 
        template <typename ... Args>
        Iterator<T> emplace (Iterator<T>, Args&&...);
 
    // функции удаления элементов
        void pop_back ();
        void pop_front ();
 
        Iterator<T> erase (Iterator<T>);
        Iterator<T> erase (Iterator<T>, Iterator<T>);
 
        void clear ()
        { free(); }
    };
 
    ///////////////////////////////////////////////
    // определение функций реализации
    template <typename T>
    void List<T>::free ()
    {
        if (sz)
        {
            while (frst)
            {
                auto cur = frst -> next;
                delete frst;
                frst = cur;
            }
 
            sz = 0;
        }
    }
 
    template <typename T>
    std::pair<lst::List<T>*, size_t> List<T>::getLastBeforeNullptr (lst::List<T>* ptr) const
    {
        size_t cnt = 0;
        if (ptr)
        {
            while (ptr -> next)
            {
                ptr = ptr -> next;
                ++cnt;
            }
            ++cnt;
        }
        return std::make_pair(ptr, cnt);
    }
 
    template <typename T>
    std::tuple<lst::List<T>*, lst::List<T>*, size_t>
    List<T>::createSmallListN (size_t n, const T& t) const
    {
        lst::List<T>* ret = nullptr;
        while (n)
        {
            auto newList = new lst::List<T>();
            newList -> data = t;
 
            if (!ret)
                ret = newList;
            else
            {
                ret -> prev = newList;
                newList -> next = ret;
                ret = newList;
            }
 
            --n;
        }
 
        auto pr = getLastBeforeNullptr(ret);
        return std::make_tuple(ret, pr.first, pr.second);
    }
 
    template <typename T>
    template <typename Y>
    std::tuple<lst::List<T>*, lst::List<T>*, size_t>
    List<T>::createSmallListDiap (Y a, Y b) const
    {
        lst::List<T>* ret = nullptr;
        while (a != b)
        {
            auto newList = new lst::List<T>();
            newList -> data = *a;
 
            if (!ret)
                ret = newList;
            else
            {
                auto pr = getLastBeforeNullptr(ret);
                pr.first -> next = newList;
                newList -> prev = pr.first;
            }
 
            ++a;
        }
 
        auto pr = getLastBeforeNullptr(ret);
        return std::make_tuple(ret, pr.first, pr.second);
    }
 
    template <typename T>
    void List<T>::copyN (size_t n, const T& t)
    {
        auto tup = createSmallListN(n, t);
        frst = std::get<0>(tup);
        lst = std::get<1>(tup);
        sz = std::get<2>(tup);
    }
 
    template <typename T>
    template <typename Y>
    void List<T>::copyDiap (Y a, Y b)
    {
        auto tup = createSmallListDiap(a, b);
        frst = std::get<0>(tup);
        lst = std::get<1>(tup);
        sz = std::get<2>(tup);
    }
 
    template <typename T>
    Iterator<T> List<T>::insertDiapOrN (Iterator<T> it, 
                                        std::tuple<lst::List<T>*, lst::List<T>*, size_t> tup)
    {
        if (!(std::get<2>(tup)))
            return it;
 
        if (!(it.getInfo().first -> prev))
        {
            std::get<1>(tup) -> next = frst;
            frst -> prev = std::get<1>(tup);
            frst = std::get<0>(tup);
        }
        else if (it.getInfo().second)
        {
            lst -> next = std::get<0>(tup);
            std::get<0>(tup) -> prev = lst;
            lst = std::get<1>(tup);
        }
        else
        {
            std::get<1>(tup) -> next = it.getInfo().first;
            std::get<0>(tup) -> prev = it.getInfo().first -> prev;
            auto tmp = it.getInfo().first -> prev;
            it.getInfo().first -> prev = std::get<1>(tup);
            tmp -> next = std::get<0>(tup);
        }
 
        sz += std::get<2>(tup);
        return Iterator<T>(std::get<1>(tup));
    }
 
    // определение функций управления копированием
    template <typename T>
    inline List<T>::List (const List& l)
    { copyDiap(l.cbegin(), l.cend()); }
 
    template <typename T>
    inline List<T>::List (List&& l) noexcept: frst(l.frst),
                                              lst(l.lst),
                                              sz(l.sz)
    { l.frst = l.lst = nullptr; }
 
    template <typename T>
    List<T>& List<T>::operator = (const List& l)
    {
        if (this != &l)
        {
            free();
            copyDiap(l.cbegin(), l.cend());
        }
        return *this;
    }
 
    template <typename T>
    List<T>& List<T>::operator = (List&& l) noexcept
    {
        if (this != &l)
        {
            free();
            frst = l.frst;
            lst = l.lst;
            sz = l.sz;
            l.frst = l.lst = nullptr;
        }
        return *this;
    }
 
    // определение других конструкторов и операторов присваивания
    template <typename T>
    template <typename Y,
              typename = typename std::enable_if<!(std::is_integral<Y>::value)>::type>
    inline List<T>::List (Y a, Y b)
    { copyDiap(a, b); }
 
    template <typename T>
    inline List<T>::List (std::initializer_list<T> il)
    { copyDiap(il.begin(), il.end()); }
 
    template <typename T>
    inline List<T>::List (size_t n, const T& t = T())
    { copyN(n, t); }
 
    template <typename T>
    List<T>& List<T>::operator = (std::initializer_list<T> il)
    {
        free();
        copyDiap(il.begin(), il.end());
        return *this;
    }
 
    // определение функций присваивания и обмена
    template <typename T>
    void List<T>::swap (List& l)
    {
        using std::swap;
        swap(frst, l.frst);
        swap(lst, l.lst);
        swap(sz, l.sz);
    }
 
    template <typename T>
    template <typename Y,
              typename = typename std::enable_if<!(std::is_integral<Y>::value)>::type>
    inline void List<T>::assign (Y a, Y b)
    { copyDiap(a, b); }
 
    template <typename T>
    inline void List<T>::assign (std::initializer_list<T> il)
    { copyDiap(il.begin(), il.end()); }
 
    template <typename T>
    inline void List<T>::assign (size_t n, const T& t = T())
    { copyN(n, t); }
 
    // определение функций доступа к элементам
    template <typename T>
    T& List<T>::front ()
    {
        if (empty())
            throw std::logic_error("front on empty List");
        return frst -> data;
    }
 
    template <typename T>
    const T& List<T>::front () const
    {
        if (empty())
            throw std::logic_error("front on empty List");
        return frst -> data;
    }
 
    template <typename T>
    T& List<T>::back ()
    {
        if (empty())
            throw std::logic_error("back on empty List");
        return lst -> data;
    }
 
    template <typename T>
    const T& List<T>::back () const
    {
        if (empty())
            throw std::logic_error("back on empty List");
        return lst -> data;
    }
 
    // определение функций связанных с размером
    template <typename T>
    void List<T>::resize (size_t n, const T& t = T())
    {
        if (n < size())
        {
            while (size() != n)
                pop_back();
        }
        else if (n > size())
        {
            while (size() != n)
                push_back(t);
        }
    }
 
    // определение функций добавления элементов
    template <typename T>
    void List<T>::push_back (const T& t)
    {
        auto newList = new lst::List<T>();
        newList -> data = t;
        lst -> next = newList;
        newList -> prev = lst;
        lst = newList;
        ++sz;
    }
 
    template <typename T>
    void List<T>::push_front (const T& t)
    {
        auto newList = new lst::List<T>();
        newList -> data = t;
        newList -> next = frst;
        frst -> prev = newList;
        frst = newList;
        ++sz;
    }
 
    template <typename T>
    inline Iterator<T> List<T>::insert (Iterator<T> it, const T& t)
    { return insertDiapOrN(it, createSmallListN(1, t)); }
 
    template <typename T>
    inline Iterator<T> List<T>::insert (Iterator<T> it, size_t n, const T& t)
    { return insertDiapOrN(it, createSmallListN(n, t)); }
 
    template <typename T>
    inline Iterator<T> List<T>::insert (Iterator<T> it, std::initializer_list<T> il)
    { return insertDiapOrN(it, createSmallListDiap(il.begin(), il.end())); }
 
    template <typename T>
    template <typename Y,
              typename = typename std::enable_if<!(std::is_integral<Y>::value)>::type>
    inline Iterator<T> List<T>::insert (Iterator<T> it, Y a, Y b)
    { return insertDiapOrN(it, createSmallListDiap(a, b)); }
 
    template <typename T>
    template <typename ... Args>
    inline void List<T>::emplace_front (Args&&... args)
    { push_front(T(std::forward<Args>(args)...)); }
 
    template <typename T>
    template <typename ... Args>
    inline void List<T>::emplace_back (Args&&... args)
    { push_back(T(std::forward<Args>(args)...)); }
 
    template <typename T>
    template <typename ... Args>
    inline Iterator<T> List<T>::emplace (Iterator<T> it, Args&& ... args)
    { return insertDiapOrN(it, createSmallListN(1, T(std::forward<Args>(args)...))); }
 
    // определение функций удаления элементов
    template <typename T>
    void List<T>::pop_back ()
    {
        if (empty())
            throw std::logic_error("pop_back on empty List");
 
        auto tmp = lst -> prev;
        delete tmp -> next;
        lst = tmp;
        lst -> next = nullptr;
        --sz;
    }
 
    template <typename T>
    void List<T>::pop_front ()
    {
        if (empty())
            throw std::logic_error("pop_front on empty List");
 
        auto tmp = frst -> next;
        delete frst;
        frst = tmp;
        frst -> prev = nullptr;
        --sz;
    }
 
    template <typename T>
    Iterator<T> List<T>::erase (Iterator<T> it)
    {
        if (it.getInfo().second)
            throw std::logic_error("erase on empty List");
 
        if (!(it.getInfo().first -> prev))
        {
            pop_front();
            it = Iterator<T>(frst);
        }
        else if (!(it.getInfo().first -> next))
        {
            pop_back();
            it = Iterator<T>(lst, true);
        }
        else
        {
            auto up = it.getInfo().first -> prev;
            auto down = it.getInfo().first -> next;
            delete it.getInfo().first;
            up -> next = down;
            down -> prev = up;
 
            --sz;
 
            it = Iterator<T>(down);
        }
        return it;
    }
 
    template <typename T>
    Iterator<T> List<T>::erase (Iterator<T> it1, Iterator<T> it2)
    {
        if (it1.getInfo().first == frst)
        {
            while (frst != it2.getInfo().first)
                pop_front();
            return frst;
        }
        else if (it2.getInfo().second)
        {
            while (lst != it1.getInfo().first)
                pop_back();
            return Iterator<T>(lst, true);
        }
        else
        {
            while (it1 != it2)
                it1 = erase(it1);
            return it1;
        }
        return Iterator<T>();
    }
 
    // определение внешних функций взаимодействующих с List
    template <typename T>
    inline void swap (List<T>& l1, List<T>& l2)
    { l1.swap(l2); }
 
    template <typename T>
    bool operator == (const List<T>& l1, const List<T>& l2)
    {
        if (l1.size() == l2.size())
            return std::equal(l1.cbegin(), l1.cend(), l2.cbegin());
        return false;
    }
 
    template <typename T>
    inline bool operator != (const List<T>& l1, const List<T>& l2)
    { return !(l1 == l2); }
 
    template <typename T>
    inline bool operator < (const List<T>& l1, const List<T>& l2)
    { return std::lexicographical_compare(l1.cbegin(), l1.cend(), l2.cbegin(), l2.cend()); }
 
    template <typename T>
    inline bool operator > (const List<T>& l1, const List<T>& l2)
    { return l2 < l1; }
 
    template <typename T>
    inline bool operator <= (const List<T>& l1, const List<T>& l2)
    { return !(l2 < l1); }
 
    template <typename T>
    inline bool operator >= (const List<T>& l1, const List<T>& l2)
    { return !(l1 < l2); }
}
 
#endif