Template Class StableVector

Class Documentation

template<typename HandleT, typename ElemT>
class StableVector

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.

Public Types

using ElementType = ElemT
using HandleType = HandleT

Public Functions

inline StableVector()

Creates an empty StableVector.

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(size_t countElements, const boost::shared_array<ElementType> &sharedArray)
HandleType push(const ElementType &elem)

Adds the given element to the vector.

Returns:

The handle referring to the inserted element.

HandleType push(ElementType &&elem)

Adds the given element by moving from it.

Returns:

The handle referring to the inserted element.

void 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!

void 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!

HandleType nextHandle() const

The handle which would be returned by calling push now.

void 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.

void clear()

Removes all elements from the vector.

boost::optional<ElementType&> 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.

boost::optional<const ElementType&> 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.

void 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!

void 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!

ElementType &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.

const ElementType &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.

size_t size() const

Absolute size of the vector (including deleted elements).

size_t numUsed() const

Number of non-deleted elements.

StableVectorIterator<HandleType, ElementType> 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.

StableVectorIterator<HandleType, ElementType> end() const

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

void 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