Container that stores objects "almost contiguously" and guarantees that pointers/iterators are not invalidated when the container grows, either through push_back/emplace_back of elements or resevation of capacity. More...

#include <SegmentedVector.h>

Collaboration diagram for UA_CoMP::Container::SegmentedVector< T, N >:

Public Types
using	value_type = T

using	size_type = std::size_t

using	self_type = SegmentedVector< T, N >

using	iterator = SVIterator< T, N, T *, T &, false >

using	const_iterator = SVIterator< T, N >

Public Member Functions
	SegmentedVector ()
	Construct empty SegmentedVector. More...

	SegmentedVector (const self_type &other)
	Copy constructor (copies elements & capacity). More...

	SegmentedVector (self_type &&other) noexcept
	Move constructor (moves elements & capacity). More...

SegmentedVector &	operator= (const self_type &other)
	Copy assignment (copies elements & capacity). More...

SegmentedVector &	operator= (self_type &&other) noexcept
	Move assignment (copies elements & capacity). More...

	~SegmentedVector ()
	Destructor. More...

T &	at (std::size_t pos)
	Access specified element with bounds checking. More...

const T &	at (std::size_t pos) const
	Access specified element with bounds checking. More...

T &	back ()
	Access the last element. More...

const T &	back () const
	Access the last element. More...

T &	operator[] (size_t pos)
	Access specified element (no bounds checking). More...

const T &	operator[] (size_t pos) const
	Access specified element (no bounds checking). More...

iterator	begin ()
	Returns an iterator to the beginning of the container. More...

const_iterator	begin () const
	Returns a const_iterator to the beginning of the container. More...

const_iterator	cbegin () const
	Returns a const_iterator to the beginning of the container. More...

iterator	end ()
	Returns an iterator to the end of the container. More...

const_iterator	end () const
	Returns a const_iterator to the end of the container. More...

const_iterator	cend () const
	Returns a const_iterator to the end. More...

std::size_t	capacity () const
	Returns number of elements that can be stored without allocating additional blocks. More...

bool	empty () const
	Checks whether container is empty. More...

std::size_t	get_block_count () const
	Returns number of currently allocated blocks. More...

std::size_t	get_elements_per_block () const
	Returns number of elements block (template parameter 'N'). More...

std::size_t	size () const
	Returns the number of elements. More...

void	reserve (size_type new_capacity)
	Allocates aditional blocks to achieve requested capacity. More...

void	shrink_to_fit ()
	Deallocates (empty) blocks to schrink capacity to fit current size. More...

void	clear ()
	Clears the content. More...

template<class... Args>
T *	emplace_back (Args &&...args)
	Constructs element in-place at the end. More...

void	pop_back ()
	Removes the last element. More...

T *	push_back (const T &obj)
	Adds element to end. More...

T *	push_back (T &&obj)
	Adds element to end. More...

Private Types
using	Chunk = typename std::aligned_storage< sizeof(T), std::alignment_of< T >::value >::type
	POD type with same alignment requirement as for T's. More...

Private Member Functions
T *	get_chunk ()
	Get next available chunk for element construction with placement new. More...

Private Attributes
std::vector< Chunk * >	m_blocks
	Vector registers pointers to blocks of chunks. More...

size_t	m_size
	Index of first free chunk when indexed contiguously. More...

Friends
class	SVIterator< T, N >

class	SVIterator< T, N, T *, T &, false >

Detailed Description

template<typename T, size_t N = 512>
class UA_CoMP::Container::SegmentedVector< T, N >

Container that stores objects "almost contiguously" and guarantees that pointers/iterators are not invalidated when the container grows, either through push_back/emplace_back of elements or resevation of capacity.

It combines vector properties (high data locality) with queue properties (can increase capacity without pointer/iterator invalidation). Actually, its implementation is much like a queue but with a limited interface e.g. no insertions. The reason for the SegmentedVector is that one cannot control the block size for std:queue (where it is small) and we need that control to make the block size flexible and rather large.

