#include <memory>
#include <cstddef>

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

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

    struct NodeBase
    {
		NodeBase *prev,
                 *next;

		NodeBase( NodeBase* prev, NodeBase* next ) noexcept :
			prev{prev},
			next{next} {}

		NodeBase() noexcept :
			NodeBase{nullptr, nullptr} {}
	} mutable mStart, mEnd;

	struct Node : NodeBase
	{
		value_type data;

        template<typename... Args>
		Node( NodeBase* prev, NodeBase* next, Args&&... args ) noexcept :
			NodeBase{prev, next},
			data{std::forward<Args>(args)...} {}

		Node() noexcept = default;
	};

    using allocator_type = typename Alloc::template rebind<Node>::other;
	using allocator_traits = std::allocator_traits<allocator_type>;

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

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

	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( NodeBase const& start, NodeBase const& end, allocator_type const& alloc = allocator_type{} ):
	    mStart{start}, mEnd{end},
	    mAllocator{alloc} {}

    template<typename... Args>
    Node* _alloc_make_node( NodeBase* prev, NodeBase* next, Args&&... args )
    {
        Node* node = allocator_traits::allocate( mAllocator, 1 );

        try
        {
            allocator_traits::construct( mAllocator, node, prev, next, std::forward<Args>(args)... );
        }
        catch(...)
        {
            allocator_traits::deallocate( mAllocator, node, 1 );
            throw;
        }

        return node;
    }

    template<typename... Args>
    Node* _alloc_make_node_notify( NodeBase* prev, NodeBase* next, Args&&... args )
    {
        Node* node = _alloc_make_node( prev, next, std::forward<Args>(args)... );

        if( prev )
            prev->next = node;
        if( next )
            next->prev = node;

        return node;
    }

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

	void _alloc_destroy_all_prev( NodeBase* end, NodeBase* ptr )
    {
        NodeBase* old_ptr;
		while( ptr != end )
		{
			old_ptr = ptr;
			ptr = ptr->prev;
			_alloc_destroy_node( static_cast<Node*>(old_ptr) );
		}
	}

private:

    template<typename... Func>
    std::pair<Node*, Node*> _alloc_create_impl( size_type n, Func... func )
    {
        if( n == 0 )
            return { nullptr, nullptr };

		Node* ptr = _alloc_make_node_notify( ptr, nullptr, func()... );
		Node* const rval = ptr;

		while( --n ) try
        {
            ptr = _alloc_make_node_notify( ptr, nullptr, func()... );
        }
        catch(...)
        {
            ptr = ptr->prev;
            _alloc_destroy_all_prev( ptr );
            throw;
        }


		return {rval, ptr};
    }

public:
	std::pair<Node*, Node*> _alloc_fill_n( size_type n )
	{
	    return _alloc_create_impl( n );
	}

	std::pair<Node*, Node*> _alloc_fill_n( size_type n, const_reference value )
	{
        return _alloc_create_impl( n, [&]() -> const_reference { return value; } );
	}

    template<typename InputIterator>
    std::pair<Node*, Node*> _alloc_copy( size_type n, InputIterator first )
    {
        return _alloc_create_impl( n, [&]() -> const_reference { return *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>
{
    #define takeover(N) using ListAlloc<Value,Alloc>::N;

    takeover(_alloc_copy)
    takeover(_alloc_make_node_notify)
    takeover(_alloc_make_node)
    takeover(_alloc_fill_n)
    takeover(_alloc_swap)
    takeover(_alloc_destroy_all_prev)
    takeover(_alloc_destroy_node)

    takeover(mAllocator)
    takeover(mStart)
    takeover(mEnd)

    typedef typename List::allocator_traits allocator_traits;

public:

    takeover( get_allocator )
    takeover( max_size )

    #undef takeover
    #define takeover(N) using typename ListAlloc<Value,Alloc>::N;
    takeover(NodeBase)

private:
    takeover(Node)

public:
    takeover(value_type)
    takeover(reference)
    takeover(const_reference)
    takeover(pointer)
    takeover(const_pointer)
    takeover(difference_type)
    takeover(size_type)
    takeover(allocator_type)


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

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

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

		friend class List;
		friend class const_iterator;

		NodeBase* p;

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

	public:

	    iterator() noexcept :
	        iterator{nullptr} {}

		reference operator*() noexcept { return static_cast<Node*>(p)->data; }
		pointer operator->() noexcept { return &static_cast<Node*>(p)->data; }

		DEFINE_OP( iterator, next, ++ )
		DEFINE_OP( iterator, prev, -- )
		DEFINE_POST_OP( iterator, ++ )
		DEFINE_POST_OP( iterator, -- )

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

	struct const_iterator : std::iterator<std::bidirectional_iterator_tag,
	                                      value_type const,
                                          difference_type,
	                                      const_pointer,
	                                      const_reference>
	{
	private:

		friend class List;

		mutable NodeBase* p;

		const_iterator( NodeBase* p ) noexcept :
			p{p} {}

	public:

	    const_iterator() noexcept :
	        const_iterator{nullptr} {}

		const_iterator( iterator it ) noexcept :
			p{it.p} {}

		const_reference operator*() noexcept { return static_cast<Node*>(p)->data; }
		const_pointer operator->() noexcept { return &static_cast<Node*>(p)->data; }

		DEFINE_OP( const_iterator, next, ++ )
		DEFINE_OP( const_iterator, prev, -- )
		DEFINE_POST_OP( const_iterator, ++ )
		DEFINE_POST_OP( const_iterator, -- )

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

#undef DEFINE_POST_OP
#undef DEFINE_OP

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

private:

	size_type mSize;

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

    void _assign_to( std::pair<Node*, Node*> pair )
    {
		mStart.next = pair.first;
		mEnd.prev = 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{} );
	}

public:

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

	explicit List( allocator_type const& alloc = allocator_type{} ):
		ListAlloc<Value, Alloc>{NodeBase{ nullptr, &mEnd }, // Start-NodeBase
		                        NodeBase{ &mStart, nullptr }, // End-NodeBase
		                        alloc},
		mSize{0} {}

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

	explicit List( size_type count,
				   allocator_type const& alloc = allocator_type{} ):
		ListAlloc<Value, Alloc>{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 ):
        ListAlloc<Value, Alloc>{ 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 ):
        ListAlloc<Value, Alloc>{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)
	{
	    clear();
	}

    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()
	{
	    _alloc_destroy_all_prev( &mStart, mEnd.prev );
	    mSize = 0;
	}

	iterator begin()              noexcept { return mStart.next ; }
	iterator end()                noexcept { return &mEnd   ; }
	const_iterator begin()  const noexcept { return mStart.next ; }
	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 = _alloc_make_node_notify( it.p->prev, it.p, std::forward<ValueT>(v)... );

        ++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;

        it.p->prev->next = it.p->next;
        it.p->next->prev = it.p->prev;

        _alloc_destroy_node( static_cast<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");
}