A sparse set data structure for efficient mapping of sparse indices to dense storage of values. More...

#include <sparse_set.hpp>

Public Types
using	value_type = T
using	index_type = IndexType
using	dense_index_type = DenseIndexType
using	size_type = size_t
using	reference = T&
using	const_reference = const T&
using	pointer = T*
using	const_pointer = const T*
using	allocator_type = Allocator
using	iterator = typename DenseContainerType::iterator
using	const_iterator = typename DenseContainerType::const_iterator
using	reverse_iterator = typename DenseContainerType::reverse_iterator
using	const_reverse_iterator

Public Member Functions
constexpr	SparseSet () noexcept(std::is_nothrow_default_constructible_v< Allocator >)=default
	Default constructor.
	SparseSet (const Allocator &alloc) noexcept(noexcept(SparseAllocator(alloc)))
	Constructor with custom allocator.
	SparseSet (std::pmr::memory_resource resource) noexcept(std::is_nothrow_constructible_v< Allocator, std::pmr::memory_resource >)
	Constructor with PMR memory resource.
	SparseSet (std::nullptr_t)=delete
constexpr	SparseSet (const SparseSet &other)=default
	Copy constructor.
constexpr	SparseSet (SparseSet &&) noexcept=default
	Move constructor.
constexpr	~SparseSet ()=default
	Destructor.
constexpr SparseSet &	operator= (const SparseSet &other)=default
	Copy assignment operator.
constexpr SparseSet &	operator= (SparseSet &&) noexcept=default
	Move assignment operator.
constexpr void	Clear () noexcept
	Clears the set, removing all elements.
constexpr DenseIndexType	Insert (IndexType index, const T &value)
	Inserts a value at the specified index (copy version).
constexpr DenseIndexType	Insert (IndexType index, T &&value)
	Inserts a value at the specified index (move version).
template<typename... Args>
constexpr DenseIndexType	Emplace (IndexType index, Args &&... args)
	Constructs a value in-place at the specified index.
constexpr void	Remove (IndexType index) noexcept
	Removes an index from the set.
constexpr void	Reserve (size_type n)
	Reserves space for at least n elements in the dense array.
constexpr void	ReserveSparse (IndexType max_index)
	Reserves space for indices up to max_index in the sparse array.
constexpr void	ShrinkToFit ()
	Shrinks the capacity of both arrays to fit their current size.
constexpr T &	Get (IndexType index) noexcept
	Gets the value at the specified index.
constexpr const T &	Get (IndexType index) const noexcept
	Gets the value at the specified index (const version).
constexpr T &	GetByDenseIndex (DenseIndexType dense_index) noexcept
	Gets the value at the specified dense index.
constexpr const T &	GetByDenseIndex (DenseIndexType dense_index) const noexcept
	Gets the value at the specified dense index (const version).
constexpr T *	TryGet (IndexType index) noexcept
	Tries to get the value at the specified index.
constexpr const T *	TryGet (IndexType index) const noexcept
	Tries to get the value at the specified index (const version).
constexpr void	Swap (SparseSet &other) noexcept
	Swaps the contents of this sparse set with another.
bool	operator== (const SparseSet &other) const noexcept
	Checks if two sparse sets are equal.
constexpr bool	Empty () const noexcept
	Checks if the set is empty.
constexpr bool	Contains (IndexType index) const noexcept
	Checks if an index exists in the set.
constexpr allocator_type	GetAllocator () const noexcept
	Returns the allocator associated with the container.
constexpr DenseIndexType	GetDenseIndex (IndexType index) const noexcept
	Gets the dense index for a given index.
constexpr size_type	Size () const noexcept
	Returns the number of values in the set.
constexpr size_type	MaxSize () const noexcept
	Returns the maximum possible size of the set.
constexpr size_type	Capacity () const noexcept
	Returns the capacity of the dense array.
constexpr size_type	SparseCapacity () const noexcept
	Returns the capacity of the sparse array.
constexpr auto	Data () noexcept -> std::span< T >
	Returns a writable span of the packed values.
constexpr auto	Data () const noexcept -> std::span< const T >
	Returns a read-only span of the packed values.