Template parameters: T type of elements stored in the container N block size i.e. number of elements per block

Definition at line 51 of file SegmentedVector.h.

Member Typedef Documentation

template<typename T , size_t N = 512>

using UA_CoMP::Container::SegmentedVector< T, N >::value_type = T

Definition at line 57 of file SegmentedVector.h.

template<typename T , size_t N = 512>

using UA_CoMP::Container::SegmentedVector< T, N >::size_type = std::size_t

Definition at line 58 of file SegmentedVector.h.

template<typename T , size_t N = 512>

using UA_CoMP::Container::SegmentedVector< T, N >::self_type = SegmentedVector<T, N>

Definition at line 59 of file SegmentedVector.h.

template<typename T , size_t N = 512>

using UA_CoMP::Container::SegmentedVector< T, N >::iterator = SVIterator<T, N, T*, T&, false>

Definition at line 60 of file SegmentedVector.h.

template<typename T , size_t N = 512>

using UA_CoMP::Container::SegmentedVector< T, N >::const_iterator = SVIterator<T, N>

Definition at line 61 of file SegmentedVector.h.

template<typename T , size_t N = 512>

using UA_CoMP::Container::SegmentedVector< T, N >::Chunk = typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type

private

POD type with same alignment requirement as for T's.

Definition at line 285 of file SegmentedVector.h.

Constructor & Destructor Documentation

template<typename T , size_t N = 512>

UA_CoMP::Container::SegmentedVector< T, N >::SegmentedVector ( )

inlineexplicit

Construct empty SegmentedVector.

Definition at line 68 of file SegmentedVector.h.

template<typename T , size_t N = 512>

UA_CoMP::Container::SegmentedVector< T, N >::SegmentedVector ( const self_type & other )

inline

Copy constructor (copies elements & capacity).

If excess capacity not needed, do shrink_to_fit.

Definition at line 72 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::capacity(), UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, UA_CoMP::Container::SegmentedVector< T, N >::m_size, UA_CoMP::Container::SegmentedVector< T, N >::push_back(), and UA_CoMP::Container::SegmentedVector< T, N >::reserve().

Here is the call graph for this function:

template<typename T , size_t N = 512>

UA_CoMP::Container::SegmentedVector< T, N >::SegmentedVector ( self_type && other )

inlinenoexcept

Move constructor (moves elements & capacity).

If excess capacity not needed, do shrink_to_fit.

Definition at line 85 of file SegmentedVector.h.

template<typename T , size_t N = 512>

UA_CoMP::Container::SegmentedVector< T, N >::~SegmentedVector ( )

inline

Destructor.

Definition at line 120 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::clear().

Here is the call graph for this function:

Member Function Documentation

template<typename T , size_t N = 512>

SegmentedVector& UA_CoMP::Container::SegmentedVector< T, N >::operator= ( const self_type & other )

inline

Copy assignment (copies elements & capacity).

If excess capacity not needed, do shrink_to_fit.

Definition at line 92 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::capacity(), UA_CoMP::Container::SegmentedVector< T, N >::clear(), UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, UA_CoMP::Container::SegmentedVector< T, N >::m_size, UA_CoMP::Container::SegmentedVector< T, N >::push_back(), and UA_CoMP::Container::SegmentedVector< T, N >::reserve().

Here is the call graph for this function:

template<typename T , size_t N = 512>

SegmentedVector& UA_CoMP::Container::SegmentedVector< T, N >::operator= ( self_type && other )

inlinenoexcept

Move assignment (copies elements & capacity).

If excess capacity not needed, do shrink_to_fit.

Definition at line 109 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::clear(), UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Here is the call graph for this function:

template<typename T , size_t N = 512>

T& UA_CoMP::Container::SegmentedVector< T, N >::at ( std::size_t pos )

inline

Access specified element with bounds checking.

Definition at line 127 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::pop_back().

