A vector which guarantees stable indices and features O(1) deletion. More...

#include <StableVector.hpp>

Public Types
using	ElementType = ElemT

using	HandleType = HandleT

Public Member Functions
StableVectorIterator< HandleType, ElementType >	begin () const
	Returns an iterator to the first element of this vector. More...

void	clear ()
	Removes all elements from the vector. More...

StableVectorIterator< HandleType, ElementType >	end () const
	Returns an iterator to the element after the last element of this vector. More...

void	erase (HandleType handle)
	Mark the element behind the given handle as deleted. More...

boost::optional< ElementType & >	get (HandleType handle)
	Returns the element referred to by `handle`. More...

boost::optional< const ElementType & >	get (HandleType handle) const
	Returns the element referred to by `handle`. More...

void	increaseSize (HandleType upTo)
	Increases the size of the vector to the length of `upTo`. More...

void	increaseSize (HandleType upTo, const ElementType &elem)
	Increases the size of the vector to the length of `upTo` by inserting copies of `elem`. More...

HandleType	nextHandle () const
	The handle which would be returned by calling `push` now. More...

size_t	numUsed () const
	Number of non-deleted elements. More...

ElementType &	operator[] (HandleType handle)
	Returns the element referred to by `handle`. More...

const ElementType &	operator[] (HandleType handle) const
	Returns the element referred to by `handle`. More...

HandleType	push (const ElementType &elem)
	Adds the given element to the vector. More...

HandleType	push (ElementType &&elem)
	Adds the given element by moving from it. More...

void	reserve (size_t newCap)
	Increase the capacity of the vector to a value that's greater or equal to newCap. More...

void	set (HandleType handle, const ElementType &elem)
	Set a value for the existing `handle`. More...

void	set (HandleType handle, ElementType &&elem)
	Set a value for the existing `handle` by moving from `elem`. More...

size_t	size () const
	Absolute size of the vector (including deleted elements). More...

	StableVector ()
	Creates an empty StableVector. More...

	StableVector (size_t countElements, const boost::shared_array< ElementType > &sharedArray)

	StableVector (size_t countElements, const ElementType &defaultValue)
	Creates a StableVector with `countElements` many copies of `defaultValue`. More...

Private Member Functions
void	checkAccess (HandleType handle) const
	Assert that the requested handle is not deleted or throw an exception otherwise. More...

Private Attributes
vector< boost::optional< ElementType > >	m_elements
	Vector for stored elements. More...

size_t	m_usedCount
	Count of used elements in elements vector. More...

Detailed Description

template<typename HandleT, typename ElemT>
class lvr2::StableVector< HandleT, ElemT >

A vector which guarantees stable indices and features O(1) deletion.

This is basically a wrapper for the std::vector, which marks an element as deleted but does not actually delete it. This means that indices are never invalidated. When inserting an element, you get its index (its so called "handle") back. This handle can later be used to access the element. This remains true regardless of other insertions and deletions happening in between.

