#include <memory>
#include <cstddef>

template<typename Value,
         typename Alloc = std::allocator<Value>>
struct ListAlloc
{
    using base = ListAlloc;

    using allocator_type = Alloc;
	using allocator_traits = std::allocator_traits<allocator_type>;

	#define takeover( N ) using N = typename allocator_traits::N;

	takeover(value_type)

	typedef value_type& reference;
	typedef value_type const& const_reference;

	takeover(pointer)
	takeover(const_pointer)

	takeover(difference_type)
	takeover(size_type)

	#undef takeover

	allocator_type mAllocator;

	ListAlloc( allocator_type const& alloc = allocator_type{} ):
	    mAllocator{alloc} {}

// ///////////////////////////////////////////////////////////////////////////////////////////

	struct Node
	{
		Node *prev,
		     *next;

		pointer data;

		Node( Node* prev, Node* next, pointer data = nullptr ) noexcept :
			prev{prev},
			next{next},
			data{data} {}

		Node() noexcept :
			Node{nullptr, nullptr} {} // No increment (delegate ctor)
	};

    void _alloc_destroy_node( Node* ptr )
    {
        allocator_traits::destroy( mAllocator, ptr->data );
        allocator_traits::deallocate( mAllocator, ptr->data, 1 );
        delete ptr;
    }

	void _alloc_destroy_all_prev( Node* ptr )
    {
        delete ptr->next; // Ist ptr der letzte Knoten, dann ist ptr->next 0. Sonst wird der nächste das end()-Äquivalent sein.

        Node* old_ptr;
		while( ptr )
		{
			old_ptr = ptr;
			ptr = ptr->prev;
			_alloc_destroy_node(old_ptr);
		}
	}

private:
    template<typename Func>
    std::pair<Node*, Node*> _alloc_create_impl( size_type n, Func constructor )
    {
		Node* ptr = new Node;
		Node* const rval = ptr;

		while( n-- )
		{
		    bool constructed = false;
			try
			{
                ptr->data = allocator_traits::allocate( mAllocator, 1 );

                constructor( ptr->data );

				constructed = true;

                ptr->next = new Node{ptr, nullptr};
			}
			catch(...)
			{
                if( constructed )
                    allocator_traits::destroy( mAllocator, ptr->data );

			    if( ptr->data )
                    allocator_traits::deallocate( mAllocator, ptr->data, 1 );

				ptr = ptr->prev;
				_alloc_destroy_all_prev( ptr );

				throw;
			}

			auto old_ptr = ptr;
			ptr = ptr->next;
			ptr->prev = old_ptr;
		}

		return {rval, ptr};
    }

public:
	std::pair<Node*, Node*> _alloc_fill_n( size_type n )
	{
	    return _alloc_create_impl( n, [&](pointer p){ allocator_traits::construct( mAllocator, p ); } );
	}

	std::pair<Node*, Node*> _alloc_fill_n( size_type n, const_pointer value )
	{
        return _alloc_create_impl( n, [&](pointer p){ allocator_traits::construct( mAllocator, p, *value ); } );
	}

    template<typename InputIterator>
    std::pair<Node*, Node*> _alloc_copy( size_type n, InputIterator first )
    {
        return _alloc_create_impl( n, [&]( pointer p ){ allocator_traits::construct( mAllocator, p, *first++ ); } );
    }

// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    void _alloc_swap( allocator_type& lhs, allocator_type& rhs, std::true_type )
    { std::swap(lhs, rhs); }
    void _alloc_swap( allocator_type&, allocator_type&, std::false_type )
    {}

    allocator_type get_allocator() const { return mAllocator; }

    size_type max_size() const { return allocator_traits::max_size(mAllocator); }
};

#include <type_traits>

