realloc_vector::vector< T > Class Template Reference

C++ vector-like container for trivially moveable types, using realloc() for growing memory, with limits on maximum absolute growth. More...

#include <vector_realloc.h>

Collaboration diagram for realloc_vector::vector< T >:

Public Types
typedef T	value_type
typedef size_t	size_type
typedef ssize_t	difference_type
typedef T &	reference
typedef const T &	const_reference
typedef T *	pointer
typedef const T *	const_pointer
typedef T *	iterator
	Iterators are simple pointers to the data.
typedef const T *	const_iterator
	Iterators are simple pointers to the data.

Public Member Functions
	vector () noexcept
	default constructor, creates empty vector, maximum growth is 128k elements
	vector (size_t count, const T &value=T(), size_t max_grow_=131072)
	constructor to create vector of given size and potentially set maximum growth size
template<class It , typename std::enable_if< at_least_input_iterator< It >::value, int >::type = 0>
	vector (It first, It last, size_t max_grow_=131072)
	contructor from iterators and optionally setting maximum growth size
	vector (const vector &v)
	copy and move constructors
	vector (vector &&v)
vector &	operator= (const vector &v)
vector &	operator= (vector &&v)
void	swap (vector &v)
size_t	size () const
	Current size, i.e. the number of elements stored in this vector.
size_t	capacity () const
	Current capacity, i.e. the number of elements that can be stored without allocating more memory.
size_t	max_size () const
	Maximum size to avoid overflow when calculating memory size.
size_t	max_capacity () const
	Maximum capacity to avoid overflow when calculating memory size.
bool	empty () const
	Returns true if the vector is empty.
size_t	get_max_grow () const
	Get the maximum growth size. Memory is grown by this amount maximally.
void	set_max_grow (size_t max_grow_)
	Set the maximum growth size. Memory is grown by this amount maximally.
T *	data ()
	Access the underlying array.
const T *	data () const
	Access the underlying array.
T &	operator[] (size_t i)
	Access the ith element. It is undefined behavior to if i >= size()
const T &	operator[] (size_t i) const
	Access the ith element. It is undefined behavior to if i >= size()
T &	at (size_t i)
	Access the ith element with bounds checking, throws an exception if i >= size()
const T &	at (size_t i) const
	Access the ith element with bounds checking, throws an exception if i >= size()
T &	front ()
	Access the first element. It is undefined behavior if this function is called on an empty vector.
const T &	front () const
	Access the first element. It is undefined behavior if this function is called on an empty vector.
T &	back ()
	Access the last element. It is undefined behavior if this function is called on an empty vector.
const T &	back () const
	Access the last element. It is undefined behavior if this function is called on an empty vector.
bool	reserve_nothrow (size_t n)
	Reserve memory for at least n elements. Returns true if allocation was successfull, false otherwise.
void	reserve (size_t n)
	Reserve memory for at least n elements. Throws an exception if memory allocation is not successful.
void	shrink_to_fit (size_t new_capacity=0)
	Free up unused memory.
void	push_back (const T &x)
	Insert element at the end of the vector. Can throw an exception if memory allocation fails.
void	push_back (T &&x)
	Insert element at the end of the vector. Can throw an exception if memory allocation fails.
template<class... Args>
T &	emplace_back (Args &&... args)
	Construct an element at the end of the vector. Can throw an exception if memory allocation fails.
bool	push_back_nothrow (const T &x)
	Insert element at the end of the vector. Does not throw exception, return value indicates if insert was successful.
bool	push_back_nothrow (T &&x)
	Insert element at the end of the vector. Does not throw exception, return value indicates if insert was successful.
template<class... Args>
bool	emplace_back_nothrow (Args &&... args)
	Construct an element at the end of the vector. Does not throw exception, return value indicates if insert was successful.
void	clear ()
	Removes all elements; does not free up memory, use shrink_to_fit() for that.
void	pop_back ()
	Removes the last element; does not free up memory, use shrink_to_fit() for that.
bool	resize_nothrow (size_t count)
	Resize vector. If new size is larger than current size, new elements are default constructed. Does not throw exception on memory allocation error, return value indicates if resize was successful.
bool	resize_nothrow (size_t count, const T &x)
	Resize vector. If new size is larger than current size, new elements are inserted as copies of x. Does not throw exception on memory allocation error, return value indicates if resize was successful.
void	resize (size_t count)
	Resize vector. If new size is larger than current size, new elements are default constructed. Can throw an exception on memory allocation error.
void	resize (size_t count, const T &x)
	Resize vector. If new size is larger than current size, new elements are inserted as copies of x. Can throw exception on memory allocation error.
iterator	begin ()
	Iterator to the beginning.
const_iterator	begin () const
	Iterator to the beginning.
const_iterator	cbegin () const
	Iterator to the beginning.
iterator	end ()
	Iterator to the end.
const_iterator	end () const
	Iterator to the end.
const_iterator	cend () const
	Iterator to the end.
iterator	erase (const_iterator pos)
	Erase element at the given position.
iterator	erase (const_iterator first, const_iterator last)
	Erase elements in the given range.
bool	insert_nothrow (const_iterator pos, iterator &res, const T &x)
	Inserts a copy of x at the given position. Does not throw an exception on memory allocation failure, the return value indicates if it was successful. The res iterator is updated to point to the inserted element if successful, otherwise it is not changed.
