stacked_vector::vector< T, vector_type > Class Template Reference

C++ vector-like container that internally maintains a "stack" of vectors instead of having one large resizeable storage. More...

#include <vector_stacked.h>

Classes
class	iterator_base
	Iterators store a reference to this class and a position. More...

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 iterator_base< false >	iterator
typedef iterator_base< true >	const_iterator

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_stack_array_size () const
	Get the maximum growth size. Separate arrays are allocated by this amount.
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, keeping at least the given new_capacity (if new_capacity > size()).
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.

Protected Member Functions
template<class U = T>
bool	copy_or_move (U *target, size_t new_size, typename std::enable_if< std::is_nothrow_move_constructible< U >::value >::type *=0)
	Helper function to copy or move values to new array, selecting copy or move based on SFINAE.
template<class U = T>
bool	copy_or_move (U *target, size_t new_size, typename std::enable_if< ! std::is_nothrow_move_constructible< U >::value >::type *=0)
bool	change_size (size_t new_size)
	Reallocate memory in the first stack element to the given new size, moving / copying elements to the new location. new_size must be > 0, but can be less than p_size.
bool	grow_vector (size_t minimum_size=0)
	Attempt to grow vector either to the given minimum size or using the default strategy, i.e. doubling size until the first element in the stack is full and after allocating max_grow elements at a time.
bool	grow_one ()
	Add one element to the stack.
std::pair< size_t, size_t >	get_indices (size_t i) const
	Helper to get internal indices (which stack + position in stack) based on item index.
T *	get_addr (size_t i)
	Helper to get memory address of element at index. Does not check if index is in range, it is undefined behavior to call this function with i >= size().
const T *	get_addr (size_t i) const
	Helper to get memory address of element at index. Does not check if index is in range, it is undefined behavior to call this function with i >= size().
T &	get_ref (size_t i)
	Helper to get reference of element at index. Does not check if index is in range, it is undefined behavior to call this function with i >= size().
const T &	get_ref (size_t i) const
	Helper to get reference of element at index. Does not check if index is in range, it is undefined behavior to call this function with i >= size().
bool	insert_helper (size_t pos, size_t new_pos)
	Helper for the insert functions – moves elements starting from pos to new_pos, allocating memory if necessary. The caller must ensure that new_pos >= pos and p_size > pos.
iterator_base< false >	make_iterator (size_t pos)
	Helper to create an iterator based on a position.
iterator_base< false >	make_iterator (iterator_base< true > pos)
	Helper to make a non-const copy of a const iterator – only possible if this class is not const.
iterator_base< true >	make_iterator (size_t pos) const
	Helper to create an iterator based on a position.

Protected Attributes
vector_type< T * >	stack
size_t	p_size
	number of elements in vector
size_t	p_capacity
	current capacity of vector
size_t	p_stack_size
	size of one array in the stack
size_t	max_grow
	grow memory by maximum this many elements at a time, i.e. maximum value for p_stack_size. Does not change, but not const to allow for swapping / copying / moving vectors with different value.

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, template< class > class vector_type = std_vector_wrapper>
class stacked_vector::vector< T, vector_type >

C++ vector-like container that internally maintains a "stack" of vectors instead of having one large resizeable storage.

Template Parameters

T	Type stored in this vector.
vector_type	Container type to use for storing pointers to the individual arrays

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 storing multiple arrays of fixed size instead of one large allocation. These array are stored in a "stack", thus they can be dynamically added or removed. Growing the vector then results in fixed memory allocations and there is no need to copy / move elements.

The downside is that indexing is more complicated, i.e. it includes an extra division and an extra memory lookup operation, thus it can be significantly slower than using a regular vector.

This can be mitigated by optimizing divide operations with the use of the libdivide library. To do this, download libdivide.h and place it in the same directory and define USE_LIBDIVIDE (e.g. by the by adding -DUSE_LIBDIVIDE command line argument if compiling with g++).

---

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

• vector_stacked.h