constexpr iterator	begin () noexcept
constexpr const_iterator	begin () const noexcept
constexpr const_iterator	cbegin () const noexcept
constexpr iterator	end () noexcept
constexpr const_iterator	end () const noexcept
constexpr const_iterator	cend () const noexcept
constexpr reverse_iterator	rbegin () noexcept
constexpr const_reverse_iterator	rbegin () const noexcept
constexpr const_reverse_iterator	crbegin () const noexcept
constexpr reverse_iterator	rend () noexcept
constexpr const_reverse_iterator	rend () const noexcept
constexpr const_reverse_iterator	crend () const noexcept
template<typename... Args>
constexpr auto	Emplace (IndexType index, Args &&... args) -> DenseIndexType

Static Public Member Functions
static constexpr bool	IsValidIndex (IndexType index) noexcept
	Checks if an index value is valid for this sparse set.

Static Public Attributes
static constexpr IndexType	kInvalidIndex
static constexpr DenseIndexType	kInvalidDenseIndex

Friends
constexpr void	swap (SparseSet &lhs, SparseSet &rhs) noexcept
	Non-member swap function for SparseSet.

Detailed Description

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>
class helios::container::SparseSet< T, IndexType, Allocator >

A sparse set data structure for efficient mapping of sparse indices to dense storage of values.

SparseSet provides O(1) insertion, deletion, and lookup operations using two arrays:

sparse: maps element indices to dense indices
dense: stores packed values of type T in contiguous memory

The data structure is particularly useful for managing sparse collections where indices may have large gaps but you want cache-friendly iteration over existing values.

Memory complexity: O(max_index + num_elements) Time complexity: O(1) for all operations (amortized for insertions)

Template Parameters

T	Type of values stored in the dense array
IndexType	Type used for element indices (default: size_t)
Allocator	Allocator type for memory management (default: std::allocator<T>)

Definition at line 40 of file sparse_set.hpp.

Member Typedef Documentation

◆ allocator_type

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::allocator_type = Allocator

Definition at line 62 of file sparse_set.hpp.

◆ const_iterator

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::const_iterator = typename DenseContainerType::const_iterator

Definition at line 65 of file sparse_set.hpp.

◆ const_pointer

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::const_pointer = const T*

Definition at line 61 of file sparse_set.hpp.

◆ const_reference

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::const_reference = const T&

Definition at line 59 of file sparse_set.hpp.

◆ const_reverse_iterator

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::const_reverse_iterator

Initial value:

typename DenseContainerType::const_reverse_iterator

Definition at line 67 of file sparse_set.hpp.

◆ dense_index_type

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::dense_index_type = DenseIndexType

Definition at line 56 of file sparse_set.hpp.

◆ index_type

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::index_type = IndexType

Definition at line 55 of file sparse_set.hpp.

◆ iterator

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::iterator = typename DenseContainerType::iterator

Definition at line 64 of file sparse_set.hpp.

◆ pointer

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::pointer = T*

Definition at line 60 of file sparse_set.hpp.

◆ reference

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::reference = T&

Definition at line 58 of file sparse_set.hpp.

◆ reverse_iterator

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::reverse_iterator = typename DenseContainerType::reverse_iterator

Definition at line 66 of file sparse_set.hpp.

◆ size_type

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::size_type = size_t

Definition at line 57 of file sparse_set.hpp.

◆ value_type

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

using helios::container::SparseSet< T, IndexType, Allocator >::value_type = T

Definition at line 54 of file sparse_set.hpp.

Constructor & Destructor Documentation

◆ SparseSet() [1/6]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::SparseSet ( ) const

constexprdefaultnoexcept

Default constructor.

Creates an empty sparse set. Exception safety: No-throw guarantee if T and Allocator are nothrow default constructible.

◆ SparseSet() [2/6]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::SparseSet ( const Allocator & alloc )

inlineexplicitnoexcept

Constructor with custom allocator.

Creates an empty sparse set with the specified allocator. Exception safety: Basic guarantee.

Parameters

alloc The allocator to use for memory management

Exceptions

May	throw if allocator copy constructor throws