bool	insert_nothrow (const_iterator pos, iterator &res, T &&x)
	Inserts x at the given position. Does not throw an exception on memory allocation failure, the return value indicates if it was successful. The res iterator is updated to point to the inserted element if successful, otherwise it is not changed.
bool	insert_nothrow (const_iterator pos, iterator &res, size_t count, const T &x)
	Inserts count copies of x at the given position. Does not throw an exception on memory allocation failure, the return value indicates if it was successful. The res iterator is updated to point to the inserted element if successful, otherwise it is not changed.
template<class InputIt , typename std::enable_if< at_least_input_iterator< InputIt >::value, int >::type = 0>
bool	insert_nothrow (const_iterator pos, iterator &res, InputIt first, InputIt last)
	Inserts the elements in the range [first,last) at pos. Does not throw an exception on memory allocation failure, the return value indicates if it was successful. The res iterator is updated to point to the inserted element if successful, otherwise it is not changed.
iterator	insert (const_iterator pos, const T &x)
	Inserts a copy of x at pos. Can throw an exception if out of memory.
iterator	insert (const_iterator pos, T &&x)
	Inserts x at pos. Can throw an exception if out of memory.
iterator	insert (const_iterator pos, size_t count, const T &x)
	Inserts count copies of x at pos. Can throw an exception if out of memory.
template<class InputIt , typename std::enable_if< at_least_input_iterator< InputIt >::value, int >::type = 0>
iterator	insert (const_iterator pos, InputIt first, InputIt last)
	Inserts the elements in the range [first,last) at pos. Can throw an exception if out of memory.
template<class T>
bool	insert_nothrow (vector< T >::const_iterator pos, vector< T >::iterator &res, const T &x)
template<class T>
bool	insert_nothrow (vector< T >::const_iterator pos, vector< T >::iterator &res, T &&x)
template<class T>
bool	insert_nothrow (vector< T >::const_iterator pos, vector< T >::iterator &res, size_t count, const T &x)
template<class InputIt , typename std::enable_if< at_least_input_iterator< InputIt >::value, int >::type >
bool	insert_nothrow (vector< T >::const_iterator pos, vector< T >::iterator &res, InputIt first, InputIt last)
template<class T , template< class > class vt>
	vector (const vector< T, vt > &v)
template<class T , template< class > class vt>
	vector (vector< T, vt > &&v)
template<class T , template< class > class vt>
bool	insert_nothrow (vector< T, vt >::const_iterator pos, vector< T, vt >::iterator &res, const T &x)
template<class T , template< class > class vt>
bool	insert_nothrow (vector< T, vt >::const_iterator pos, vector< T, vt >::iterator &res, T &&x)
template<class T , template< class > class vt>
bool	insert_nothrow (vector< T, vt >::const_iterator pos, vector< T, vt >::iterator &res, size_t count, const T &x)
template<class InputIt , typename std::enable_if< at_least_input_iterator< InputIt >::value, int >::type >
bool	insert_nothrow (vector< T, vt >::const_iterator pos, vector< T, vt >::iterator &res, InputIt first, InputIt last)

Protected Member Functions
bool	change_size (size_t new_size)
	Reallocate memory to the given new size.
bool	grow_vector (size_t minimum_size=0)
	Attempt to grow vector either to the given minimum size or by doubling the current size unless growth would be larger than max_grow, in which case size is increased by max_grow.
bool	insert_helper (size_t pos, size_t new_pos)

Protected Attributes
T *	start
	pointer to elements
size_t	p_size
	number of elements in vector
size_t	p_capacity
	current capacity of vector
size_t	max_grow
	grow memory by maximum this many elements at a time

Static Protected Attributes
static constexpr size_t	p_max_capacity = std::numeric_limits<size_t>::max() / sizeof(T)
	maximum safe capacity to avoid overflow

Detailed Description

template<class T>
class realloc_vector::vector< T >

C++ vector-like container for trivially moveable types, using realloc() for growing memory, with limits on maximum absolute growth.

Main motivation for this class are the following perceived issues with std::vector:

1. An std::vector always grows by a fixed factor (typically 2, i.e. doubling capacity on most implementations). This is required to avoid O(n^2) copies of elements if growing a vector requires copying all elements (see below). Thus, if a vector is full with N elements, memory requirement jumps up to 2*N, which might end up wasting memory space.
2. Since the stored type in std::vector is not necessarily trivially copyable (cannot be moved with memcopy() / memmove()), any change in capacity needs to be performed in three steps: 1. allocate new memory; 2. copy elements; 3. free previous memory. This way, it is not possible to use any optimizations offered by realloc() (e.g. using mremap() on Linux for large allocations). Growing a vector of size N then actually requires allocating memory in total for 3*N elements, and using 2*N elements of it for the duration of the grow.

This class addresses these issues by requiring the stored type to be trivially copyable, thus realloc() can be used for changing the size. Using the assumption that realloc() is optimized for large memory areas to avoid a copy, this will result in the memory requirement being only the requested new size. This also allows the vector to be grown in smaller chunks that can be useful to avoid getting an out of memory error.

Currently, the requirement is for the type to be trivially copyable (as per std::is_trivially_copyable), but it could be relaxed to any type that can be moved by a simple memmove() (and not calling the destructor explicitly), i.e. any type that allocates dynamic memory as well, as long as it does not store a pointer to itself (and no pointers to it are stored elsewhere as well).

---

The documentation for this class was generated from the following files:

• vector_realloc.h
• vector_stacked.h