Here is the caller graph for this function:

template<typename T , size_t N = 512>

const T& UA_CoMP::Container::SegmentedVector< T, N >::at ( std::size_t pos ) const

inline

Access specified element with bounds checking.

Definition at line 138 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

template<typename T , size_t N = 512>

T& UA_CoMP::Container::SegmentedVector< T, N >::back ( )

inline

Access the last element.

Definition at line 149 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

template<typename T , size_t N = 512>

const T& UA_CoMP::Container::SegmentedVector< T, N >::back ( ) const

inline

Access the last element.

Definition at line 152 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

template<typename T , size_t N = 512>

T& UA_CoMP::Container::SegmentedVector< T, N >::operator[] ( size_t pos )

inline

Access specified element (no bounds checking).

Definition at line 158 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks.

template<typename T , size_t N = 512>

const T& UA_CoMP::Container::SegmentedVector< T, N >::operator[] ( size_t pos ) const

inline

Access specified element (no bounds checking).

Definition at line 161 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks.

template<typename T , size_t N = 512>

iterator UA_CoMP::Container::SegmentedVector< T, N >::begin ( )

inline

Returns an iterator to the beginning of the container.

Definition at line 171 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::end(), and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Here is the call graph for this function:

template<typename T , size_t N = 512>

const_iterator UA_CoMP::Container::SegmentedVector< T, N >::begin ( ) const

inline

Returns a const_iterator to the beginning of the container.

Definition at line 174 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::end(), and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Here is the call graph for this function:

template<typename T , size_t N = 512>

const_iterator UA_CoMP::Container::SegmentedVector< T, N >::cbegin ( ) const

inline

Returns a const_iterator to the beginning of the container.

Definition at line 177 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::end(), and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Here is the call graph for this function:

template<typename T , size_t N = 512>

iterator UA_CoMP::Container::SegmentedVector< T, N >::end ( )

inline

Returns an iterator to the end of the container.

Definition at line 180 of file SegmentedVector.h.

References UA_CoMP::Container::SVIterator< T, N, P, R, is_const_iterator >::m_end.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::begin(), and UA_CoMP::Container::SegmentedVector< T, N >::cbegin().

Here is the caller graph for this function:

template<typename T , size_t N = 512>

const_iterator UA_CoMP::Container::SegmentedVector< T, N >::end ( ) const

inline

Returns a const_iterator to the end of the container.

Definition at line 183 of file SegmentedVector.h.

References UA_CoMP::Container::SVIterator< T, N, P, R, is_const_iterator >::m_end.

template<typename T , size_t N = 512>

const_iterator UA_CoMP::Container::SegmentedVector< T, N >::cend ( ) const

inline

Returns a const_iterator to the end.

Definition at line 186 of file SegmentedVector.h.

References UA_CoMP::Container::SVIterator< T, N, P, R, is_const_iterator >::m_end.

template<typename T , size_t N = 512>

std::size_t UA_CoMP::Container::SegmentedVector< T, N >::capacity ( ) const

inline

Returns number of elements that can be stored without allocating additional blocks.

Definition at line 193 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::operator=(), UA_CoMP::Container::SegmentedVector< T, N >::reserve(), and UA_CoMP::Container::SegmentedVector< T, N >::SegmentedVector().

Here is the caller graph for this function:

template<typename T , size_t N = 512>

bool UA_CoMP::Container::SegmentedVector< T, N >::empty ( ) const

inline

Checks whether container is empty.

Definition at line 196 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_size.

template<typename T , size_t N = 512>

std::size_t UA_CoMP::Container::SegmentedVector< T, N >::get_block_count ( ) const

inline

Returns number of currently allocated blocks.

Definition at line 199 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks.

template<typename T , size_t N = 512>

std::size_t UA_CoMP::Container::SegmentedVector< T, N >::get_elements_per_block ( ) const

inline

Returns number of elements block (template parameter 'N').