/// Geborgt von camper - verzeih'
#define TAG_CHECK(It, ItTag) \
           ,typename std::enable_if<std::is_convertible< \
                 typename std::conditional<std::is_class<It>::value || std::is_pointer<It>::value, std::iterator_traits<It>, std::false_type>::type::iterator_category, \
                 ItTag>::value, int>::type = 0

#include <iterator>

template<typename Value,
         typename Alloc = std::allocator<Value>>
class List : ListAlloc<Value, Alloc>
{
    using base = typename List::base;

    #define takeover(N) using base::N;

    takeover(_alloc_copy)
    takeover(_alloc_fill_n)
    takeover(_alloc_swap)
    takeover(_alloc_destroy_all_prev)
    takeover(_alloc_destroy_node)
    takeover(mAllocator)

    typedef typename base::allocator_traits allocator_traits;

public:

    takeover( get_allocator )
    takeover( max_size )

    #undef takeover
    #define takeover(N) using typename base::N;

    takeover(Node)

    takeover(value_type)

    takeover(reference)
    takeover(const_reference)
    takeover(pointer)
    takeover(const_pointer)

    takeover(difference_type)
    takeover(size_type)

    takeover(allocator_type)

	struct iterator : std::iterator<std::bidirectional_iterator_tag,
	                                     value_type,
	                                     difference_type,
	                                     pointer,
	                                     reference>
	{
	private:

		friend class List;

		mutable Node* p;

		iterator( Node* p ) noexcept :
			p{p} {}

	public:

	    iterator() noexcept :
	        iterator{nullptr} {}

		reference operator*() noexcept { return *(p->data); }
		pointer operator->() noexcept { return p->data; }
		const_reference operator*() const noexcept { return *(p->data); }
		const_pointer operator->() const noexcept { return p->data; }

		friend bool operator==( iterator lhs, iterator rhs ) noexcept { return lhs.p == rhs.p; }
		friend bool operator!=( iterator lhs, iterator rhs ) noexcept { return !(lhs == rhs); }

		#define DEFINE_OP( mem, ch, specifier ) \
			iterator specifier operator ch() specifier noexcept \
			{ \
				p = p->mem; \
				return *this; \
			}

		DEFINE_OP( next, ++, )
		DEFINE_OP( prev, --, )
		DEFINE_OP( next, ++, const )
		DEFINE_OP( prev, --, const )

		#define DEFINE_POST_OP( ch, specifier ) \
			iterator specifier operator ch(int) specifier noexcept \
			{ \
				auto rval = *this; \
				++*this; \
				return rval; \
			}

		DEFINE_POST_OP( ++, )
		DEFINE_POST_OP( --, )
		DEFINE_POST_OP( ++, const )
		DEFINE_POST_OP( --, const )

		#undef DEFINE_POST_OP
		#undef DEFINE_OP
	};

    typedef iterator const const_iterator;

	typedef std::reverse_iterator<iterator> reverse_iterator;
	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

private:

	iterator mStart, mEnd;

	size_type mSize;

/// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    void _assign_to( std::pair<Node*, Node*> pair )
    {
		mStart = pair.first;
		mEnd = pair.second;
    }

    template<typename scenario_bool>
	void _swap( List& other )
	{
	    std::swap( mStart, other.mStart );
	    std::swap( mEnd, other.mEnd );
	    std::swap( mSize, other.mSize );
	    _alloc_swap( mAllocator, other.mAllocator, scenario_bool{} );
	}

	/**< Löscht alles. Danach sind beide start und end Iteratoren nicht gültig */
	void _shutdown()
	{
        if( !empty() )
        {
            --mEnd;
            _alloc_destroy_all_prev( mEnd.p );
            mSize = 0;
        }
        else
            delete mEnd.p;
	}

public:

	void swap( List& other )
	{
	    _swap<typename allocator_traits::propagate_on_container_swap>(other);
	}

	explicit List( allocator_type const& alloc = allocator_type{} ):
		base{alloc},
		mStart{ new Node },
		mEnd{ mStart },
		mSize{0} {}

