fork download 
  1. #include <memory>
  2. #include <cstddef>
  3.  
  4. template<typename Value,
  5.          typename Alloc = std::allocator<Value>>
  6. struct ListAlloc
  7. {
  8.     using base = ListAlloc;
  9.  
  10.     using allocator_type = Alloc;
  11.     using allocator_traits = std::allocator_traits<allocator_type>;
  12.  
  13. 	#define takeover( N ) using N = typename allocator_traits::N;
  14.  
  15. 	takeover(value_type)
  16.  
  17. 	typedef value_type& reference;
  18. 	typedef value_type const& const_reference;
  19.  
  20. 	takeover(pointer)
  21. 	takeover(const_pointer)
  22.  
  23. 	takeover(difference_type)
  24. 	takeover(size_type)
  25.  
  26. 	#undef takeover
  27.  
  28. 	allocator_type mAllocator;
  29.  
  30. 	ListAlloc( allocator_type const& alloc = allocator_type{} ):
  31. 	    mAllocator{alloc} {}
  32.  
  33. // ///////////////////////////////////////////////////////////////////////////////////////////
  34.  
  35. 	struct Node
  36. 	{
  37. 		Node *prev,
  38. 		     *next;
  39.  
  40. 		pointer data;
  41.  
  42. 		Node( Node* prev, Node* next, pointer data = nullptr ) noexcept :
  43. 			prev{prev},
  44. 			next{next},
  45. 			data{data} {}
  46.  
  47. 		Node() noexcept :
  48. 			Node{nullptr, nullptr} {} // No increment (delegate ctor)
  49. 	};
  50.  
  51.     void _alloc_destroy_node( Node* ptr )
  52.     {
  53.         allocator_traits::destroy( mAllocator, ptr->data );
  54.         allocator_traits::deallocate( mAllocator, ptr->data, 1 );
  55.         delete ptr;
  56.     }
  57.  
  58. 	void _alloc_destroy_all_prev( Node* ptr )
  59.     {
  60.         delete ptr->next; // Ist ptr der letzte Knoten, dann ist ptr->next 0. Sonst wird der nächste das end()-Äquivalent sein.
  61.  
  62.         Node* old_ptr;
  63. 		while( ptr )
  64. 		{
  65. 			old_ptr = ptr;
  66. 			ptr = ptr->prev;
  67. 			_alloc_destroy_node(old_ptr);
  68. 		}
  69. 	}
  70.  
  71. private:
  72.     template<typename Func>
  73.     std::pair<Node*, Node*> _alloc_create_impl( size_type n, Func constructor )
  74.     {
  75. 		Node* ptr = new Node;
  76. 		Node* const rval = ptr;
  77.  
  78. 		while( n-- )
  79. 		{
  80. 		    bool constructed = false;
  81. 			try
  82. 			{
  83.                 ptr->data = allocator_traits::allocate( mAllocator, 1 );
  84.  
  85.                 constructor( ptr->data );
  86.  
  87. 				constructed = true;
  88.  
  89.                 ptr->next = new Node{ptr, nullptr};
  90. 			}
  91. 			catch(...)
  92. 			{
  93.                 if( constructed )
  94.                     allocator_traits::destroy( mAllocator, ptr->data );
  95.  
  96. 			    if( ptr->data )
  97.                     allocator_traits::deallocate( mAllocator, ptr->data, 1 );
  98.  
  99. 				ptr = ptr->prev;
  100. 				_alloc_destroy_all_prev( ptr );
  101.  
  102. 				throw;
  103. 			}
  104.  
  105. 			auto old_ptr = ptr;
  106. 			ptr = ptr->next;
  107. 			ptr->prev = old_ptr;
  108. 		}
  109.  
  110. 		return {rval, ptr};
  111.     }
  112.  
  113. public:
  114. 	std::pair<Node*, Node*> _alloc_fill_n( size_type n )
  115. 	{
  116. 	    return _alloc_create_impl( n, [&](pointer p){ allocator_traits::construct( mAllocator, p ); } );
  117. 	}
  118.  
  119. 	std::pair<Node*, Node*> _alloc_fill_n( size_type n, const_pointer value )
  120. 	{
  121.         return _alloc_create_impl( n, [&](pointer p){ allocator_traits::construct( mAllocator, p, *value ); } );
  122. 	}
  123.  
  124.     template<typename InputIterator>
  125.     std::pair<Node*, Node*> _alloc_copy( size_type n, InputIterator first )
  126.     {
  127.         return _alloc_create_impl( n, [&]( pointer p ){ allocator_traits::construct( mAllocator, p, *first++ ); } );
  128.     }
  129.  
  130. // ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  131.  
  132.     void _alloc_swap( allocator_type& lhs, allocator_type& rhs, std::true_type )
  133.     { std::swap(lhs, rhs); }
  134.     void _alloc_swap( allocator_type&, allocator_type&, std::false_type )
  135.     {}
  136.  
  137.     allocator_type get_allocator() const { return mAllocator; }
  138.  
  139.     size_type max_size() const { return allocator_traits::max_size(mAllocator); }
  140. };
  141.  
  142. #include <type_traits>
  143.  
  144. /// Geborgt von camper - verzeih'
  145. #define TAG_CHECK(It, ItTag) \
  146.            ,typename std::enable_if<std::is_convertible< \
  147.                  typename std::conditional<std::is_class<It>::value || std::is_pointer<It>::value, std::iterator_traits<It>, std::false_type>::type::iterator_category, \
  148.                  ItTag>::value, int>::type = 0
  149.  
  150. #include <iterator>
  151.  
  152. template<typename Value,
  153.          typename Alloc = std::allocator<Value>>
  154. class List : ListAlloc<Value, Alloc>
  155. {
  156.     using base = typename List::base;
  157.  
  158.     #define takeover(N) using base::N;
  159.  
  160.     takeover(_alloc_copy)
  161.     takeover(_alloc_fill_n)
  162.     takeover(_alloc_swap)
  163.     takeover(_alloc_destroy_all_prev)
  164.     takeover(_alloc_destroy_node)
  165.     takeover(mAllocator)
  166.  
  167.     typedef typename base::allocator_traits allocator_traits;
  168.  
  169. public:
  170.  
  171.     takeover( get_allocator )
  172.     takeover( max_size )
  173.  
  174.     #undef takeover
  175.     #define takeover(N) using typename base::N;
  176.  
  177.     takeover(Node)
  178.  
  179.     takeover(value_type)
  180.  
  181.     takeover(reference)
  182.     takeover(const_reference)
  183.     takeover(pointer)
  184.     takeover(const_pointer)
  185.  
  186.     takeover(difference_type)
  187.     takeover(size_type)
  188.  
  189.     takeover(allocator_type)
  190.  
  191. 	struct iterator : std::iterator<std::bidirectional_iterator_tag,
  192. 	                                     value_type,
  193. 	                                     difference_type,
  194. 	                                     pointer,
  195. 	                                     reference>
  196. 	{
  197. 	private:
  198.  
  199. 		friend class List;
  200.  
  201. 		mutable Node* p;
  202.  
  203. 		iterator( Node* p ) noexcept :
  204. 			p{p} {}
  205.  
  206. 	public:
  207.  
  208. 	    iterator() noexcept :
  209. 	        iterator{nullptr} {}
  210.  
  211. 		reference operator*() noexcept { return *(p->data); }
  212. 		pointer operator->() noexcept { return p->data; }
  213. 		const_reference operator*() const noexcept { return *(p->data); }
  214. 		const_pointer operator->() const noexcept { return p->data; }
  215.  
  216. 		friend bool operator==( iterator lhs, iterator rhs ) noexcept { return lhs.p == rhs.p; }
  217. 		friend bool operator!=( iterator lhs, iterator rhs ) noexcept { return !(lhs == rhs); }
  218.  
  219. 		#define DEFINE_OP( mem, ch, specifier ) \
  220. 			iterator specifier& operator ch() specifier noexcept \
  221. 			{ \
  222. 				p = p->mem; \
  223. 				return *this; \
  224. 			}
  225.  
  226. 		DEFINE_OP( next, ++, )
  227. 		DEFINE_OP( prev, --, )
  228. 		DEFINE_OP( next, ++, const )
  229. 		DEFINE_OP( prev, --, const )
  230.  
  231. 		#define DEFINE_POST_OP( ch, specifier ) \
  232. 			iterator specifier operator ch(int) specifier noexcept \
  233. 			{ \
  234. 				auto rval = *this; \
  235. 				ch*this; \
  236. 				return rval; \
  237. 			}
  238.  
  239. 		DEFINE_POST_OP( ++, )
  240. 		DEFINE_POST_OP( --, )
  241. 		DEFINE_POST_OP( ++, const )
  242. 		DEFINE_POST_OP( --, const )
  243.  
  244. 		#undef DEFINE_POST_OP
  245. 		#undef DEFINE_OP
  246. 	};
  247.  
  248.     typedef iterator const const_iterator;
  249.  
  250. 	typedef std::reverse_iterator<iterator> reverse_iterator;
  251. 	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  252.  
  253. private:
  254.  
  255. 	iterator mStart, mEnd;
  256.  
  257. 	size_type mSize;
  258.  
  259. /// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  260.  
  261.     void _assign_to( std::pair<Node*, Node*> pair )
  262.     {
  263. 		mStart = pair.first;
  264. 		mEnd = pair.second;
  265.     }
  266.  
  267.     template<typename scenario_bool>
  268. 	void _swap( List& other )
  269. 	{
  270. 	    std::swap( mStart, other.mStart );
  271. 	    std::swap( mEnd, other.mEnd );
  272. 	    std::swap( mSize, other.mSize );
  273. 	    _alloc_swap( mAllocator, other.mAllocator, scenario_bool{} );
  274. 	}
  275.  
  276. 	/**< Löscht alles. Danach sind beide start und end Iteratoren nicht gültig */
  277. 	void _shutdown()
  278. 	{
  279.         if( !empty() )
  280.         {
  281.             --mEnd;
  282.             _alloc_destroy_all_prev( mEnd.p );
  283.             mSize = 0;
  284.         }
  285.         else
  286.             delete mEnd.p;
  287. 	}
  288.  
  289. public:
  290.  
  291. 	void swap( List& other )
  292. 	{
  293. 	    _swap<typename allocator_traits::propagate_on_container_swap>(other);
  294. 	}
  295.  
  296. 	explicit List( allocator_type const& alloc = allocator_type{} ):
  297. 		base{alloc},
  298. 		mStart{ new Node },
  299. 		mEnd{ mStart },
  300. 		mSize{0} {}
  301.  
  302. 	explicit List( size_type count,
  303. 				   const_reference value,
  304. 				   allocator_type const& alloc = allocator_type{} ):
  305. 		base{alloc},
  306. 		mSize{count}
  307. 	{
  308. 	    _assign_to( _alloc_fill_n(count, mAllocator.address(value)) );
  309. 	}
  310.  
  311. 	explicit List( size_type count,
  312. 				   allocator_type const& alloc = allocator_type{} ):
  313. 		base{alloc},
  314. 		mSize{count}
  315. 	{
  316. 	    _assign_to( _alloc_fill_n(count) );
  317. 	}
  318.  
  319. 	template<typename InputIterator
  320.              TAG_CHECK(InputIterator, std::input_iterator_tag)>
  321. 	explicit List( InputIterator first,
  322.                    InputIterator last,
  323.                    allocator_type const& alloc = allocator_type{} ):
  324.        List{alloc}
  325.     {
  326.         assign(first, last);
  327.     }
  328.  
  329.     List( std::initializer_list<value_type> ilist,
  330.           allocator_type const& alloc = allocator_type{} ):
  331.         List(std::begin(ilist), std::end(ilist), alloc) {}
  332.  
  333.     List( List const& l ):
  334.         base{ allocator_traits::select_on_container_copy_construction(l.mAllocator) },
  335.         mSize{l.mSize}
  336.     { _assign_to( _alloc_copy( mSize, l.cbegin() ) ); }
  337.  
  338.     List( List const& l, allocator_type const& alloc ):
  339.         base{alloc},
  340.         mSize{l.mSize}
  341.     { _assign_to( _alloc_copy( mSize, l.cbegin() ) ); }
  342.  
  343.     List& operator=( List const& l )
  344.     {
  345.         clear();
  346.  
  347.         if( allocator_traits::propagate_on_container_copy_assignment::value )
  348.             mAllocator = l.mAllocator;
  349.  
  350.         _assign_to( _alloc_copy( l.mSize, l.cbegin() ) );
  351.         mSize = l.mSize;
  352.  
  353.         return *this;
  354.     }
  355.  
  356.     List( List&& l ):
  357. 		List{}
  358.     { _swap<std::false_type>(l); }
  359.  
  360.     List( List&& l, allocator_type const& alloc ):
  361.         List{alloc}
  362.     { _swap<std::false_type>(l); }
  363.  
  364.     List& operator=( List&& l )
  365.     {
  366.         clear();
  367.         _swap<allocator_traits::propagate_on_container_move_assignment>(l);
  368.     }
  369.  
  370. 	~List() // noexcept (ist schon default)
  371. 	{
  372. 	    _shutdown();
  373. 	}
  374.  
  375.     void assign( size_type count, const_reference value )
  376.     {
  377.         clear();
  378.         mSize = count;
  379.         _assign_to( _alloc_fill_n(count, mAllocator.address(value)) );
  380.     }
  381.  
  382.     template<typename InputIterator>
  383.     void assign( InputIterator first, InputIterator last )
  384.     {
  385.         clear();
  386.         insert( cbegin(), first, last );
  387.     }
  388.  
  389.     void assign( std::initializer_list<value_type> ilist )
  390.     {
  391.         assign(std::begin(ilist), std::end(ilist));
  392.     }
  393.  
  394. 	size_type size() const { return mSize; }
  395.  
  396. 	bool empty() const { return size() == 0; }
  397.  
  398. 	void clear()
  399. 	{
  400. 	    _shutdown();
  401.  
  402.         mStart = new Node;
  403.         mEnd = mStart;
  404. 	}
  405.  
  406. 	iterator begin()              noexcept { return mStart ; }
  407. 	iterator end()                noexcept { return mEnd   ; }
  408. 	const_iterator begin()  const noexcept { return mStart ; }
  409. 	const_iterator end()    const noexcept { return mEnd   ; }
  410. 	const_iterator cbegin() const noexcept { return begin(); }
  411. 	const_iterator cend()   const noexcept { return end()  ; }
  412.  
  413. 	reverse_iterator rbegin()              { return reverse_iterator{begin()}; }
  414. 	reverse_iterator rend()                { return reverse_iterator{end()  }; }
  415. 	const_reverse_iterator rbegin()  const { return const_reverse_iterator{cbegin()}; }
  416. 	const_reverse_iterator rend()    const { return const_reverse_iterator{cend()  }; }
  417. 	const_reverse_iterator crbegin() const { return rbegin(); }
  418. 	const_reverse_iterator crend()   const { return rend()  ; }
  419.  
  420. 	reference front() noexcept { return *begin(); }
  421. 	reference back() noexcept { return *--iterator{end()}; }
  422. 	const_reference front() const noexcept { return *cbegin(); }
  423. 	const_reference back() const noexcept { return *--const_iterator{cend()}; }
  424.  
  425.     template<typename... ValueT>
  426.     iterator emplace( const_iterator it, ValueT&&... v )
  427.     {
  428.         auto node = new Node{it.p->prev, it.p};
  429.  
  430.         if( it == mStart )
  431.             mStart = node;
  432.  
  433.         try
  434.         {
  435.             node->data = allocator_traits::allocate( mAllocator, 1 );
  436.             allocator_traits::construct( mAllocator, node->data, std::forward<ValueT>(v)... );
  437.         }
  438.         catch(...)
  439.         {
  440.             if(node->data)
  441.                 allocator_traits::deallocate(mAllocator, node->data, 1);
  442.             throw;
  443.         }
  444.  
  445.         if( it.p->prev )
  446.             it.p->prev->next = node;
  447.         it.p->prev = node;
  448.  
  449.         ++mSize;
  450.  
  451.         return node;
  452.     }
  453.  
  454.     iterator insert( const_iterator it, const_reference value )
  455.     { return emplace(it, value); }
  456.     iterator insert( const_iterator it, value_type&& value )
  457.     { return emplace(it, value); }
  458.  
  459.     iterator insert( const_iterator it, size_type count, const_reference value )
  460.     {
  461.         if( count == 0 )
  462.             return it;
  463.  
  464.         auto rval = insert( it, value );
  465.  
  466.         while( --count )
  467.             insert( it, value );
  468.  
  469.         return rval;
  470.     }
  471.  
  472.     template<typename InputIterator
  473.              TAG_CHECK(InputIterator, std::input_iterator_tag)>
  474.     iterator insert( const_iterator it, InputIterator first, InputIterator last )
  475.     {
  476.         if( first == last )
  477.             return it;
  478.  
  479.         auto rval = insert( it, *first );
  480.  
  481.         while( ++first != last )
  482.             insert( it, *first );
  483.  
  484.         return rval;
  485.     }
  486.  
  487.     iterator insert( const_iterator it, std::initializer_list<value_type> ilist )
  488.     {
  489.         insert( it, std::begin(ilist), std::end(ilist) );
  490.     }
  491.  
  492.     template<typename... Args>
  493.     iterator emplace_back( Args&&... args )
  494.     {
  495.         return emplace( cend(), std::forward<Args>(args)... );
  496.     }
  497.  
  498.     template<typename... Args>
  499.     iterator emplace_front( Args&&... args )
  500.     {
  501.         return emplace( cbegin(), std::forward<Args>(args)... );
  502.     }
  503.  
  504.     void push_back( const_reference v )
  505.     { insert( cend(), v ); }
  506.     void push_back( value_type&& v )
  507.     { insert( cend(), v ); }
  508.  
  509.     void push_front( const_reference v )
  510.     { insert( cbegin(), v ); }
  511.     void push_front( value_type&& v )
  512.     { insert( cbegin(), v ); }
  513.  
  514.     iterator erase( const_iterator it )
  515.     {
  516.         auto rval = it.p->next;
  517.  
  518.         if( it == mStart )
  519.             mStart = rval;
  520.  
  521.         if( it.p->prev )
  522.             it.p->prev->next = it.p->next;
  523.         if( it.p->next )
  524.             it.p->next->prev = it.p->prev;
  525.  
  526.         _alloc_destroy_node( it.p );
  527.  
  528.         --mSize;
  529.  
  530.         return rval;
  531.     }
  532.  
  533.     iterator erase( const_iterator first, const_iterator last )
  534.     {
  535.         while( first != last )
  536.             erase( first++ );
  537.  
  538.         return last;
  539.     }
  540.  
  541.     void pop_back()
  542.     { erase( --end() ); }
  543.     void pop_front()
  544.     { erase( begin() ); }
  545.  
  546. private:
  547.  
  548.     template<typename ... Args>
  549.     void _resize_impl( size_type new_size, Args&&... args )
  550.     {
  551.         if( new_size > size() )
  552.             for( size_type n = size(); n != new_size; ++n )
  553.                 emplace_back( std::forward<Args>(args)... );
  554.  
  555.         else if( new_size < size() )
  556.             erase( std::next(cbegin(), new_size), cend() );
  557.     }
  558.  
  559. public:
  560.     void resize( size_type new_size, const_reference value )
  561.     { _resize_impl( new_size, value ); }
  562.     void resize( size_type new_size )
  563.     { _resize_impl( new_size ); }
  564. };
  565. #include <iostream>
  566. #include <iterator>
  567. #include <cassert>
  568. #include <string>
  569.  
  570. int main()
  571. {
  572. #define check(s) assert(std::string(l.begin(), l.end()) == s)
  573.  
  574.   List<char> l;
  575.   l.push_back('m');  check("m");
  576.   l.push_back('z');  check("mz");
  577.   l.push_front('a'); check("amz");
  578.   l.erase(l.begin());check("mz");
  579.   l.insert(l.begin(), 'a');check("amz");
  580.   l.insert(l.end(), '!');  check("amz!");
  581.   l.pop_front();     check("mz!");
  582.   l.pop_back();      check("mz");
  583.   List<char>::iterator i=l.begin(); i++;
  584.   i = l.insert(i, '-'); check("m-z");
  585.   i = l.erase(i);       check("mz");
  586.   l.erase(i);           check("m");
  587.   l.push_front('a');    check("am");
  588.   l.push_back('z');     check("amz");
  589.   i=l.end(); i--; i--;
  590.   i=l.erase(i);         check("az");
  591. }
  592.  
Success #stdin #stdout 0s 3028KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/P6IBYq
language:
C++14 (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!