USE WITH CAUTION: This NEVER frees memory of deleted values (except on its own destruction and can get very large if used incorrectly! If deletions in your use-case are far more numerous than insertions, this data structure is probably not fitting your needs. The memory requirement of this class is O(n_p) where n_p is the number of push() calls.

Template Parameters

HandleT	This handle type contains the actual index. It has to be derived from `BaseHandle`!
ElemT	Type of elements in the vector.

Definition at line 104 of file StableVector.hpp.

Member Typedef Documentation

◆ ElementType

template<typename HandleT , typename ElemT >

using lvr2::StableVector< HandleT, ElemT >::ElementType = ElemT

Definition at line 113 of file StableVector.hpp.

◆ HandleType

template<typename HandleT , typename ElemT >

using lvr2::StableVector< HandleT, ElemT >::HandleType = HandleT

Definition at line 114 of file StableVector.hpp.

Constructor & Destructor Documentation

◆ StableVector() [1/3]

template<typename HandleT , typename ElemT >

lvr2::StableVector< HandleT, ElemT >::StableVector ( )

inline

Creates an empty StableVector.

Definition at line 119 of file StableVector.hpp.

◆ StableVector() [2/3]

template<typename HandleT , typename ElemT >

lvr2::StableVector< HandleT, ElemT >::StableVector	(	size_t	countElements,
		const ElementType &	defaultValue
	)

Creates a StableVector with countElements many copies of defaultValue.

The elements are stored contiguously in the vectors, thus the valid indices of these elements are 0 to countElements - 1.

◆ StableVector() [3/3]

template<typename HandleT , typename ElemT >

lvr2::StableVector< HandleT, ElemT >::StableVector	(	size_t	countElements,
		const boost::shared_array< ElementType > &	sharedArray
	)

Member Function Documentation

◆ begin()

template<typename HandleT , typename ElemT >

StableVectorIterator<HandleType, ElementType> lvr2::StableVector< HandleT, ElemT >::begin ( ) const

Returns an iterator to the first element of this vector.

This iterator auto skips deleted elements and returns handles to the valid elements.

◆ checkAccess()

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::checkAccess ( HandleType handle ) const

private

Assert that the requested handle is not deleted or throw an exception otherwise.

◆ clear()

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::clear ( )

Removes all elements from the vector.

◆ end()

template<typename HandleT , typename ElemT >

StableVectorIterator<HandleType, ElementType> lvr2::StableVector< HandleT, ElemT >::end ( ) const

Returns an iterator to the element after the last element of this vector.

◆ erase()

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::erase ( HandleType handle )

Mark the element behind the given handle as deleted.

While the element is deleted, the handle stays valid. This means that trying to obtain the element with this handle later, will always result in none (if get() was used). Additionally, the handle can also be used with the set() method.

◆ get() [1/2]

template<typename HandleT , typename ElemT >

boost::optional<ElementType&> lvr2::StableVector< HandleT, ElemT >::get ( HandleType handle )

Returns the element referred to by handle.

Returns none if the element was deleted or if the handle is out of bounds.

◆ get() [2/2]

template<typename HandleT , typename ElemT >

boost::optional<const ElementType&> lvr2::StableVector< HandleT, ElemT >::get ( HandleType handle ) const

Returns the element referred to by handle.

Returns none if the element was deleted or if the handle is out of bounds.

◆ increaseSize() [1/2]

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::increaseSize ( HandleType upTo )

Increases the size of the vector to the length of upTo.

This means that the next call to push() after calling resize(upTo) will return exactly the upTo handle. All elements that are inserted by this method are marked as deleted and thus aren't initialized. They can be set later with set().

If upTo is already a valid handle, this method will panic!

◆ increaseSize() [2/2]

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::increaseSize	(	HandleType	upTo,
		const ElementType &	elem
	)

Increases the size of the vector to the length of upTo by inserting copies of elem.

This means that the next call to push() after calling resize(upTo) will return exactly the upTo handle.

If upTo is already a valid handle, this method will panic!

◆ nextHandle()

template<typename HandleT , typename ElemT >

HandleType lvr2::StableVector< HandleT, ElemT >::nextHandle ( ) const

The handle which would be returned by calling push now.

◆ numUsed()

template<typename HandleT , typename ElemT >

size_t lvr2::StableVector< HandleT, ElemT >::numUsed ( ) const

Number of non-deleted elements.

◆ operator[]() [1/2]

template<typename HandleT , typename ElemT >

ElementType& lvr2::StableVector< HandleT, ElemT >::operator[] ( HandleType handle )

Returns the element referred to by handle.

If handle is out of bounds or the element was deleted, this method will throw an exception in debug mode and has UB in release mode. Use get() instead to gracefully handle the absence of an element.

◆ operator[]() [2/2]

template<typename HandleT , typename ElemT >

const ElementType& lvr2::StableVector< HandleT, ElemT >::operator[] ( HandleType handle ) const

Returns the element referred to by handle.

If handle is out of bounds or the element was deleted, this method will throw an exception in debug mode and has UB in release mode. Use get() instead to gracefully handle the absence of an element.

◆ push() [1/2]

template<typename HandleT , typename ElemT >

HandleType lvr2::StableVector< HandleT, ElemT >::push ( const ElementType & elem )

Adds the given element to the vector.

Returns: The handle referring to the inserted element.

◆ push() [2/2]

template<typename HandleT , typename ElemT >

HandleType lvr2::StableVector< HandleT, ElemT >::push ( ElementType && elem )

Adds the given element by moving from it.

Returns: The handle referring to the inserted element.

◆ reserve()

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::reserve ( size_t newCap )

Increase the capacity of the vector to a value that's greater or equal to newCap.

If newCap is greater than the current capacity, new storage is allocated, otherwise the method does nothing.

Parameters

newCap new capacity of the vector

◆ set() [1/2]

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::set	(	HandleType	handle,
		const ElementType &	elem
	)

Set a value for the existing handle.

In this method, the handle has to be valid: it has to be obtained by a prior push() call. If you want to insert a new element, use push() instead of this set() method!

◆ set() [2/2]

template<typename HandleT , typename ElemT >

void lvr2::StableVector< HandleT, ElemT >::set	(	HandleType	handle,
		ElementType &&	elem
	)

Set a value for the existing handle by moving from elem.

In this method, the handle has to be valid: it has to be obtained by a prior push() call. If you want to insert a new element, use push() instead of this set() method!

◆ size()

template<typename HandleT , typename ElemT >

size_t lvr2::StableVector< HandleT, ElemT >::size ( ) const

Absolute size of the vector (including deleted elements).

Member Data Documentation

◆ m_elements

template<typename HandleT , typename ElemT >

vector<boost::optional<ElementType> > lvr2::StableVector< HandleT, ElemT >::m_elements

private

Vector for stored elements.

Definition at line 281 of file StableVector.hpp.

◆ m_usedCount

template<typename HandleT , typename ElemT >

size_t lvr2::StableVector< HandleT, ElemT >::m_usedCount

private

Count of used elements in elements vector.

Definition at line 278 of file StableVector.hpp.

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

StableVector.hpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename HandleT, typename ElemT> class lvr2::StableVector< HandleT, ElemT >

Member Typedef Documentation

◆ ElementType

◆ HandleType

Constructor & Destructor Documentation

◆ StableVector() [1/3]

◆ StableVector() [2/3]

◆ StableVector() [3/3]

Member Function Documentation

◆ begin()

◆ checkAccess()

◆ clear()

◆ end()

◆ erase()

◆ get() [1/2]

◆ get() [2/2]

◆ increaseSize() [1/2]

◆ increaseSize() [2/2]

◆ nextHandle()

◆ numUsed()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ push() [1/2]

◆ push() [2/2]

◆ reserve()

◆ set() [1/2]

◆ set() [2/2]

◆ size()

Member Data Documentation

◆ m_elements

◆ m_usedCount

template<typename HandleT, typename ElemT>
class lvr2::StableVector< HandleT, ElemT >