Definition at line 91 of file sparse_set.hpp.

◆ SparseSet() [3/6]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::SparseSet ( std::pmr::memory_resource * resource )

inlineexplicitnoexcept

Constructor with PMR memory resource.

Enabled only when Allocator is constructible from std::pmr::memory_resource*.

Parameters

resource Memory resource used to construct allocator

Definition at line 103 of file sparse_set.hpp.

◆ SparseSet() [4/6]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::SparseSet ( std::nullptr_t )

delete

◆ SparseSet() [5/6]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::SparseSet ( const SparseSet< T, IndexType, Allocator > & other )

constexprdefault

Copy constructor.

Creates a copy of another sparse set. Exception safety: Strong guarantee.

Parameters

other The sparse set to copy from

Exceptions

May	throw if T copy constructor or memory allocation fails

◆ SparseSet() [6/6]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::SparseSet ( SparseSet< T, IndexType, Allocator > && )

constexprdefaultnoexcept

Move constructor.

Transfers ownership of resources from other sparse set. Exception safety: No-throw guarantee.

◆ ~SparseSet()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

helios::container::SparseSet< T, IndexType, Allocator >::~SparseSet ( )

constexprdefault

Destructor.

Destroys the sparse set and releases all memory.

Member Function Documentation

◆ begin() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_iterator helios::container::SparseSet< T, IndexType, Allocator >::begin ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 479 of file sparse_set.hpp.

◆ begin() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

iterator helios::container::SparseSet< T, IndexType, Allocator >::begin ( )

inlinenodiscardconstexprnoexcept

Definition at line 478 of file sparse_set.hpp.

◆ Capacity()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

size_type helios::container::SparseSet< T, IndexType, Allocator >::Capacity ( ) const

inlinenodiscardconstexprnoexcept

Returns the capacity of the dense array.

Returns the number of elements that can be stored in the dense array without triggering a reallocation. Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: The capacity of the dense array

Definition at line 439 of file sparse_set.hpp.

◆ cbegin()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_iterator helios::container::SparseSet< T, IndexType, Allocator >::cbegin ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 482 of file sparse_set.hpp.

◆ cend()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_iterator helios::container::SparseSet< T, IndexType, Allocator >::cend ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 490 of file sparse_set.hpp.

◆ Clear()

template<typename T, typename IndexType, typename Allocator>

void helios::container::SparseSet< T, IndexType, Allocator >::Clear ( )

constexprnoexcept

Clears the set, removing all elements.

Removes all values from the set. The sparse array is reset to invalid indices but its capacity is preserved for performance. Time complexity: O(sparse_capacity). Exception safety: No-throw guarantee.

Definition at line 522 of file sparse_set.hpp.

◆ Contains()

template<typename T, typename IndexType, typename Allocator>

bool helios::container::SparseSet< T, IndexType, Allocator >::Contains ( IndexType index ) const

nodiscardconstexprnoexcept

Checks if an index exists in the set.

Performs a comprehensive check to ensure the index is valid and exists in the set. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if index is invalid or negative.

Parameters

index The index to check

Returns: True if the index exists in the set, false otherwise

Definition at line 788 of file sparse_set.hpp.

◆ crbegin()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_reverse_iterator helios::container::SparseSet< T, IndexType, Allocator >::crbegin ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 500 of file sparse_set.hpp.

◆ crend()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_reverse_iterator helios::container::SparseSet< T, IndexType, Allocator >::crend ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 510 of file sparse_set.hpp.

◆ Data() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

auto helios::container::SparseSet< T, IndexType, Allocator >::Data ( ) const -> std::span< const T >

inlinenodiscardconstexprnoexcept

Returns a read-only span of the packed values.

Provides direct access to the densely packed values in the order they were inserted (with removal gaps filled by later insertions). Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: A span containing all values in the set

Definition at line 474 of file sparse_set.hpp.

◆ Data() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

auto helios::container::SparseSet< T, IndexType, Allocator >::Data ( ) -> std::span< T >

inlinenodiscardconstexprnoexcept

Returns a writable span of the packed values.

Provides direct access to the densely packed values in the order they were inserted (with removal gaps filled by later insertions). Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: A span containing all values in the set

