#include #include #include #include #include #include namespace cs { namespace { inline constexpr std::size_t __DEFAULT_CAPACITY__ = 8; } // anonymous namespace template < typename T > class random_access_iterator { public: using iterator_category = std::random_access_iterator_tag; using value_type = T; using difference_type = std::ptrdiff_t; using pointer = T*; using reference = T&; private: template < typename _T > friend random_access_iterator< _T > operator + ( const random_access_iterator< _T >&, const typename random_access_iterator< _T >::difference_type ) noexcept; template < typename _T > friend random_access_iterator< _T > operator + ( const typename random_access_iterator< _T >::difference_type, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend random_access_iterator< _T > operator - ( const random_access_iterator< _T >&, const typename random_access_iterator< _T >::difference_type ) noexcept; template < typename _T > friend typename random_access_iterator< _T >::difference_type operator - ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend bool operator < ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend bool operator > ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend bool operator <= ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend bool operator >= ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend bool operator == ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; template < typename _T > friend bool operator != ( const random_access_iterator< _T >&, const random_access_iterator< _T >& ) noexcept; public: explicit random_access_iterator( pointer _ptr = nullptr ) noexcept : m_ptr{ _ptr } {} random_access_iterator& operator ++ () noexcept { ++this->m_ptr; return *this; } random_access_iterator operator ++ ( int ) noexcept { random_access_iterator _tmp{ *this }; ++this->m_ptr; return _tmp; } random_access_iterator& operator -- () noexcept { --this->m_ptr; return *this; } random_access_iterator operator -- ( int ) noexcept { random_access_iterator _tmp{ *this }; --this->m_ptr; return _tmp; } random_access_iterator& operator += ( const difference_type distance ) noexcept { this->m_ptr += distance; return *this; } random_access_iterator& operator -= ( const difference_type distance ) noexcept { this->m_ptr -= distance; return *this; } reference operator [] ( const difference_type distance ) noexcept { return *( this->m_ptr + distance ); } const reference operator [] ( const difference_type distance ) const noexcept { return *( this->m_ptr + distance ); } reference operator * () noexcept { return *this->m_ptr; } const reference operator * () const noexcept { return *this->m_ptr; } pointer operator -> () noexcept { return this->m_ptr; } const pointer operator -> () const noexcept { return this->m_ptr; } bool operator () () const noexcept { return ( this->m_ptr != nullptr ); } private: pointer m_ptr; }; template < typename T > random_access_iterator< T > operator + ( const random_access_iterator< T >& it, const typename random_access_iterator< T >::difference_type distance ) noexcept { return random_access_iterator{ it.m_ptr + distance }; } template < typename T > random_access_iterator< T > operator + ( const typename random_access_iterator< T >::difference_type distance, const random_access_iterator< T >& it ) noexcept { return ( it + distance ); } template < typename T > random_access_iterator< T > operator - ( const random_access_iterator< T >& it, const typename random_access_iterator< T >::difference_type distance ) noexcept { return random_access_iterator{ it.m_ptr - distance }; } template < typename T > typename random_access_iterator< T >::difference_type operator - ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return ( left.m_ptr - right.m_ptr ); } template < typename T > bool operator < ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return ( left.m_ptr < right.m_ptr ); } template < typename T > bool operator > ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return ( right < left ); } template < typename T > bool operator <= ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return !( right < left ); } template < typename T > bool operator >= ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return !( left < right ); } template < typename T > bool operator == ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return ( left.m_ptr == right.m_ptr ); } template < typename T > bool operator != ( const random_access_iterator< T >& left, const random_access_iterator< T >& right ) noexcept { return !( left == right ); } template < typename T, typename Allocator = std::allocator< T > > class dynamic_array { private: template < typename _T, typename _Allocator > friend bool operator < ( const dynamic_array< _T, _Allocator >&, const dynamic_array< _T, _Allocator >& ) noexcept; template < typename _T, typename _Allocator > friend bool operator > ( const dynamic_array< _T, _Allocator >&, const dynamic_array< _T, _Allocator >& ) noexcept; template < typename _T, typename _Allocator > friend bool operator <= ( const dynamic_array< _T, _Allocator >&, const dynamic_array< _T, _Allocator >& ) noexcept; template < typename _T, typename _Allocator > friend bool operator >= ( const dynamic_array< _T, _Allocator >&, const dynamic_array< _T, _Allocator >& ) noexcept; template < typename _T, typename _Allocator > friend bool operator == ( const dynamic_array< _T, _Allocator >&, const dynamic_array< _T, _Allocator >& ) noexcept; template < typename _T, typename _Allocator > friend bool operator != ( const dynamic_array< _T, _Allocator >&, const dynamic_array< _T, _Allocator >& ) noexcept; public: using value_type = T; using allocator_type = Allocator; 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 move_reference = value_type&&; using pointer = typename allocator_traits::pointer; using const_pointer = typename allocator_traits::const_pointer; using iterator = random_access_iterator< value_type >; using const_iterator = random_access_iterator< const value_type >; using reverse_iterator = std::reverse_iterator< iterator >; using const_reverse_iterator = std::reverse_iterator< const_iterator >; private: void allocate( size_type = __DEFAULT_CAPACITY__ ); void reallocate(); void reallocate( size_type ); void deallocate(); public: dynamic_array(); explicit dynamic_array( const allocator_type& ); explicit dynamic_array( size_type, const allocator_type& = allocator_type() ); dynamic_array( size_type, const_reference, const allocator_type& = allocator_type() ); dynamic_array( std::initializer_list< value_type >, const allocator_type& = allocator_type() ); template < typename InputIt > dynamic_array ( InputIt, InputIt, std::enable_if_t< std::is_convertible_v< std::iterator_traits< InputIt >::iterator_category, std::input_iterator_tag >, const allocator_type& > = allocator_type() ); dynamic_array( const dynamic_array& ); dynamic_array( const dynamic_array&, const allocator_type& ); dynamic_array( dynamic_array&& ); dynamic_array( dynamic_array&&, const allocator_type& = allocator_type() ); virtual ~dynamic_array(); dynamic_array& operator = ( const dynamic_array& ); dynamic_array& operator = ( dynamic_array&& ); dynamic_array& operator = ( std::initializer_list< value_type > ); void assign( size_type, const_reference ); void assign( std::initializer_list< value_type > ); template < typename InputIt > auto assign ( InputIt, InputIt ) -> std::enable_if_t< std::is_convertible_v< std::iterator_traits< InputIt >::iterator_category, std::input_iterator_tag >, void >; reference at( const size_type ); const_reference at( const size_type ) const; reference operator [] ( const size_type ); const_reference operator [] ( const size_type ) const; inline reference front() { return *this->m_begin; } inline const_reference front() const { return *this->m_begin; } inline reference back() { return *( this->m_end - 1 ); } inline const_reference back() const { return *( this->m_end - 1 ); } inline pointer data() { return this->m_begin; } inline const_pointer data() const { return this->m_begin; } inline iterator begin() { return random_access_iterator< value_type >{ this->m_begin }; } inline const_iterator begin() const { return random_access_iterator< const value_type >{ this->m_begin }; } inline const_iterator cbegin() const { return random_access_iterator< const value_type >{ this->m_begin }; } inline iterator end() { return random_access_iterator< value_type >{ this->m_end }; } inline const_iterator end() const { return random_access_iterator< const value_type >{ this->m_end }; } inline const_iterator cend() const { return random_access_iterator< const value_type >{ this->m_end }; } inline reverse_iterator rbegin() { return std::make_reverse_iterator( this->end() ); } inline const_reverse_iterator rbegin() const { return std::make_reverse_iterator( this->cend() ); } inline const_reverse_iterator crbegin() const { return std::make_reverse_iterator( this->cend() ); } inline reverse_iterator rend() { return std::make_reverse_iterator( this->begin() ); } inline const_reverse_iterator rend() const { return std::make_reverse_iterator( this->cbegin() ); } inline const_reverse_iterator crend() const { return std::make_reverse_iterator( this->cbegin() ); } inline allocator_type get_allocator() const { return this->m_allocator; } inline bool empty() const { return ( this->m_begin == this->m_end ); } inline size_type size() const { return ( this->m_end - this->m_begin ); } inline size_type capacity() const { return ( this->m_end_of_storage - this->m_begin ); } void reserve( size_type ); void shrink_to_fit(); void clear(); iterator insert( const_iterator, const_reference ); iterator insert( const_iterator, move_reference ); iterator insert( const_iterator, size_type, const_reference ); iterator insert( const_iterator, std::initializer_list< value_type > ); template < typename InputIt > auto insert( const_iterator, InputIt, InputIt ) -> std::enable_if_t< std::is_convertible_v< std::iterator_traits< InputIt >::iterator_category, std::input_iterator_tag >, iterator >; template < typename... Args > iterator emplace( const_iterator, Args&&... ); iterator erase( const_iterator ); iterator erase( const_iterator, const_iterator ); size_type erase ( const_reference ); template < typename Predicate > auto erase( Predicate ) -> std::enable_if_t< std::is_invocable_v< Predicate, value_type >, size_type >; void push_back( const_reference ); void push_back( move_reference ); template < typename... Args > void emplace_back( Args&&... ); void pop_back(); void resize( size_type ); void resize( size_type, const_reference ); void swap( dynamic_array& ); private: pointer m_begin; pointer m_end; pointer m_end_of_storage; allocator_type m_allocator; }; template < typename InputIt, typename Allocator = std::allocator< typename std::iterator_traits< InputIt >::value_type > > dynamic_array( InputIt, InputIt, Allocator = Allocator() ) -> dynamic_array< typename std::iterator_traits< InputIt >::value_type, Allocator >; template < typename T, typename Allocator > void dynamic_array< T, Allocator >::allocate( size_type capacity ) { this->m_begin = allocator_traits::allocate( this->m_allocator, capacity ); this->m_end = this->m_begin; this->m_end_of_storage = this->m_begin + capacity; } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::reallocate() { size_type old_size = this->size(); size_type new_capacity = this->capacity() << 1; pointer _tmp = allocator_traits::allocate( this->m_allocator, new_capacity ); for ( pointer it{ this->m_begin }, first{ _tmp }; it != this->m_end; ++it ) { allocator_traits::construct( this->m_allocator, first++, std::move( *it ) ); } this->deallocate(); this->m_begin = _tmp; this->m_end = this->m_begin + old_size; this->m_end_of_storage = this->m_begin + new_capacity; } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::reallocate( size_type new_capacity ) { size_type old_size = this->size(); pointer _tmp = allocator_traits::allocate( this->m_allocator, new_capacity ); for ( pointer it{ this->m_begin }, first{ _tmp }; it != this->m_end; ++it ) { allocator_traits::construct( this->m_allocator, first++, std::move( *it ) ); } this->deallocate(); this->m_begin = _tmp; this->m_end = this->m_begin + old_size; this->m_end_of_storage = this->m_begin + new_capacity; } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::deallocate() { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } allocator_traits::deallocate( this->m_allocator, this->m_begin, this->capacity() ); this->m_begin = nullptr; this->m_end = nullptr; this->m_end_of_storage = nullptr; } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array() : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator_type() } { this->allocate(); } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( const allocator_type& allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { this->allocate(); } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( size_type size, const allocator_type& allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { this->allocate( ( __DEFAULT_CAPACITY__ < size ? size : __DEFAULT_CAPACITY__ ) ); while ( size-- ) { allocator_traits::construct( this->m_allocator, this->m_end++ ); } } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( size_type size, const_reference value, const allocator_type& allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { this->allocate( ( __DEFAULT_CAPACITY__ < size ? size : __DEFAULT_CAPACITY__ ) ); while ( size-- ) { allocator_traits::construct( this->m_allocator, this->m_end++, value ); } } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( std::initializer_list< value_type > init, const allocator_type& allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { size_type size = init.size(); this->allocate( ( __DEFAULT_CAPACITY__ < size ? size : __DEFAULT_CAPACITY__ ) ); for ( auto it{ init.begin() }; it != init.end(); ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, *it ); } } template < typename T, typename Allocator > template < typename InputIt > dynamic_array< T, Allocator >::dynamic_array ( InputIt first, InputIt last, std::enable_if_t< std::is_convertible_v< std::iterator_traits< InputIt >::iterator_category, std::input_iterator_tag >, const allocator_type& > allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { difference_type size = std::distance( first, last ); this->allocate( ( __DEFAULT_CAPACITY__ < size ? size : __DEFAULT_CAPACITY__ ) ); while ( first != last ) { allocator_traits::construct( this->m_allocator, this->end++, std::move( *first++ ) ); } } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( const dynamic_array< T, Allocator >& other ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator_traits::select_on_container_copy_construction( other.get_allocator() ) } { this->allocate( other.capacity() ); for ( pointer it{ other.m_begin }; it != other.m_end; ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, *it ); } } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( const dynamic_array< T, Allocator >& other, const allocator_type& allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { this->allocate( other.capacity() ); for ( pointer it{ other.m_begin }; it != other.m_end; ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, *it ); } } template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( dynamic_array< T, Allocator >&& other ) : m_begin{ std::exchange( other.m_begin, nullptr ) }, m_end{ std::exchange( other.m_end, nullptr ) }, m_end_of_storage{ std::exchange( other.m_end_of_storage, nullptr ) }, m_allocator{ std::exchange( other.m_allocator, allocator_type() ) } {} template < typename T, typename Allocator > dynamic_array< T, Allocator >::dynamic_array( dynamic_array< T, Allocator >&& other, const allocator_type& allocator ) : m_begin{ nullptr }, m_end{ nullptr }, m_end_of_storage{ nullptr }, m_allocator{ allocator } { if ( this->m_allocator == other.m_allocator ) { this->m_begin = std::exchange( other.m_begin, nullptr ); this->m_end = std::exchange( other.m_end, nullptr ); this->m_end_of_storage = std::exchange( other.m_end_of_storage, nullptr ); } else { this->allocate( other.capacity() ); for ( pointer it{ other.m_begin }; it != other.m_end; ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, std::move( *it ) ) ; } } } template < typename T, typename Allocator > dynamic_array< T, Allocator >::~dynamic_array() { this->deallocate(); } template < typename T, typename Allocator > dynamic_array< T, Allocator >& dynamic_array< T, Allocator >::operator = ( const dynamic_array< T, Allocator >& other ) { if ( this->capacity() < other.size() ) { this->deallocate(); if ( allocator_traits::propagate_on_container_copy_assignment::value ) { this->m_allocator = other.m_allocator; } this->allocatocate( other.capacity() ); } else { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } if ( allocator_traits::propagate_on_container_copy_assignment::value ) { this->m_allocator = other.m_allocator; } } for ( pointer it{ other.m_begin }; it != other.m_end; ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, *it ); } return *this; } template < typename T, typename Allocator > dynamic_array< T, Allocator >& dynamic_array< T, Allocator >::operator = ( dynamic_array< T, Allocator >&& other ) { if ( allocator_traits::propagate_on_container_move_assignment::value || ( this->m_allocator == other.m_allocator ) ) { this->m_begin = std::exchange( other.m_begin, nullptr ); this->m_end = std::exchange( other.m_end, nullptr ); this->m_end_of_storage = std::exchange( other.m_end_of_storage, nullptr ); this->m_allocator = std::exchange( other.m_allocator, allocator_type() ); } else { if ( this->capacity() < other.size() ) { this->deallocate(); this->allocate( other.capacity() ); } else { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } for ( pointer it{ other.m_begin }; it != other.m_end; ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, std::move( *it ) ); } } return *this; } template < typename T, typename Allocator > dynamic_array< T, Allocator >& dynamic_array< T, Allocator >::operator = ( std::initializer_list< value_type > values ) { size_type new_size = values.size(); if ( this->capacity() < new_size ) { this->deallocate(); this->allocate( new_size ); } else { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } for ( auto it{ values.begin() }; it != values.end(); ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, *it ); } return *this; } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::assign( size_type count, const_reference value ) { if ( this->capacity() < count ) { this->deallocate(); this->allocate( count ); } else { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } while ( count-- ) { allocator_traits::construct( this->m_allocator, this->m_end++, value ); } } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::assign( std::initializer_list< value_type > values ) { size_type new_size = values.size(); if ( this->capacity() < new_size ) { this->deallocate(); this->allocate( new_size ); } else { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } for ( auto it{ values.begin() }; it != values.end(); ++it ) { allocator_traits::construct( this->m_allocator, this->m_end++, *it ); } } template < typename T, typename Allocator > template < typename InputIt > auto dynamic_array< T, Allocator >::assign ( InputIt first, InputIt last ) -> std::enable_if_t< std::is_convertible_v< std::iterator_traits< InputIt >::iterator_category, std::input_iterator_tag >, void > { size_type new_size = std::distance( first, last ); if ( this->capacity() < new_size ) { this->deallocate(); this->allocate( new_size ); } else { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } while ( first != last ) { allocator_traits::construct( this->m_allocator, this->m_end++, *first++ ); } } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::at( const size_type index ) -> reference { if ( !( index < this->size() ) ) { throw std::out_of_range(); } return *( this->m_begin + index ); } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::at( const size_type index ) const -> const_reference { if ( !( index < this->size() ) ) { throw std::out_of_range(); } return *( this->m_begin + index ); } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::operator [] ( const size_type index ) -> reference { return *( this->m_begin + index ); } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::operator [] ( const size_type index ) const -> const_reference { return *( this->m_begin + index ); } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::reserve( size_type new_capacity ) { if ( this->capacity() < new_capacity ) { this->reallocate( new_capacity ); } } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::shrink_to_fit() { if ( !( this->size() < __DEFAULT_CAPACITY__ ) ) { this->reallocate( this->size() ); } } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::clear() { while ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::insert( const_iterator position, const_reference value ) -> iterator { difference_type distance = position - this->cbegin(); if ( this->m_end == this->m_end_of_storage ) { this->reallocate(); } pointer p = this->m_begin + distance; for ( pointer it{ this->m_end++ }; it != p; --it ) { *it = std::move( *( it - 1 ) ); } allocator_traits::construct( this->m_allocator, p, value ); return iterator{ p }; } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::insert( const_iterator position, move_reference value ) -> iterator { difference_type distance = position - this->cbegin(); if ( this->m_end == this->m_end_of_storage ) { this->reallocate(); } pointer p = this->m_begin + distance; for ( pointer it{ this->m_end++ }; it != p; --it ) { *it = std::move( *( it - 1 ) ); } allocator_traits::construct( this->m_allocator, p, std::move( value ) ); return iterator{ p }; } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::insert( const_iterator position, size_type count, const_reference value ) -> iterator { difference_type distance = position - this->cbegin(); if ( static_cast< size_type >( this->m_end_of_storage - this->m_end ) < count ) { this->reallocate( this->capacity() + count ); } pointer p = this->m_begin + distance; this->m_end += count; for ( pointer it{ this->m_end - 1 }; !( static_cast< size_type > ( it - p ) < count ); --it ) { *it = std::move( *( it - count ) ); } while ( count-- ) { allocator_traits::construct( this->m_allocator, p++, value ); } return iterator{ p - count }; } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::insert( const_iterator position, std::initializer_list< value_type > values ) -> iterator { difference_type distance = position - this->cbegin(); size_type count = values.size(); if ( static_cast< size_type >( this->m_end_of_storage - this->m_end ) < count ) { this->reallocate( this->capacity() + count ); } pointer p = this->m_begin + distance; this->m_end += count; for ( pointer it{ this->m_end - 1 }; !( static_cast< size_type > ( it - p ) < count ); --it ) { *it = std::move( *( it - count ) ); } for ( auto it{ values.begin() }; it != values.end(); ++it ) { allocator_traits::construct( this->m_allocator, p++, *it ); } return iterator{ p - count }; } template < typename T, typename Allocator > template < typename InputIt > auto dynamic_array< T, Allocator >::insert( const_iterator position, InputIt first, InputIt last ) -> std::enable_if_t< std::is_convertible_v< std::iterator_traits< InputIt >::iterator_category, std::input_iterator_tag >, iterator > { difference_type distance = position - this->cbegin(); difference_type count = std::distance( first, last ); if ( this->m_end_of_storage - this->m_end< count ) { this->reallocate( this->capacity() + count ); } pointer p = this->m_begin + distance; this->m_end += count; for ( pointer it{ this->m_end - 1 }; !( it - p < count ); --it ) { *it = std::move( *( it - count ) ); } while ( first != last ) { allocator_traits::construct( this->m_allocator, p++, *first++ ); } return iterator{ p - count }; } template < typename T, typename Allocator > template < typename... Args > auto dynamic_array< T, Allocator >::emplace( const_iterator position, Args&&... args ) -> iterator { if ( this->m_end == this->m_end_of_storage ) { this->reallocate(); } pointer p = this->m_begin + ( position - this->cbegin() ); for ( pointer it{ this->m_end++ }; it != p; --it ) { *it = std::move( *( it - 1 ) ); } allocator_traits::construct( this->m_allocator, p, std::move( args )... ); return iterator{ p }; } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::erase( const_iterator position ) -> iterator { pointer p = this->m_begin + ( position - this->cbegin() ); if ( position != this->cend() ) { allocator_traits::destroy( this->m_allocator, p ); --this->m_end; for ( pointer it{ p }; it != this->m_end; ++it ) { *it = std::move( *( it + 1 ) ); } } return iterator{ p }; } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::erase( const_iterator first, const_iterator last ) -> iterator { pointer p_first = this->m_begin + ( first - this->cbegin() ); pointer p_last = this->m_begin + ( last - this->cbegin() ); difference_type distance = p_last - p_first; if ( first != last ) { while ( p_first != p_last ) { allocator_traits::destroy( this->m_allocator, --p_last ); } this->m_end -= distance; while ( p_last != this->m_end ) { *p_last = std::move( *( p_last + distance ) ); ++p_last; } } return iterator{ p_first }; } template < typename T, typename Allocator > auto dynamic_array< T, Allocator >::erase ( const_reference value ) -> size_type { pointer p = this->m_begin; while ( *p != value ) { ++p; } if ( p != this->m_end ) { for ( pointer it{ p }; ++it != this->m_end; ) { if ( !( *it == value ) ) { *p++ = std::move( *it ); } } } difference_type distance = this->m_end - p; while ( this->m_end != p ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } return distance; } template < typename T, typename Allocator > template < typename Predicate > auto dynamic_array< T, Allocator >::erase( Predicate pred ) -> std::enable_if_t< std::is_invocable_v< Predicate, value_type >, size_type > { pointer p = this->m_begin; while ( !pred( *p ) ) { ++p; } if ( p != this->m_end ) { for ( pointer it{ p }; ++it != this->m_end; ) { if ( !pred( *it ) ) { *p++ = std::move( *it ); } } } difference_type distance = this->m_end - p; while ( this->m_end != p ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } return distance; } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::push_back( const_reference value ) { if ( this->m_end == this->m_end_of_storage ) { this->reallocate(); } allocator_traits::construct( this->m_allocator, this->m_end++, value ); } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::push_back( move_reference value ) { if ( this->m_end == this->m_end_of_storage ) { this->reallocate(); } allocator_traits::construct( this->m_allocator, this->m_end++, std::move( value ) ); } template < typename T, typename Allocator > template < typename... Args > void dynamic_array< T, Allocator >::emplace_back( Args&&... args ) { if ( this->m_end == this->m_end_of_storage ) { this->reallocate(); } allocator_traits::construct( this->m_allocator, this->m_end++, std::move( args )... ); } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::pop_back() { if ( this->m_end != this->m_begin ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::resize( size_type new_size ) { if ( new_size < this->size() ) { while ( this->m_end - this->m_begin > new_size ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } else if ( this->capacity() < new_size ) { this->reallocate( new_size ); while ( this->m_end - this->m_begin < new_size ) { allocator_traits::construct( this->m_allocator, this->m_end++ ); } } } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::resize( size_type new_size, const_reference value ) { if ( new_size < this->size() ) { while ( this->m_end - this->m_begin > new_size ) { allocator_traits::destroy( this->m_allocator, --this->m_end ); } } else if ( this->capacity() < new_size ) { this->reallocate( new_size ); while ( this->m_end - this->m_begin < new_size ) { allocator_traits::construct( this->m_allocator, this->m_end++, value ); } } } template < typename T, typename Allocator > void dynamic_array< T, Allocator >::swap( dynamic_array< T, Allocator >& other ) { std::swap( this->m_begin, other.m_begin ); std::swap( this->m_end, other.m_end ); std::swap( this->m_end_of_storage, other.m_end_of_storage ); if ( allocator_traits::propagate_on_container_swap::value ) { std::swap( this->m_allocator, other.m_allocator ); } } template < typename T, typename Allocator > bool operator < ( const dynamic_array< T, Allocator >& left, const dynamic_array< T, Allocator >& right ) noexcept { typename dynamic_array< T, Allocator >::pointer first1 = left.m_begin; typename dynamic_array< T, Allocator >::pointer first2 = right.m_begin; for ( ; ( first1 != left.m_end ) && ( first2 != right.m_end ); ++first1, ++first2 ) { if ( *first1 < *first2 ) { return true; } if ( *first2 < *first1 ) { return false; } } return ( ( first1 == left.m_end ) && ( first2 != right.m_end ) ); } template < typename T, typename Allocator > bool operator > ( const dynamic_array< T, Allocator >& left, const dynamic_array< T, Allocator >& right ) noexcept { return ( right < left ); } template < typename T, typename Allocator > bool operator <= ( const dynamic_array< T, Allocator >& left, const dynamic_array< T, Allocator >& right ) noexcept { return !( right < left ); } template < typename T, typename Allocator > bool operator >= ( const dynamic_array< T, Allocator >& left, const dynamic_array< T, Allocator >& right ) noexcept { return !( left < right ); } template < typename T, typename Allocator > bool operator == ( const dynamic_array< T, Allocator >& left, const dynamic_array< T, Allocator >& right ) noexcept { typename dynamic_array< T, Allocator >::pointer first1 = left.m_begin; typename dynamic_array< T, Allocator >::pointer first2 = right.m_begin; for ( ; ( first1 != left.m_end ) && ( first2 != right.m_end ); ++first1, ++first2 ) { if ( !( *first1 == *first2 ) ) { return false; } } return ( ( first1 == left.m_end ) && ( first2 == right.m_end ) ); } template < typename T, typename Allocator > bool operator != ( const dynamic_array< T, Allocator >& left, const dynamic_array< T, Allocator >& right ) noexcept { return !( left == right ); } } // namespace cs template < typename T, typename Allocator = std::allocator< T > > std::ostream& operator << ( std::ostream& os, const cs::dynamic_array< T, Allocator >& arr ) { os << "[ "; if ( !arr.empty() ) { os << arr.front(); for ( auto it{ arr.cbegin() + 1 }; it != arr.cend(); ++it ) { os << ", " << *it; } } os << " ]"; return os; } int main( int argc, char** argv ) { using TEST_CONTAINER = cs::dynamic_array< int >; using std::cout; using std::endl; cout << "<<< Sample Demonstration >>>\n" << "============================\n" << '\n'; cout << "Constructing vector from initializer list... "; TEST_CONTAINER c1{ 1, 2, 3, 4, 5 }; cout << "done\n" << "Vector: " << c1 << '\n' << "Size: " << c1.size() << '\n' << "Capacity: " << c1.capacity() << '\n'; cout << "\nEmplacing 0 at front... "; c1.emplace( c1.cbegin(), 0 ); cout << "done\n" << "Vector: " << c1 << '\n' << "Size: " << c1.size() << '\n' << "Capacity: " << c1.capacity() << '\n'; cout << "\nAdding missing digits at the end... "; c1.insert( c1.cend(), { 6, 7, 8, 9 } ); cout << "done\n" << "Vector: " << c1 << '\n' << "Size: " << c1.size() << '\n' << "Capacity: " << c1.capacity() << '\n'; cout << "\nPushing back another 0... "; c1.push_back( 0 ); cout << "done\n" << "Vector: " << c1 << '\n' << "Size: " << c1.size() << '\n' << "Capacity: " << c1.capacity() << '\n'; cout << "\nDeleting all values smaller than 5... "; c1.erase( []( const int n ) -> bool { return ( n < 6 ); } ); cout << "done\n" << "Vector: " << c1 << '\n' << "Size: " << c1.size() << '\n' << "Capacity: " << c1.capacity() << '\n'; cout << "\nClearing values... "; c1.clear(); cout << "done\n" << "Vector: " << c1 << '\n' << "Size: " << c1.size() << '\n' << "Capacity: " << c1.capacity() << '\n'; return EXIT_SUCCESS; }

Dynamic Arrays