#include #include #include #include #include template < typename T, typename Allocator = std::allocator< T > > class linked_list { static_assert( std::is_same_v< T, typename Allocator::value_type >, "Expected T to match Allocator::T." ); struct node_base { node_base* next; node_base() : next{ nullptr } {} node_base( node_base* const _next ) : next{ _next } {} }; struct node : public node_base { T data; node() : node_base{ nullptr }, data{ T() } {} template < typename... Args > node( Args&&... args ) : node_base{ nullptr }, data{ std::forward< Args >( args )... } {} template < typename... Args > node( node_base* const _next, Args&&... args ) : node_base{ _next }, data{ std::forward< Args >( args )... } {} }; public: class forward_iterator { friend class linked_list; public: using iterator_category = std::forward_iterator_tag; using value_type = T; using difference_type = std::ptrdiff_t; using pointer = T*; using reference = T&; explicit forward_iterator( node_base* _ptr = nullptr ) : ptr{ _ptr } {} forward_iterator& operator ++ () { this->ptr = ptr->next; return *this; } forward_iterator operator ++ ( int ) { forward_iterator _tmp( *this ); this->ptr = ptr->next; return _tmp; } reference operator * () { return static_cast< node* >( this->ptr )->data; } const reference operator * () const { return static_cast< node* >( this->ptr )->data; } pointer operator -> () { return &( static_cast< node* >( this->ptr )->data ); } const pointer operator -> () const { return &( static_cast< node* >( this->ptr )->data ); } bool operator () () const { return ( this->ptr != nullptr ); } bool operator == ( const forward_iterator& other ) const { return ( this->ptr == other.ptr ); } bool operator != ( const forward_iterator& other ) const { return ( this->ptr != other.ptr ); } private: node_base* ptr; }; class const_forward_iterator { friend class linked_list; public: using iterator_category = std::forward_iterator_tag; using value_type = const T; using difference_type = std::ptrdiff_t; using pointer = const T*; using reference = const T&; explicit const_forward_iterator( const node_base* _ptr = nullptr ) : ptr{ _ptr } {} const_forward_iterator& operator ++ () { this->ptr = ptr->next; return *this; } const_forward_iterator operator ++ ( int ) { forward_iterator _tmp( *this ); this->ptr = ptr->next; return _tmp; } const reference operator * () const { return static_cast< const node* >( this->ptr )->data; } const pointer operator -> () const { return &( static_cast< const node* >( this->ptr )->data ); } bool operator () () const { return ( this->ptr != nullptr ); } bool operator == ( const forward_iterator& other ) const { return ( this->ptr == other.ptr ); } bool operator != ( const forward_iterator& other ) const { return ( this->ptr != other.ptr ); } private: const node_base* ptr; }; using value_type = T; using allocator_type = typename std::allocator_traits< Allocator >::template rebind_alloc< node >; using allocator_traits = std::allocator_traits< allocator_type >; using size_type = std::size_t; using difference_type = std::ptrdiff_t; using reference = value_type&; using const_reference = const value_type&; using pointer = typename allocator_traits::pointer; using const_pointer = typename allocator_traits::const_pointer; using iterator = forward_iterator; using const_iterator = const_forward_iterator; linked_list(); explicit linked_list( const allocator_type& ); linked_list( size_type, const_reference, const allocator_type& = allocator_type() ); explicit linked_list( size_type, const allocator_type& = allocator_type() ); linked_list( std::initializer_list< value_type >, const allocator_type& = allocator_type() ); template < typename InputIt > linked_list( InputIt, InputIt, const allocator_type& = allocator_type() ); linked_list( const linked_list& ); linked_list( linked_list&& ); ~linked_list(); linked_list& operator = ( const linked_list& ); linked_list& operator = ( linked_list&& ); linked_list& operator = ( std::initializer_list< value_type > ); void assign( size_type, const_reference ); void assign( std::initializer_list< value_type > ); template < typename InputIt > void assign( InputIt, InputIt ); inline bool empty() const { return !this->head.next; } inline reference front() { return static_cast< node* >( this->head.next )->data; } inline const_reference front() const { return static_cast< node* >( this->head.next )->data; } inline iterator before_begin() { return iterator{ &this->head }; } inline const_iterator before_begin() const { return const_iterator{ &this->head }; } inline const_iterator cbefore_begin() const { return const_iterator{ &this->head }; } inline iterator begin() { return iterator{ this->head.next }; } inline const_iterator begin() const { return const_iterator{ this->head.next }; } inline const_iterator cbegin() const { return const_iterator{ this->head.next }; } inline iterator end() { return iterator{ nullptr }; } inline const_iterator end() const { return const_iterator{ nullptr }; } inline const_iterator cend() const { return const_iterator{ nullptr }; } void clear(); iterator insert_after( const_iterator, const_reference ); iterator insert_after( const_iterator, value_type&& ); iterator insert_after( const_iterator, size_type, const_reference ); iterator insert_after( const_iterator, std::initializer_list< value_type > ); template < typename InputIt > iterator insert_after( const_iterator, InputIt, InputIt ); template < typename... Args > iterator emplace_after( const_iterator, Args&&... ); iterator erase_after( const_iterator ); iterator erase_after( const_iterator, const_iterator ); void push_front( const_reference ); void push_front( value_type&& ); template < typename... Args > reference emplace_front( Args&&... ); void pop_front(); void push_back( const_reference ); void push_back( value_type&& ); template < typename... Args > reference emplace_back( Args&&... ); void pop_back(); void resize( size_type ); void resize( size_type, const_reference ); void swap( linked_list& ); /* Operations omitted */ private: template < typename... Args > node* construct_node( Args&&... ); void destroy_node( node_base* ); allocator_type allocator; node_base head; }; template < typename InputIt, class Allocator = std::allocator< typename std::iterator_traits< InputIt >::value_type > > linked_list( InputIt, InputIt, Allocator = Allocator() ) -> linked_list< typename std::iterator_traits< InputIt >::value_type, Allocator >; template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list() : allocator{ Allocator() }, head{ nullptr } {} template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list( const allocator_type& _alloc ) : allocator{ _alloc }, head{ nullptr } {} template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list( size_type _count, const_reference _value, const allocator_type& _alloc ) : allocator{ _alloc }, head{ nullptr } { node_base** _current{ &this->head.next }; for ( ; _count; --_count, _current = &( ( *_current )->next ) ) { *_current = this->construct_node( _value ); } } template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list( size_type _count, const allocator_type& _alloc ) : allocator{ _alloc }, head{ nullptr } { node_base** _current{ &this->head.next }; for ( ; _count; --_count, _current = &( ( *_current )->next ) ) { *_current = this->construct_node(); } } template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list( std::initializer_list< value_type > _init, const allocator_type& _alloc ) : allocator{ _alloc }, head{ nullptr } { node_base** _current{ &this->head.next }; for ( auto _it{ _init.begin() }; _it != _init.end(); ++_it, _current = &( ( *_current )->next ) ) { *_current = this->construct_node( *_it ); } } template < typename T, typename Allocator > template < typename InputIt > linked_list< T, Allocator >::linked_list( InputIt _first, InputIt _last, const allocator_type& _alloc ) : allocator{ _alloc }, head{ nullptr } { node_base** _current{ &this->head.next }; for ( ; _first != _last; ++_first, _current = &( ( *_current )->next ) ) { *_current = this->construct_node( *_first ); } } template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list( const linked_list< T, Allocator >& other ) : allocator{ other.allocator }, head{ nullptr } { node_base** _current{ &this->head.next }; for ( auto _it{ other.begin() }; _it != other.end(); ++_it, _current = &( ( *_current->next ) ) ) { *_current = this->construct_node( _it->data ); } } template < typename T, typename Allocator > linked_list< T, Allocator >::linked_list( linked_list< T, Allocator >&& other ) : allocator{ std::move( other.allocator ) }, head{ std::move( other.head ) } {} template < typename T, typename Allocator > linked_list< T, Allocator >::~linked_list() { this->clear(); } template < typename T, typename Allocator > linked_list< T, Allocator >& linked_list< T, Allocator >::operator = ( const linked_list< T, Allocator >& other ) { if ( this != &other ) { this->clear(); this->allocator = other.allocator; node_base** _current{ &this->head.next }; for ( auto _it{ other.begin() }; _it != other.end(); ++_it, _current = &( ( *_current->next ) ) ) { *_current = this->construct_node( _it->data ); } } return *this; } template < typename T, typename Allocator > linked_list< T, Allocator >& linked_list< T, Allocator >::operator = ( linked_list< T, Allocator >&& other ) { if ( this != &other ) { this->clear(); this->allocator = std::move( other.allocator ); this->head = std::move( other.head ); } return *this; } template < typename T, typename Allocator > linked_list< T, Allocator >& linked_list< T, Allocator >::operator = ( std::initializer_list< value_type > _init ) { this->clear(); node_base** _current{ &this->head.next }; for ( auto _it{ _init.begin() }; _it != _init.end(); ++_it, _current = &( ( *_current->next ) ) ) { *_current = this->construct_node( *_it ); } return *this; } template < typename T, typename Allocator > void linked_list< T, Allocator >::assign( size_type _count, const_reference _value ) { this->clear(); node_base** _current{ &this->head.next }; for ( ; _count; --_count, _current = &( ( *_current->next ) ) ) { *_current = this->construct_node( _value ); } } template < typename T, typename Allocator > void linked_list< T, Allocator >::assign( std::initializer_list< value_type > _init ) { this->clear(); node_base** _current{ &this->head.next }; for ( auto _it{ _init.begin() }; _it != _init.end(); ++_it, _current = &( ( *_current->next ) ) ) { *_current = this->construct_node( *_it ); } } template < typename T, typename Allocator > template < typename InputIt > void linked_list< T, Allocator >::assign( InputIt _first, InputIt _last ) { this->clear(); node_base** _current{ &this->head.next }; for ( ; _first != _last; ++_first, _current = &( ( *_current->next ) ) ) { *_current = this->construct_node( *_first ); } } template < typename T, typename Allocator > void linked_list< T, Allocator >::clear() { node_base* _current{ this->head.next }; node_base* _next{ nullptr }; while ( _current ) { _next = _current->next; this->destroy_node( _current ); _current = _next; } this->head.next = nullptr; } template < typename T, typename Allocator > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::insert_after( const_iterator _pos, const_reference _value ) { iterator _it{ _pos.ptr->next }; _it.ptr->next = this->construct_node( _it.ptr->next, _value ); return _it; } template < typename T, typename Allocator > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::insert_after( const_iterator _pos, value_type&& _value ) { iterator _it{ _pos.ptr->next }; _it.ptr->next = this->construct_node( _it.ptr->next, std::forward< value_type >( _value ) ); return _it; } template < typename T, typename Allocator > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::insert_after( const_iterator _pos, size_type _count, const_reference _value ) { iterator _it{ _pos.ptr->next }; for ( ; _count; --_count, ++_it ) { _it.ptr->next = this->construct_node( _it.ptr->next, _value ); } return _it; } template < typename T, typename Allocator > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::insert_after( const_iterator _pos, std::initializer_list< value_type > _init ) { iterator _it{ _pos.ptr->next }; for ( auto _first{ _init.begin() }; _first != _init.end(); ++_first, ++_it ) { _it.ptr->next = this->construct_node( _it.ptr->next, *_first ); } return _it; } template < typename T, typename Allocator > template < typename InputIt > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::insert_after( const_iterator _pos, InputIt _first, InputIt _last ) { iterator _it{ _pos.ptr->next }; for ( ; _first != _last; ++_first, ++_it ) { _it.ptr->next = this->construct_node( _it.ptr->next, *_first ); } return _it; } template < typename T, typename Allocator > template < typename... Args > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::emplace_after( const_iterator _pos, Args&&... args ) { iterator _it{ _pos.ptr->next }; _it.ptr->next = this->construct_node( _it.ptr->next, std::forward< Args >( args )... ); return _it; } template < typename T, typename Allocator > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::erase_after( const_iterator _pos ) { iterator _it{ const_cast< node_base* >( _pos.ptr ) }; iterator _next{ _it.ptr->next->next }; this->destroy_node( _it.ptr->next ); _it.ptr->next = _next.ptr; return _next; } template < typename T, typename Allocator > typename linked_list< T, Allocator >::iterator linked_list< T, Allocator >::erase_after( const_iterator _first, const_iterator _last ) { iterator _it{ _first.ptr }; iterator _next{ _first.ptr->next }; while ( _next.ptr != _last.ptr ) { _next = _next.ptr->next; this->destroy_node( _it.ptr->next ); _it.ptr->next = _next; } return _next; } template < typename T, typename Allocator > void linked_list< T, Allocator >::pop_front() { if ( this->head.next ) { node_base* _ptr{ this->head.next }; this->head.next = _ptr->next; this->destroy_node( _ptr ); } } template < typename T, typename Allocator > void linked_list< T, Allocator >::push_front( const_reference _value ) { this->head.next = this->construct_node ( this->head.next, _value ); } template < typename T, typename Allocator > void linked_list< T, Allocator >::push_front( value_type&& _value ) { this->head.next = this->construct_node ( this->head.next, std::forward< value_type >( _value ) ); } template < typename T, typename Allocator > template < typename... Args > typename linked_list< T, Allocator >::reference linked_list< T, Allocator >::emplace_front( Args&&... args ) { this->head.next = this->construct_node ( this->head.next, std::forward< Args >( args )... ); return ( static_cast< node* >( this->head.next )->data ); } template < typename T, typename Allocator > void linked_list< T, Allocator >::pop_back() { if ( !this->head.next->next ) { this->destroy_node( this->head.next ); } else { node_base** _current{ &this->head.next }; while ( ( *_current )->next->next ) { _current = &( ( *_current )->next ); } this->destroy_node( ( *_current )->next ); ( *_current )->next = nullptr; } } template < typename T, typename Allocator > void linked_list< T, Allocator >::push_back( const_reference _value ) { if ( !this->head.next ) { this->head.next = this->construct_node( _value ); } else { node_base** _current{ &this->head.next }; while ( ( *_current )->next ) { _current = &( ( *_current )->next ); } ( *_current )->next = this->construct_node( _value ); } } template < typename T, typename Allocator > void linked_list< T, Allocator >::push_back( value_type&& _value ) { if ( !this->head.next ) { this->head.next = this->construct_node( std::forward< value_type >( _value ) ); } else { node_base** _current{ &this->head.next }; while ( ( *_current )->next ) { _current = &( ( *_current )->next ); } ( *_current )->next = this->construct_node( std::forward< value_type >( _value ) ); } } template < typename T, typename Allocator > template < typename... Args > typename linked_list< T, Allocator >::reference linked_list< T, Allocator >::emplace_back( Args&&... args ) { if ( !this->head.next ) { this->head.next = this->construct_node( std::forward< Args >( args )... ); return ( static_cast< node* >( this->head.next )->data ); } else { node_base** _current{ &this->head.next }; while ( ( *_current )->next ) { _current = &( ( *_current )->next ); } ( *_current )->next = this->construct_node( std::forward< Args >( args )... ); return ( static_cast< node* >( ( *_current )->next )->data ); } } template < typename T, typename Allocator > void linked_list< T, Allocator >::resize( size_type _count ) { node_base** _current{ &this->head.next }; if ( !( *_current ) ) { for ( ; _count; --_count, _current = &( ( *_current )->next ) ) { *_current = this->construct_node(); } } else { while ( --_count && ( *_current )->next ) { _current = &( ( *_current )->next ); } if ( _count ) { for ( ; _count; --_count, _current = &( ( *_current )->next ) ) { ( *_current )->next = this->construct_node(); } } else { for ( node_base** _next{} ; ( *_current )->next; ( *_current )->next = *_next ) { _next = &( ( *_current )->next->next ); this->destroy_node( ( *_current )->next ); } } } } template < typename T, typename Allocator > void linked_list< T, Allocator >::resize( size_type _count, const_reference _value ) { node_base** _current{ &this->head.next }; if ( !( *_current ) ) { for ( ; _count; --_count, _current = &( ( *_current )->next ) ) { *_current = this->construct_node( _value ); } } else { while ( --_count && ( *_current )->next ) { _current = &( ( *_current )->next ); } if ( _count ) { for ( ; _count; --_count, _current = &( ( *_current )->next ) ) { ( *_current )->next = this->construct_node( _value ); } } else { for ( node_base** _next{} ; ( *_current )->next; ( *_current )->next = *_next ) { _next = &( ( *_current )->next->next ); this->destroy_node( ( *_current )->next ); } } } } template < typename T, typename Allocator > void linked_list< T, Allocator >::swap( linked_list< T, Allocator >& other ) { std::swap( this->head.next, other.head.next ); } template < typename T, typename Allocator > template < typename... Args > typename linked_list< T, Allocator >::node* linked_list< T, Allocator >::construct_node( Args&&... args ) { node* _tmp{ allocator_traits::allocate( this->allocator, 1 ) }; allocator_traits::construct( this->allocator, _tmp, std::forward< Args >( args )... ); return _tmp; } template < typename T, typename Allocator > void linked_list< T, Allocator >::destroy_node( node_base* ptr ) { allocator_traits::destroy( this->allocator, static_cast< node* >( ptr ) ); allocator_traits::deallocate( this->allocator, static_cast< node* >( ptr ), 1 ); } template < typename T, typename Allocator > bool operator == ( const linked_list< T, Allocator >& lhs, const linked_list< T, Allocator >& rhs ) { typename linked_list< T, Allocator >::const_iterator _it_lhs{ lhs.cbegin() }; typename linked_list< T, Allocator >::const_iterator _it_rhs{ rhs.cbegin() }; for ( ; ( _it_lhs != lhs.cend() ) && ( _it_rhs != rhs.cend() ); ++_it_lhs, ++_it_rhs ) { if ( *_it_lhs != *_it_rhs ) { return false; } } return ( _it_lhs == lhs.cend() && _it_rhs == rhs.cend() ); } template < typename T, typename Allocator > bool operator != ( const linked_list< T, Allocator >& lhs, const linked_list< T, Allocator >& rhs ) { typename linked_list< T, Allocator >::const_iterator _it_lhs{ lhs.cbegin() }; typename linked_list< T, Allocator >::const_iterator _it_rhs{ rhs.cbegin() }; for ( ; ( _it_lhs != lhs.cend() ) && ( _it_rhs != rhs.cend() ); ++_it_lhs, ++_it_rhs ) { if ( *_it_lhs != *_it_rhs ) { return true; } } return !( _it_lhs == lhs.cend() && _it_rhs == rhs.cend() ); } template < typename T, typename Allocator > bool operator < ( const linked_list< T, Allocator >& lhs, const linked_list< T, Allocator >& rhs ) { typename linked_list< T, Allocator >::const_iterator _it_lhs{ lhs.cbegin() }; typename linked_list< T, Allocator >::const_iterator _it_rhs{ rhs.cbegin() }; for ( ; ( _it_lhs != lhs.cend() ) && ( _it_rhs != rhs.cend() ); ++_it_lhs, ++_it_rhs ) { if ( *_it_lhs < *_it_rhs ) { return true; } if ( *_it_rhs < *_it_lhs ) { return false; } } return ( _it_lhs == lhs.cend() && _it_rhs != rhs.cend() ); } template < typename T, typename Allocator > bool operator <= ( const linked_list< T, Allocator >& lhs, const linked_list< T, Allocator >& rhs ) { typename linked_list< T, Allocator >::const_iterator _it_lhs{ lhs.cbegin() }; typename linked_list< T, Allocator >::const_iterator _it_rhs{ rhs.cbegin() }; for ( ; ( _it_lhs != lhs.cend() ) && ( _it_rhs != rhs.cend() ); ++_it_lhs, ++_it_rhs ) { if ( *_it_lhs < *_it_rhs ) { return true; } if ( *_it_rhs < *_it_lhs ) { return false; } } return ( _it_lhs == lhs.cend() ); } template < typename T, typename Allocator > bool operator > ( const linked_list< T, Allocator >& lhs, const linked_list< T, Allocator >& rhs ) { typename linked_list< T, Allocator >::const_iterator _it_lhs{ lhs.cbegin() }; typename linked_list< T, Allocator >::const_iterator _it_rhs{ rhs.cbegin() }; for ( ; ( _it_lhs != lhs.cend() ) && ( _it_rhs != rhs.cend() ); ++_it_lhs, ++_it_rhs ) { if ( *_it_lhs > *_it_rhs ) { return true; } if ( *_it_rhs > *_it_lhs ) { return false; } } return ( _it_rhs == rhs.cend() && _it_lhs != lhs.cend() ); } template < typename T, typename Allocator > bool operator >= ( const linked_list< T, Allocator >& lhs, const linked_list< T, Allocator >& rhs ) { typename linked_list< T, Allocator >::const_iterator _it_lhs{ lhs.cbegin() }; typename linked_list< T, Allocator >::const_iterator _it_rhs{ rhs.cbegin() }; for ( ; ( _it_lhs != lhs.cend() ) && ( _it_rhs != rhs.cend() ); ++_it_lhs, ++_it_rhs ) { if ( *_it_lhs > *_it_rhs ) { return true; } if ( *_it_rhs > *_it_lhs ) { return false; } } return ( _it_rhs != rhs.cend() ); } #include #include int main( int argc, char* argv[] ) { linked_list< std::string > _to_do_list { "Some entry", "Custom memory allocation system", "Intelligent Systems", "Design Patterns", "Big Integers", "Data Structures" }; _to_do_list.push_front( "Revision of old codes" ); _to_do_list.push_back( "Code Coach problems" ); _to_do_list.insert_after( _to_do_list.cbegin(), "Tuples and Typelists" ); _to_do_list.emplace_back( "Some entry" ); _to_do_list.erase_after( _to_do_list.cbegin() ); _to_do_list.pop_back(); _to_do_list.resize( 10, "No entry..." ); std::cout << "SoloLearn To-Do-List:\n" << "~~~~~~~~~~~~~~~~~~~~~\n"; for ( const auto& el : _to_do_list ) { std::cout << "$ " << el << std::endl; } return 0; }

Sololearn To-Do List