Definition at line 462 of file sparse_set.hpp.

◆ Emplace() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

template<typename... Args>

DenseIndexType helios::container::SparseSet< T, IndexType, Allocator >::Emplace	(	IndexType	index,
		Args &&...	args )

constexpr

Constructs a value in-place at the specified index.

Constructs a value directly in the dense array at the given index. If the index already exists, the existing value is replaced. The sparse array will be resized if necessary to accommodate the index. Time complexity: O(1) amortized (O(index) worst case if sparse array needs resizing). Exception safety: Strong guarantee.

Warning: Triggers assertion if index is invalid or negative.

Parameters

index	The index to insert at
args	Arguments to forward to T's constructor

Returns: The dense index where the value was stored

Exceptions

std::bad_alloc If memory allocation fails during sparse array resize or dense array growth

◆ Emplace() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

template<typename... Args>

auto helios::container::SparseSet< T, IndexType, Allocator >::Emplace	(	IndexType	index,
		Args &&...	args ) -> DenseIndexType

constexpr

Definition at line 592 of file sparse_set.hpp.

◆ Empty()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

bool helios::container::SparseSet< T, IndexType, Allocator >::Empty ( ) const

inlinenodiscardconstexprnoexcept

Checks if the set is empty.

Returns true if no values are stored in the set. Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: True if the set contains no elements, false otherwise

Definition at line 361 of file sparse_set.hpp.

◆ end() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_iterator helios::container::SparseSet< T, IndexType, Allocator >::end ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 487 of file sparse_set.hpp.

◆ end() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

iterator helios::container::SparseSet< T, IndexType, Allocator >::end ( )

inlinenodiscardconstexprnoexcept

Definition at line 486 of file sparse_set.hpp.

◆ Get() [1/2]

template<typename T, typename IndexType, typename Allocator>

const T & helios::container::SparseSet< T, IndexType, Allocator >::Get ( IndexType index ) const

nodiscardconstexprnoexcept

Gets the value at the specified index (const version).

Returns a const reference to the value stored at the given index. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if index is invalid, negative, or doesn't exist.

Parameters

index The index to access

Returns: Const reference to the value at the specified index

Definition at line 690 of file sparse_set.hpp.

◆ Get() [2/2]

template<typename T, typename IndexType, typename Allocator>

T & helios::container::SparseSet< T, IndexType, Allocator >::Get ( IndexType index )

nodiscardconstexprnoexcept

Gets the value at the specified index.

Returns a reference to the value stored at the given index. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if index is invalid, negative, or doesn't exist.

Parameters

index The index to access

Returns: Reference to the value at the specified index

Definition at line 680 of file sparse_set.hpp.

◆ GetAllocator()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

allocator_type helios::container::SparseSet< T, IndexType, Allocator >::GetAllocator ( ) const

inlinenodiscardconstexprnoexcept

Returns the allocator associated with the container.

Gets the allocator used for the dense array. Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: Copy of the allocator

Definition at line 394 of file sparse_set.hpp.

◆ GetByDenseIndex() [1/2]

template<typename T, typename IndexType, typename Allocator>

const T & helios::container::SparseSet< T, IndexType, Allocator >::GetByDenseIndex ( DenseIndexType dense_index ) const

nodiscardconstexprnoexcept

Gets the value at the specified dense index (const version).

Returns a const reference to the value stored at the given dense position. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if dense_index is invalid, negative, or out of bounds.

Parameters

dense_index The dense position to access

Returns: Const reference to the value at the specified dense position

Definition at line 715 of file sparse_set.hpp.

◆ GetByDenseIndex() [2/2]

template<typename T, typename IndexType, typename Allocator>

T & helios::container::SparseSet< T, IndexType, Allocator >::GetByDenseIndex ( DenseIndexType dense_index )

nodiscardconstexprnoexcept

Gets the value at the specified dense index.

Returns a reference to the value stored at the given dense position. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if dense_index is invalid, negative, or out of bounds.

Parameters

dense_index The dense position to access

Returns: Reference to the value at the specified dense position

Definition at line 701 of file sparse_set.hpp.