	explicit List( size_type count,
				   const_reference value,
				   allocator_type const& alloc = allocator_type{} ):
		base{alloc},
		mSize{count}
	{
	    _assign_to( _alloc_fill_n(count, mAllocator.address(value)) );
	}

	explicit List( size_type count,
				   allocator_type const& alloc = allocator_type{} ):
		base{alloc},
		mSize{count}
	{
	    _assign_to( _alloc_fill_n(count) );
	}

	template<typename InputIterator
             TAG_CHECK(InputIterator, std::input_iterator_tag)>
	explicit List( InputIterator first,
                   InputIterator last,
                   allocator_type const& alloc = allocator_type{} ):
       List{alloc}
    {
        assign(first, last);
    }

    List( std::initializer_list<value_type> ilist,
          allocator_type const& alloc = allocator_type{} ):
        List(std::begin(ilist), std::end(ilist), alloc) {}

    List( List const& l ):
        base{ allocator_traits::select_on_container_copy_construction(l.mAllocator) },
        mSize{l.mSize}
    { _assign_to( _alloc_copy( mSize, l.cbegin() ) ); }

    List( List const& l, allocator_type const& alloc ):
        base{alloc},
        mSize{l.mSize}
    { _assign_to( _alloc_copy( mSize, l.cbegin() ) ); }

    List& operator=( List const& l )
    {
        clear();

        if( allocator_traits::propagate_on_container_copy_assignment::value )
            mAllocator = l.mAllocator;

        _assign_to( _alloc_copy( l.mSize, l.cbegin() ) );
        mSize = l.mSize;

        return *this;
    }

    List( List&& l ):
		List{}
    { _swap<std::false_type>(l); }

    List( List&& l, allocator_type const& alloc ):
        List{alloc}
    { _swap<std::false_type>(l); }

    List& operator=( List&& l )
    {
        clear();
        _swap<allocator_traits::propagate_on_container_move_assignment>(l);
    }

	~List() // noexcept (ist schon default)
	{
	    _shutdown();
	}

    void assign( size_type count, const_reference value )
    {
        clear();
        mSize = count;
        _assign_to( _alloc_fill_n(count, mAllocator.address(value)) );
    }

    template<typename InputIterator>
    void assign( InputIterator first, InputIterator last )
    {
        clear();
        insert( cbegin(), first, last );
    }

    void assign( std::initializer_list<value_type> ilist )
    {
        assign(std::begin(ilist), std::end(ilist));
    }

	size_type size() const { return mSize; }

	bool empty() const { return size() == 0; }

	void clear()
	{
	    _shutdown();

        mStart = new Node;
        mEnd = mStart;
	}

	iterator begin()              noexcept { return mStart ; }
	iterator end()                noexcept { return mEnd   ; }
	const_iterator begin()  const noexcept { return mStart ; }
	const_iterator end()    const noexcept { return mEnd   ; }
	const_iterator cbegin() const noexcept { return begin(); }
	const_iterator cend()   const noexcept { return end()  ; }

	reverse_iterator rbegin()              { return reverse_iterator{begin()}; }
	reverse_iterator rend()                { return reverse_iterator{end()  }; }
	const_reverse_iterator rbegin()  const { return const_reverse_iterator{cbegin()}; }
	const_reverse_iterator rend()    const { return const_reverse_iterator{cend()  }; }
	const_reverse_iterator crbegin() const { return rbegin(); }
	const_reverse_iterator crend()   const { return rend()  ; }

	reference front() noexcept { return *begin(); }
	reference back() noexcept { return *--iterator{end()}; }
	const_reference front() const noexcept { return *cbegin(); }
	const_reference back() const noexcept { return *--const_iterator{cend()}; }

