#include // For std::out_of_range #include // For std::exchange // Don't worry about this :) #if defined(__clang__) #define _attribute(n) __attribute__ ((n)) #elif defined(__GNUC__) || defined(__GNUG__) #define _attribute(n) __attribute__ ((n)) #elif defined(_MSC_VER) #define _attribute(n) #endif _attribute(const) uint64_t clz( uint64_t x ) { static const uint8_t table[32] = { 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; if( x == 0 ) return 64; int n = 0; for( ; (( x & 0xF000000000000000 ) == 0); n += 4, x <<= 4 ){} return n + (int)table[ x >> (63-4) ]; } _attribute(const) uint64_t nextPowerOf2( uint64_t n ) { return 1ull << ( 64 - clz( n ) ); } // namespace custom { template> class vector { public: template class RandomAccessIterator; using value_type = T; using allocator_type = Allocator; using size_type = size_t; using difference_type = std::ptrdiff_t; using reference = value_type&; using const_reference = const value_type&; using pointer = typename std::allocator_traits::pointer; using const_pointer = typename std::allocator_traits::const_pointer; using iterator = RandomAccessIterator; using const_iterator = RandomAccessIterator; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; public: vector() = default; vector( size_t initialSize ); vector( const vector& other ); vector( vector&& other ) noexcept; vector( std::initializer_list init ); vector& operator=( const vector& other ); vector& operator=( vector&& other ) noexcept; vector& operator=( std::initializer_list init ); ~vector(); void push_back( const T& data ); void pop_back(); T& operator[]( size_t index ); const T& operator[]( size_t index ) const; T& at( size_t index ); const T& at( size_t index ) const; T& front(); const T& front() const; T& back(); const T& back() const; T* data() noexcept; const T* data() const noexcept; void swap( vector& other ) noexcept; size_t size() const noexcept; bool empty() const noexcept; void clear() noexcept; size_t capacity() const noexcept; // Still a few functions to go... template class RandomAccessIterator : public std::iterator< std::random_access_iterator_tag, PT, ptrdiff_t, PT*, PT& > { private: PT* mPtr; public: explicit RandomAccessIterator( PT* ptr = nullptr ) : mPtr( ptr ){} RandomAccessIterator& operator++() { ++mPtr; return *this; } RandomAccessIterator operator++(int) { RandomAccessIterator __tmp = *this; ++mPtr; return __tmp; } RandomAccessIterator& operator--() { --mPtr; return *this; } RandomAccessIterator operator--(int) { RandomAccessIterator __tmp = *this; --mPtr; return __tmp; } bool operator==( const RandomAccessIterator& other ) const { return mPtr == other.mPtr; } bool operator!=( const RandomAccessIterator& other ) const { return !(operator==( other )); } RandomAccessIterator operator+( const ptrdiff_t& offset ) const { RandomAccessIterator __tmp = *this; __tmp.mPtr += offset; return __tmp; } RandomAccessIterator operator-( const ptrdiff_t& offset ) const { RandomAccessIterator __tmp = *this; __tmp.mPtr -= offset; return __tmp; } ptrdiff_t operator-( const RandomAccessIterator& it ) const { return std::distance( it.mPtr, mPtr ); } PT& operator*() { return *mPtr; } const PT& operator*() const { return *mPtr; } PT* operator->() { return &(operator*()); } const PT* operator->() const { return &(operator*()); } operator bool() const { return mPtr != nullptr; } }; iterator begin() noexcept; iterator end() noexcept; const_iterator begin() const noexcept; const_iterator end() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; reverse_iterator rbegin(); reverse_iterator rend() noexcept; const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; private: void reallocate( size_t newSize ); void range_check( size_t index ) const; template void storage_reuse_optimization( Container&& c ); private: T* mData = nullptr; size_t mSize = 0; size_t mCap = 0; }; template vector::vector( size_t initialSize ) : mData( Allocator{}.allocate( initialSize ) ), mSize( initialSize ), mCap( initialSize ) { std::fill( mData, mData + initialSize, T() ); } template vector::vector( const vector& other ) : mData( Allocator{}.allocate( other.size() ) ), mSize( other.size() ), mCap( other.size() ) // Yes, did it on purpose { std::copy( other.mData, other.mData + other.size(), mData ); } template vector::vector( vector&& other ) noexcept : mData( std::exchange( other.mData, nullptr ) ), mSize( std::exchange( other.mSize, 0 ) ), mCap ( std::exchange( other.mCap, 0 ) ) { } template vector::vector( std::initializer_list init ) : mData( Allocator{}.allocate( init.size() ) ), mSize( init.size() ), mCap( init.size() ) { std::copy( init.begin(), init.end(), begin() ); } template vector& vector::operator=( const vector& other ) { if( this != &other ) // Protect against self assignment { storage_reuse_optimization( other ); } return *this; } template vector& vector::operator=( vector&& other ) noexcept { mData = std::exchange( other.mData, nullptr ); mSize = std::exchange( other.mSize, 0 ); mCap = std::exchange( other.mCap, 0 ); return *this; } template vector& vector::operator=( std::initializer_list init ) { storage_reuse_optimization( init ); } template vector::~vector() { Allocator{}.deallocate( mData, mSize ); } template void vector::push_back( const T& data ) { if( mSize == mCap ) { reallocate( nextPowerOf2( mCap ) ); } mData[ mSize++ ] = data; } template void vector::pop_back() { --mSize; } template T& vector::operator[]( size_t index ) { return mData[index]; } template const T& vector::operator[]( size_t index ) const { return mData[index]; } template T& vector::at( size_t index ) { range_check( index ); return mData[index]; } template const T& vector::at( size_t index ) const { range_check( index ); return mData[index]; } template T& vector::front() { return mData[0]; } template const T& vector::front() const { return mData[0]; } template T& vector::back() { return mData[mSize-1]; } template const T& vector::back() const { return mData[mSize-1]; } template T* vector::data() noexcept { return mData; } template const T* vector::data() const noexcept { return mData; } template void vector::swap( vector& other ) noexcept { std::swap( *this, other ); } template size_t vector::size() const noexcept { return mSize; } template bool vector::empty() const noexcept { return mSize == 0; } template void vector::clear() noexcept { mSize = 0; } template size_t vector::capacity() const noexcept { return mCap; } template void vector::reallocate( size_t newSize ) { Allocator allocator; T* newData = allocator.allocate( newSize ); if( mData ) { std::copy( mData, mData + size(), newData ); allocator.deallocate( mData, size() ); } mData = newData; mCap = newSize; } template void vector::range_check( size_t index ) const { if( index >= mSize ) throw std::out_of_range( "vector::range_check: __index (which is " + std::to_string( index ) + ") >= this->size() (which is " + std::to_string( mSize ) + ")" ); } template template void vector::storage_reuse_optimization( Container&& c ) { if( c.size() != size() ) { Allocator allocator; allocator.deallocate( mData, size() ); mCap = 0; mSize = 0; mData = nullptr; // If the next allocation fails, then mCap, mSize and mData are left in a usable state mData = allocator.allocate( c.size() ); mSize = c.size(); mCap = c.size(); } std::copy( std::begin(c), std::end(c), begin() ); } template typename vector::iterator vector::begin() noexcept { return iterator( &mData[0] ); } template typename vector::iterator vector::end() noexcept { return iterator( &mData[size()] ); } template typename vector::const_iterator vector::begin() const noexcept { return cbegin(); } template typename vector::const_iterator vector::end() const noexcept { return cend(); } template typename vector::const_iterator vector::cbegin() const noexcept { return const_iterator( &mData[0] ); } template typename vector::const_iterator vector::cend() const noexcept { return const_iterator( &mData[size()] ); } template typename vector::reverse_iterator vector::rbegin() { return reverse_iterator( end() ); } template typename vector::reverse_iterator vector::rend() noexcept { return reverse_iterator( begin() ); } template typename vector::const_reverse_iterator vector::crbegin() const noexcept { return const_reverse_iterator( cend() ); } template typename vector::const_reverse_iterator vector::crend() const noexcept { return const_reverse_iterator( cbegin() ); } } #include #include #include #include #include // Returns CPU clock cycle count since CPU, useful for random numbers and calculating clock cycles :) uint64_t rdtsc() { uint32_t l, h; __asm__ __volatile__( "rdtsc" : "=a"(l), "=d"(h) ); return (uint64_t)h << 32 | l; } // Everything still works if you replace custom with std here #define vec custom::vector template class allocator { public: using value_type = T; public: allocator() = default; template constexpr allocator ( const allocator & ) noexcept {} [[nodiscard]] constexpr T* allocate( std::size_t n ); constexpr void deallocate( T* p, std::size_t n ); private: void report( T* p, std::size_t n, bool alloc = true ) const { std::cout << ( alloc ? "Alloc: " : "Dealloc: " ) << sizeof( T ) * n << " bytes at " << std::hex << std::showbase << reinterpret_cast( p ) << std::dec << '\n'; } }; template constexpr T* allocator::allocate( std::size_t n ) { if( n > std::numeric_limits::max() / sizeof( T ) ) { throw std::bad_alloc(); } if( auto p = static_cast( std::malloc( n * sizeof( T ) ) ) ) { report(p, n); return p; } throw std::bad_alloc(); } template constexpr void allocator::deallocate( T* p, std::size_t n ) { report(p, n, 0); std::free( p ); } template bool operator==(const allocator &, const allocator &) { return true; } template bool operator!=(const allocator &, const allocator &) { return false; } class Foo { public: Foo( int a ) : m_A( a ) { std::cout << "Foo con\n"; } Foo( const Foo& o ) : m_A( o.m_A ){ std::cout << "Foo copy con\n"; } Foo& operator=( const Foo& o ){ m_A = o.m_A; std::cout << "Foo assignment op\n"; return *this; } ~Foo(){ std::cout << "Foo decon\n"; } operator int() const noexcept { return m_A; } private: int m_A; }; int main() { vec> v{ 5, 4, 9 }, t; std::cout << "Print v info:\n"; for( const auto& i : v ) std::cout << i << ' '; std::cout << "\n\nFront: " << v.front() << " Back: " << v.back() << '\n'; std::cout << "Size: " << v.size() << " Capacity: " << v.capacity() << '\n'; std::cout << "Sum: " << std::accumulate( v.begin(), v.end(), 0 ) << '\n'; std::cout << "Copy v to t\n"; t = v; std::cout << "Destroy v\n"; vec>().swap( v ); // Guaranteed destruction of data, it's a common idiom // ' https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Clear-and-minimize ' for more std::cout << "Change t[1] to 7\n"; // Check t[1] to 7 t[1] = 7; // Enhanced loops work std::cout << "\nEnhanced for loop:\n"; for( const auto& i : t ) std::cout << i << ' '; std::cout << "\n\nMultiply everything by a random number using std::transform\n"; std::transform( t.begin(), t.end(), t.begin(), []( const auto& i ){ return i * (rdtsc() % 200); } ); std::cout << "\n\nIterator:\n"; for( /*auto*/vec>::iterator it = t.begin(); it != t.end(); ++it ){ std::cout << *it << ' '; } std::cout << "\n\nReverse_Iterator:\n"; for( /*auto*/vec>::reverse_iterator it = t.rbegin(); it != t.rend(); ++it ){ std::cout << *it << ' '; } std::cout << "\n\nExcessing out of bounds:\n"; try { t.at( -3198644341589729085 ); }catch( std::out_of_range& e ) { std::cout << "\nCaught an out_of_range exception:\n" << e.what() << '\n'; } }

Vector Implementation