◆ GetDenseIndex()

template<typename T, typename IndexType, typename Allocator>

auto helios::container::SparseSet< T, IndexType, Allocator >::GetDenseIndex ( IndexType index ) const

nodiscardconstexprnoexcept

Gets the dense index for a given index.

Returns the position of the value in the dense array for the specified index. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if index is invalid, negative, or doesn't exist.

Parameters

index The index to look up

Returns: The dense index

Definition at line 805 of file sparse_set.hpp.

◆ Insert() [1/2]

template<typename T, typename IndexType, typename Allocator>

auto helios::container::SparseSet< T, IndexType, Allocator >::Insert	(	IndexType	index,
		const T &	value )

constexpr

Inserts a value at the specified index (copy version).

Adds the specified value to the set at the given index if it's not already present. If the index already exists, the existing value is replaced. The sparse array will be resized if necessary to accommodate the index. Time complexity: O(1) amortized (O(index) worst case if sparse array needs resizing). Exception safety: Strong guarantee.

Warning: Triggers assertion if index is invalid or negative

Parameters

index	The index to insert at
value	The value to move insert

Returns: The dense index where the value was stored

Exceptions

std::bad_alloc If memory allocation fails during sparse array resize or dense array growth

Definition at line 529 of file sparse_set.hpp.

◆ Insert() [2/2]

template<typename T, typename IndexType, typename Allocator>

auto helios::container::SparseSet< T, IndexType, Allocator >::Insert	(	IndexType	index,
		T &&	value )

constexpr

Inserts a value at the specified index (move version).

Adds the specified value to the set at the given index if it's not already present. If the index already exists, the existing value is replaced. The sparse array will be resized if necessary to accommodate the index. Time complexity: O(1) amortized (O(index) worst case if sparse array needs resizing). Exception safety: Strong guarantee.

Warning: Triggers assertion if index is invalid or negative

Parameters

index	The index to insert at
value	The value to copy insert

Returns: The dense index where the value was stored

Exceptions

std::bad_alloc If memory allocation fails during sparse array resize or dense array growth

Definition at line 560 of file sparse_set.hpp.

◆ IsValidIndex()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

constexpr bool helios::container::SparseSet< T, IndexType, Allocator >::IsValidIndex ( IndexType index )

inlinestaticnodiscardconstexprnoexcept

Checks if an index value is valid for this sparse set.

Returns true if the index is not the reserved invalid value. Time complexity: O(1). Exception safety: No-throw guarantee.

Parameters

index The index to validate

Returns: True if the index is valid, false if it's the reserved invalid value

Definition at line 372 of file sparse_set.hpp.

◆ MaxSize()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

size_type helios::container::SparseSet< T, IndexType, Allocator >::MaxSize ( ) const

inlinenodiscardconstexprnoexcept

Returns the maximum possible size of the set.

Returns the theoretical maximum number of elements the set can hold. Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: The maximum possible size

Definition at line 428 of file sparse_set.hpp.

◆ operator=() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

SparseSet & helios::container::SparseSet< T, IndexType, Allocator >::operator= ( const SparseSet< T, IndexType, Allocator > & other )

constexprdefault

Copy assignment operator.

Assigns the contents of another sparse set to this one. Exception safety: Strong guarantee.

Parameters

other The sparse set to copy from

Returns: Reference to this sparse set

Exceptions

May	throw if T copy assignment or memory allocation fails

◆ operator=() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

SparseSet & helios::container::SparseSet< T, IndexType, Allocator >::operator= ( SparseSet< T, IndexType, Allocator > && )

constexprdefaultnoexcept

Move assignment operator.

Transfers ownership of resources from other sparse set. Exception safety: No-throw guarantee.

Returns: Reference to this sparse set

◆ operator==()

template<typename T, typename IndexType, typename Allocator>
requires std::equality_comparable<T>

bool helios::container::SparseSet< T, IndexType, Allocator >::operator== ( const SparseSet< T, IndexType, Allocator > & other ) const

inlinenodiscardnoexcept

Checks if two sparse sets are equal.