    template<typename... ValueT>
    iterator emplace( const_iterator it, ValueT&&... v )
    {
        auto node = new Node{it.p->prev, it.p};

        if( it == mStart )
            mStart = node;

        try
        {
            node->data = allocator_traits::allocate( mAllocator, 1 );
            allocator_traits::construct( mAllocator, node->data, std::forward<ValueT>(v)... );
        }
        catch(...)
        {
            if(node->data)
                allocator_traits::deallocate(mAllocator, node->data, 1);
            throw;
        }

        if( it.p->prev )
            it.p->prev->next = node;
        it.p->prev = node;

        ++mSize;

        return node;
    }

    iterator insert( const_iterator it, const_reference value )
    { return emplace(it, value); }
    iterator insert( const_iterator it, value_type&& value )
    { return emplace(it, value); }

    iterator insert( const_iterator it, size_type count, const_reference value )
    {
        if( count == 0 )
            return it;

        auto rval = insert( it, value );

        while( --count )
            insert( it, value );

        return rval;
    }

    template<typename InputIterator
             TAG_CHECK(InputIterator, std::input_iterator_tag)>
    iterator insert( const_iterator it, InputIterator first, InputIterator last )
    {
        if( first == last )
            return it;

        auto rval = insert( it, *first );

        while( ++first != last )
            insert( it, *first );

        return rval;
    }

    iterator insert( const_iterator it, std::initializer_list<value_type> ilist )
    {
        insert( it, std::begin(ilist), std::end(ilist) );
    }

    template<typename... Args>
    iterator emplace_back( Args&&... args )
    {
        return emplace( cend(), std::forward<Args>(args)... );
    }

    template<typename... Args>
    iterator emplace_front( Args&&... args )
    {
        return emplace( cbegin(), std::forward<Args>(args)... );
    }

    void push_back( const_reference v )
    { insert( cend(), v ); }
    void push_back( value_type&& v )
    { insert( cend(), v ); }

    void push_front( const_reference v )
    { insert( cbegin(), v ); }
    void push_front( value_type&& v )
    { insert( cbegin(), v ); }

    iterator erase( const_iterator it )
    {
        auto rval = it.p->next;

        if( it == mStart )
            mStart = rval;

        if( it.p->prev )
            it.p->prev->next = it.p->next;
        if( it.p->next )
            it.p->next->prev = it.p->prev;

        _alloc_destroy_node( it.p );

        --mSize;

        return rval;
    }

    iterator erase( const_iterator first, const_iterator last )
    {
        while( first != last )
            erase( first++ );

        return last;
    }

    void pop_back()
    { erase( --end() ); }
    void pop_front()
    { erase( begin() ); }

private:

    template<typename ... Args>
    void _resize_impl( size_type new_size, Args&&... args )
    {
        if( new_size > size() )
            for( size_type n = size(); n != new_size; ++n )
                emplace_back( std::forward<Args>(args)... );

        else if( new_size < size() )
            erase( std::next(cbegin(), new_size), cend() );
    }

public:
    void resize( size_type new_size, const_reference value )
    { _resize_impl( new_size, value ); }
    void resize( size_type new_size )
    { _resize_impl( new_size ); }
};
#include <iostream>
#include <iterator>
#include <cassert>
#include <string>
 
int main()
{
#define check(s) assert(std::string(l.begin(), l.end()) == s)
 
  List<char> l;
  l.push_back('m');  check("m");
  l.push_back('z');  check("mz");
  l.push_front('a'); check("amz");
  l.erase(l.begin());check("mz");
  l.insert(l.begin(), 'a');check("amz");
  l.insert(l.end(), '!');  check("amz!");
  l.pop_front();     check("mz!");
  l.pop_back();      check("mz");
  List<char>::iterator i=l.begin(); i++;
  i = l.insert(i, '-'); check("m-z");
  i = l.erase(i);       check("mz");
  l.erase(i);           check("m");
  l.push_front('a');    check("am");
  l.push_back('z');     check("amz");
  i=l.end(); i--; i--;
  i=l.erase(i);         check("az");
}