Definition at line 202 of file SegmentedVector.h.

template<typename T , size_t N = 512>

std::size_t UA_CoMP::Container::SegmentedVector< T, N >::size ( ) const

inline

Returns the number of elements.

Definition at line 205 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::shrink_to_fit().

Here is the caller graph for this function:

template<typename T , size_t N = 512>

void UA_CoMP::Container::SegmentedVector< T, N >::reserve ( size_type new_capacity )

inline

Allocates aditional blocks to achieve requested capacity.

Definition at line 212 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::capacity(), and UA_CoMP::Container::SegmentedVector< T, N >::m_blocks.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::operator=(), and UA_CoMP::Container::SegmentedVector< T, N >::SegmentedVector().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T , size_t N = 512>

void UA_CoMP::Container::SegmentedVector< T, N >::shrink_to_fit ( )

inline

Deallocates (empty) blocks to schrink capacity to fit current size.

Definition at line 220 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::size().

Here is the call graph for this function:

template<typename T , size_t N = 512>

void UA_CoMP::Container::SegmentedVector< T, N >::clear ( )

inline

Clears the content.

Definition at line 229 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::operator=(), and UA_CoMP::Container::SegmentedVector< T, N >::~SegmentedVector().

Here is the caller graph for this function:

template<typename T , size_t N = 512>

template<class... Args>

T* UA_CoMP::Container::SegmentedVector< T, N >::emplace_back ( Args &&... args )

inline

Constructs element in-place at the end.

Definition at line 243 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::get_chunk().

Here is the call graph for this function:

template<typename T , size_t N = 512>

void UA_CoMP::Container::SegmentedVector< T, N >::pop_back ( )

inline

Removes the last element.

Definition at line 250 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::at(), UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Here is the call graph for this function:

template<typename T , size_t N = 512>

T* UA_CoMP::Container::SegmentedVector< T, N >::push_back ( const T & obj )

inline

Adds element to end.

Definition at line 270 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::get_chunk().

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::operator=(), and UA_CoMP::Container::SegmentedVector< T, N >::SegmentedVector().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T , size_t N = 512>

T* UA_CoMP::Container::SegmentedVector< T, N >::push_back ( T && obj )

inline

Adds element to end.

Definition at line 277 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::get_chunk().

Here is the call graph for this function:

template<typename T , size_t N = 512>

T* UA_CoMP::Container::SegmentedVector< T, N >::get_chunk ( )

inlineprivate

Get next available chunk for element construction with placement new.

Definition at line 293 of file SegmentedVector.h.

References UA_CoMP::Container::SegmentedVector< T, N >::m_blocks, and UA_CoMP::Container::SegmentedVector< T, N >::m_size.

Referenced by UA_CoMP::Container::SegmentedVector< T, N >::emplace_back(), and UA_CoMP::Container::SegmentedVector< T, N >::push_back().

Here is the caller graph for this function:

Friends And Related Function Documentation

template<typename T , size_t N = 512>

friend class SVIterator< T, N >

friend

Definition at line 288 of file SegmentedVector.h.

template<typename T , size_t N = 512>

friend class SVIterator< T, N, T *, T &, false >

friend

Definition at line 289 of file SegmentedVector.h.

Member Data Documentation

template<typename T , size_t N = 512>

std::vector<Chunk*> UA_CoMP::Container::SegmentedVector< T, N >::m_blocks

private

Vector registers pointers to blocks of chunks.

Definition at line 307 of file SegmentedVector.h.

template<typename T , size_t N = 512>

size_t UA_CoMP::Container::SegmentedVector< T, N >::m_size

private

Index of first free chunk when indexed contiguously.

Definition at line 308 of file SegmentedVector.h.

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

SegmentedVector.h

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

template<typename T, size_t N = 512> class UA_CoMP::Container::SegmentedVector< T, N >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<typename T, size_t N = 512>
class UA_CoMP::Container::SegmentedVector< T, N >