Two sparse sets are equal if they contain the same index-value pairs. Time complexity: O(Size() + other.Size()). Exception safety: No-throw guarantee.

Parameters

other The sparse set to compare with

Returns: True if both sets contain the same index-value pairs

Definition at line 769 of file sparse_set.hpp.

◆ rbegin() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_reverse_iterator helios::container::SparseSet< T, IndexType, Allocator >::rbegin ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 497 of file sparse_set.hpp.

◆ rbegin() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

reverse_iterator helios::container::SparseSet< T, IndexType, Allocator >::rbegin ( )

inlinenodiscardconstexprnoexcept

Definition at line 494 of file sparse_set.hpp.

◆ Remove()

template<typename T, typename IndexType, typename Allocator>

void helios::container::SparseSet< T, IndexType, Allocator >::Remove ( IndexType index )

constexprnoexcept

Removes an index from the set.

Removes the specified index from the set using swap-and-pop technique to maintain dense packing. The last element in the dense array is moved to fill the gap left by the removed element. Time complexity: O(1). Exception safety: No-throw guarantee.

Warning: Triggers assertion if index is invalid, negative, or doesn't exist.

Parameters

index The index to remove

Definition at line 623 of file sparse_set.hpp.

◆ rend() [1/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

const_reverse_iterator helios::container::SparseSet< T, IndexType, Allocator >::rend ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 507 of file sparse_set.hpp.

◆ rend() [2/2]

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

reverse_iterator helios::container::SparseSet< T, IndexType, Allocator >::rend ( )

inlinenodiscardconstexprnoexcept

Definition at line 504 of file sparse_set.hpp.

◆ Reserve()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

void helios::container::SparseSet< T, IndexType, Allocator >::Reserve ( size_type n )

inlineconstexpr

Reserves space for at least n elements in the dense array.

Ensures that the dense array can hold at least n elements without triggering a reallocation. Does not affect the sparse array capacity. Time complexity: O(1) if no reallocation, O(Size()) if reallocation occurs. Exception safety: Strong guarantee.

Warning: Triggers assertion if n is negative.

Parameters

n	The minimum capacity to reserve

Exceptions

std::bad_alloc If memory allocation fails

Definition at line 229 of file sparse_set.hpp.

◆ ReserveSparse()

template<typename T, typename IndexType, typename Allocator>

void helios::container::SparseSet< T, IndexType, Allocator >::ReserveSparse ( IndexType max_index )

constexpr

Reserves space for indices up to max_index in the sparse array.

Ensures that the sparse array can accommodate indices up to max_index without triggering a reallocation. Time complexity: O(1) if no reallocation, O(max_index) if reallocation occurs. Exception safety: Strong guarantee.

Warning: Triggers assertion if max_index is invalid or negative.

Parameters

max_index The maximum index to accommodate

Exceptions

std::bad_alloc If memory allocation fails

Definition at line 651 of file sparse_set.hpp.

◆ ShrinkToFit()

template<typename T, typename IndexType, typename Allocator>

void helios::container::SparseSet< T, IndexType, Allocator >::ShrinkToFit ( )

constexpr

Shrinks the capacity of both arrays to fit their current size.

Reduces memory usage by shrinking both the dense and sparse arrays to their minimum required size. Time complexity: O(Size() + SparseSize()). Exception safety: Strong guarantee.

Exceptions

std::bad_alloc If memory allocation fails during shrinking

Definition at line 665 of file sparse_set.hpp.

◆ Size()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

size_type helios::container::SparseSet< T, IndexType, Allocator >::Size ( ) const

inlinenodiscardconstexprnoexcept

Returns the number of values in the set.

Returns the count of values currently stored in the set. Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: The number of values in the set

Definition at line 418 of file sparse_set.hpp.

◆ SparseCapacity()

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

size_type helios::container::SparseSet< T, IndexType, Allocator >::SparseCapacity ( ) const

inlinenodiscardconstexprnoexcept

Returns the capacity of the sparse array.

Returns the maximum index that can be stored without triggering a sparse array reallocation. Time complexity: O(1). Exception safety: No-throw guarantee.

Returns: The capacity of the sparse array

Definition at line 450 of file sparse_set.hpp.

◆ Swap()

template<typename T, typename IndexType, typename Allocator>

void helios::container::SparseSet< T, IndexType, Allocator >::Swap ( SparseSet< T, IndexType, Allocator > & other )

constexprnoexcept

Swaps the contents of this sparse set with another.

Efficiently swaps all data between two sparse sets. Time complexity: O(1). Exception safety: No-throw guarantee.

Parameters

other The sparse set to swap with

Definition at line 761 of file sparse_set.hpp.

◆ TryGet() [1/2]

template<typename T, typename IndexType, typename Allocator>

const T * helios::container::SparseSet< T, IndexType, Allocator >::TryGet ( IndexType index ) const

nodiscardconstexprnoexcept

Tries to get the value at the specified index (const version).

Returns a pointer to the value stored at the given index, or nullptr if the index doesn't exist. Time complexity: O(1). Exception safety: No-throw guarantee.

Parameters

index The index to access

Returns: Pointer to the value at the specified index, or nullptr if index doesn't exist

Definition at line 745 of file sparse_set.hpp.

◆ TryGet() [2/2]

template<typename T, typename IndexType, typename Allocator>

T * helios::container::SparseSet< T, IndexType, Allocator >::TryGet ( IndexType index )

nodiscardconstexprnoexcept

Tries to get the value at the specified index.

Returns a pointer to the value stored at the given index, or nullptr if the index doesn't exist. Time complexity: O(1). Exception safety: No-throw guarantee.

Parameters

index The index to access

Returns: Pointer to the value at the specified index, or nullptr if index doesn't exist

Definition at line 729 of file sparse_set.hpp.

◆ swap

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

void swap	(	SparseSet< T, IndexType, Allocator > &	lhs,
		SparseSet< T, IndexType, Allocator > &	rhs )

friend

Non-member swap function for SparseSet.

Provides a non-member swap function to enable ADL and compatibility with standard algorithms. Time complexity: O(1). Exception safety: No-throw guarantee.

Parameters

lhs	First sparse set
rhs	Second sparse set

Definition at line 339 of file sparse_set.hpp.

Member Data Documentation

◆ kInvalidDenseIndex

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

DenseIndexType helios::container::SparseSet< T, IndexType, Allocator >::kInvalidDenseIndex

staticconstexpr

Initial value:

=

std::numeric_limits<DenseIndexType>::max()

Definition at line 72 of file sparse_set.hpp.

◆ kInvalidIndex

template<typename T, typename IndexType = size_t, typename Allocator = std::allocator<T>>

IndexType helios::container::SparseSet< T, IndexType, Allocator >::kInvalidIndex

staticconstexpr

Initial value:

=

std::numeric_limits<IndexType>::max()

Definition at line 70 of file sparse_set.hpp.

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ dense_index_type

◆ index_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ SparseSet() [1/6]

◆ SparseSet() [2/6]

◆ SparseSet() [3/6]

◆ SparseSet() [4/6]

◆ SparseSet() [5/6]

◆ SparseSet() [6/6]

◆ ~SparseSet()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ Capacity()

◆ cbegin()

◆ cend()

◆ Clear()

◆ Contains()

◆ crbegin()

◆ crend()

◆ Data() [1/2]

◆ Data() [2/2]

◆ Emplace() [1/2]

◆ Emplace() [2/2]

◆ Empty()

◆ end() [1/2]

◆ end() [2/2]

◆ Get() [1/2]

◆ Get() [2/2]

◆ GetAllocator()

◆ GetByDenseIndex() [1/2]

◆ GetByDenseIndex() [2/2]

◆ GetDenseIndex()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ IsValidIndex()

◆ MaxSize()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ Remove()

◆ rend() [1/2]

◆ rend() [2/2]

◆ Reserve()

◆ ReserveSparse()

◆ ShrinkToFit()

◆ Size()

◆ SparseCapacity()

◆ Swap()

◆ TryGet() [1/2]

◆ TryGet() [2/2]

Friends And Related Symbol Documentation

◆ swap

Member Data Documentation

◆ kInvalidDenseIndex

◆ kInvalidIndex