1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
|
#include <iostream>
#include <iterator>
#include <memory>
#include <cstdlib>
#include <type_traits>
#include <initializer_list>
namespace my
{
template < typename T > struct vector
{
using value_type = T ;
using size_type = std::size_t ;
using difference_type = std::ptrdiff_t ;
using reference = value_type& ;
using const_reference = const value_type& ;
using pointer = value_type* ;
using const_pointer = const value_type* ;
using iterator = pointer ;
using const_iterator = const_pointer ;
using reverse_iterator = std::reverse_iterator<iterator> ;
using const_reverse_iterator = std::reverse_iterator<const_iterator> ;
bool empty() const noexcept { return size() == 0 ; }
size_type size() const noexcept { return sz ; }
size_type capacity() const noexcept { return cap ; }
template< typename INPUT_ITERATOR > vector( INPUT_ITERATOR begin, INPUT_ITERATOR end )
{ for( ; begin != end ; ++begin ) push_back(*begin) ; }
template < typename U > vector( std::initializer_list<U> ilist ) : vector( ilist.begin(), ilist.end() ) {}
~vector() { if(first) { destroy( first, size() ) ; deallocate(first) ; } }
// TO DO: copy, assign, swap, move
iterator begin() noexcept { return first ; }
iterator end() noexcept { return begin() + size() ; }
const_iterator begin() const noexcept { return first ; }
const_iterator end() const noexcept { return begin() + size() ; }
const_iterator cbegin() const noexcept { return first ; }
const_iterator cend() const noexcept { return begin() + size() ; }
reverse_iterator rbegin() noexcept { return reverse_iterator( end() ) ; }
reverse_iterator rend() noexcept { return reverse_iterator( begin() ) ; }
const_reverse_iterator rbegin() const noexcept { return reverse_iterator( end() ) ; }
const_reverse_iterator rend() const noexcept { return reverse_iterator( begin() ) ; }
const_reverse_iterator crbegin() const noexcept { return reverse_iterator( end() ) ; }
const_reverse_iterator crend() const noexcept { return reverse_iterator( begin() ) ; }
void push_back( const T& v )
{
reserve( size() + 1 ) ;
construct( first+size(), v ) ;
++sz ;
}
void push_back( T&& v )
{
reserve( size() + 1 ) ;
construct( first+size(), std::move(v) ) ;
++sz ;
}
template < typename... CTOR_ARGS > void emplace_back( CTOR_ARGS&&... args )
{
reserve( size() + 1 ) ;
construct( first+size(), std::forward<CTOR_ARGS>(args)... ) ;
++sz ;
}
// TO DO: pop_back, lots more stuff
void reserve( size_type requested_cap )
{
if( requested_cap > cap )
{
const auto n = recommended_capacity(requested_cap) ;
// allocate uninitialised storage for n items
T* new_buff = allocate(n) ;
if( first != nullptr )
{
// move construct / copy construct items in uninitialised storage
// move only if the move-constructor is guaranteed not to throw
// TO DO: support the basic guarantee for exception safety see: https://www.stroustrup.com/3rd_safe.pdf
if constexpr(CAN_MOVE_T)
std::uninitialized_copy_n( std::make_move_iterator(first), size(), new_buff ) ;
else std::uninitialized_copy_n( first, size(), new_buff ) ;
destroy( first, size() ) ; // destroy moved from / copied from items
deallocate(first) ; // release old buffer
}
// use new_buf
first = new_buff ;
cap = n ;
}
}
private:
size_type sz = 0 ;
size_type cap = 0 ;
T* first = nullptr ;
static constexpr std::size_t T_SIZE = sizeof(T) ;
static constexpr std::size_t T_ALIGN = alignof(T) ;
static constexpr bool CAN_MOVE_T = std::is_nothrow_move_constructible_v<T> ;
size_type recommended_capacity( size_type requested_cap ) const noexcept
{
// TO DO: fine tune as required
size_type rec_sz = sz * 2 ; // default: small allocation; double current size
if( size() * T_SIZE > 64 * 1024 ) rec_sz = sz * 4 / 3 ; // large allocation; increase by 50%
else if( size() * T_SIZE > 16 * 1024 ) rec_sz = sz * 7 / 3 ; // medium allocation; increase by 75%
// return larger of these (we always allocate space for at least 16 items).
return std::max( std::max( requested_cap, rec_sz ), size_type(16) ) ;
}
T* allocate( size_type n ) // allocate uninitialised storage
{
// std::aligned_alloc: https://en.cppreference.com/w/cpp/memory/c/aligned_alloc
return static_cast<T*>( std::aligned_alloc( T_ALIGN, T_SIZE * n ) ) ;
}
// invariant: buffer is a pointer returned earlier by allocate
void deallocate( T* buffer ) { std::free(buffer) ; }
// in-place construct at location pointed to by where
T* construct( T* where, const T& v ) { return ::new (where) T(v) ; } // copy construct
T* construct( T* where, T&& v ) { return ::new (where) T( std::move(v) ) ; } // move construct
template < typename... CTOR_ARGS > T* construct( T* where, CTOR_ARGS&&... args ) // contruct from args
{ return ::new (where) T( std::forward<CTOR_ARGS>(args)... ) ; }
void destroy( T* p ) { p->T::~T() ; } // destroy without releasing memory
void destroy( T* beg, size_type n ) { for( size_type i = 0 ; i < n ; ++i ) destroy(beg+i) ; }
};
}
#include <string>
#include <algorithm>
int main()
{
const auto print = []( const auto& seq ) { for( const auto& v : seq ) std::cout << v << ' ' ; std::cout << '\n' ; };
my::vector<std::string> vec { "how", "now", "brown", "cow" } ;
vec.emplace_back( 4, 'd' ) ;
print(vec) ;
std::sort( std::begin(vec), std::end(vec) ) ;
print(vec) ;
while( vec.size() < 20 ) vec.emplace_back() ; // to test reserve
std::cout << vec.size() << ' ' << vec.capacity() << '\n' ;
vec.reserve(2000) ;
std::cout << vec.size() << ' ' << vec.capacity() << '\n' ;
}
|