> I did not pay much attention because std::vector is already perfect.
I derived a class gvector. It has a growth-factor of n and m. n is an
integral growth-factor that the vector's capacity is lineary incremented
every time it gets full. m is a float that the vector's capacity is mul-
tiplied by if it gets full. Whichever size is chosen depends on which is
greater.
Usually n is chosen that it determines the allocation-steps which are
backed by the memory-pool of the allocator. When the memory-allocator
begin to allocate the memory directly from the kernel as the block-size
gets large enough, the capacity is resized by an appropriately chosen m.
One might think that multiplying the vector's capacity by a constant
factor is a waste of memory, but keep in mind that the kernels don't
really physically allocate pages demanded from the kernel until you
really touch the memory; and memory that is only allocated to reserve
for a certain capacity isn't touched until you add elements to the
vector.
So here's my gvector:
#pragma once
#include <vector>
#include <utility>
#include <new>
#include <cassert>
template<typename T, typename Allocator = std::allocator<T>>
struct gvector : public std::vector<T, Allocator>
{
using super = std::vector<T, Allocator>;
using iterator = typename super::iterator;
using const_iterator = typename super::const_iterator;
using size_type = typename super::size_type;
explicit gvector( std::size_t growConst = 1, float growExp = 1.0,
Allocator const &alloc = Allocator() );
explicit gvector( Allocator const &alloc = Allocator() );
explicit gvector( size_type count, T const &value, Allocator const
&alloc = Allocator() );
explicit gvector( size_type count );
template<typename InputIt>
gvector( InputIt first, InputIt last, Allocator const &alloc =
Allocator() );
gvector( super const &other );
gvector( super const &other, Allocator const &alloc =
Allocator() );
gvector( super const &&other );
gvector( std::initializer_list<T> init, Allocator const &alloc
= Allocator() );
iterator insert( iterator pos, T const &value );
iterator insert( const_iterator pos, T const &value );
iterator insert( const_iterator pos, T const &&value );
iterator insert( const_iterator pos, size_type count, T const &value );
template<typename InputIt>
iterator insert( const_iterator pos, InputIt first, InputIt last );
iterator insert( const_iterator pos, std::initializer_list<T> ilist );
template<typename ... Args>
iterator emplace( const_iterator pos, Args &&...args );
void push_back( T const &value );
void push_back( T &&value );
template<typename ... Args>
void emplace_back( Args &&...args );
void set_grow( std::size_t growConst = 1, float growExp = 1.0 );
private:
void grow();
std::size_t m_growConst;
float m_growExp;
};
template<typename T, typename Allocator>
gvector<T, Allocator>::gvector( std::size_t growConst, float growExp,
Allocator const &alloc ) :
super( alloc ),
m_growConst( growConst ),
m_growExp( growExp )
{
assert(growExp >= 0.0);
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( Allocator const &alloc ) :
super( alloc ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( size_type count, T const
&value, Allocator const &alloc ) :
super( count, value, alloc ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( size_type count ) :
super( count ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
template<typename InputIt>
inline
gvector<T, Allocator>::gvector::gvector( InputIt first, InputIt last,
Allocator const &alloc ) :
super( first, last, alloc ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( super const &other ) :
super( other ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( super const &other, Allocator
const &alloc ) :
super( other, alloc ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( super const &&other ) :
super( std::move( other ) ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
gvector<T, Allocator>::gvector::gvector( std::initializer_list<T> init,
Allocator const &alloc ) :
super( init, alloc ),
m_growConst( 1 ),
m_growExp( 0.0 )
{
}
template<typename T, typename Allocator>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::insert(
iterator pos, T const &value )
{
if( super::size() == super::capacity() )
grow();
return super::insert( pos, value );
}
template<typename T, typename Allocator>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::insert(
const_iterator pos, T const &value )
{
if( super::size() == super::capacity() )
grow();
return super::insert( pos, value );
}
template<typename T, typename Allocator>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::insert(
const_iterator pos, T const &&value )
{
if( super::size() == super::capacity() )
grow();
return super::insert( pos, value );
}
template<typename T, typename Allocator>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::insert(
const_iterator pos, size_type count, T const &value )
{
if( super::size() == super::capacity() )
grow();
return super::insert( pos, count, value );
}
template<typename T, typename Allocator>
template<typename InputIt>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::insert(
const_iterator pos, InputIt first, InputIt last )
{
if( super::size() == super::capacity() )
grow();
return super::insert( pos, first, last );
}
template<typename T, typename Allocator>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::insert(
const_iterator pos, std::initializer_list<T> ilist )
{
if( super::size() == super::capacity() )
grow();
return super::insert( pos, ilist );
}
template<typename T, typename Allocator>
template<typename ... Args>
inline
typename gvector<T, Allocator>::iterator gvector<T, Allocator>::emplace(
const_iterator pos, Args &&...args )
{
if( super::size() == super::capacity() )
grow();
return super::emplace( pos, args ... );
}
template<typename T, typename Allocator>
inline
void gvector<T, Allocator>::push_back( T const &value )
{
if( super::size() == super::capacity() )
grow();
super::push_back( value );
}
template<typename T, typename Allocator>
inline
void gvector<T, Allocator>::push_back( T &&value )
{
if( super::size() == super::capacity() )
grow();
super::push_back( std::move( value ) );
}
template<typename T, typename Allocator>
template<typename ... Args>
inline
void gvector<T, Allocator>::emplace_back( Args &&...args )
{
if( super::size() == super::capacity() )
grow();
super::emplace_back( args ... );
}
template<typename T, typename Allocator>
void gvector<T, Allocator>::set_grow( std::size_t growConst, float growExp )
{
assert(growExp >= 0.0);
m_growConst = growConst;
m_growExp = growExp;
}
template<typename T, typename Allocator>
void gvector<T, Allocator>::grow()
{
using namespace std;
size_t size = super::size(),
capacity = super::capacity();
assert(size == capacity);
size_t growConst = size + m_growConst,
growExp = (size_t)(size * m_growExp);
growExp = growExp != size ? growExp : size + 1;
try
{
super::reserve( growConst >= growExp ? growConst : growExp );
}
catch( bad_alloc & )
{
if( growConst >= growExp )
super::reserve( size + 1 );
else
try
{
super::reserve( growConst );
}
catch( bad_alloc & )
{
super::reserve( size + 1 );
}
}
}
#if !defined(NDEBUG)
template
struct gvector<char, std::allocator<char>>;
#endif