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	sparse_container_type = std::vector< DenseIndexType, SparseAllocator >

using	dense_container_type = std::vector< T, DenseAllocator >

using	iterator = typename dense_container_type::iterator

using	const_iterator = typename dense_container_type::const_iterator

using	reverse_iterator = typename dense_container_type::reverse_iterator

using	const_reverse_iterator = typename dense_container_type::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.

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.

DenseIndexType	Insert (IndexType index, const T &value)
	Inserts a value at the specified index (copy version).

DenseIndexType	Insert (IndexType index, T &&value)
	Inserts a value at the specified index (move version).

template<typename... Args>
DenseIndexType	Emplace (IndexType index, Args &&... args)
	Constructs a value in-place at the specified index.

void	Remove (IndexType index) noexcept
	Removes an index from the set.

void	Reserve (size_type n)
	Reserves space for at least n elements in the dense array.

void	ReserveSparse (IndexType max_index)
	Reserves space for indices up to max_index in the sparse array.

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

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 std::span< T >	Data () noexcept
	Returns a writable span of the packed values.

constexpr std::span< const T >	Data () const noexcept
	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

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 = std::numeric_limits<IndexType>::max()

static constexpr DenseIndexType	kInvalidDenseIndex = std::numeric_limits<DenseIndexType>::max()

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 37 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 52 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 dense_container_type::const_iterator

Definition at line 58 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 51 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 49 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 = typename dense_container_type::const_reverse_iterator

Definition at line 60 of file sparse_set.hpp.

◆ dense_container_type

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

using helios::container::SparseSet< T, IndexType, Allocator >::dense_container_type = std::vector<T, DenseAllocator>

Definition at line 55 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 46 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 45 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 dense_container_type::iterator

Definition at line 57 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 50 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 48 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 dense_container_type::reverse_iterator

Definition at line 59 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 47 of file sparse_set.hpp.

◆ sparse_container_type

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

using helios::container::SparseSet< T, IndexType, Allocator >::sparse_container_type = std::vector<DenseIndexType, SparseAllocator>

Definition at line 54 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 44 of file sparse_set.hpp.

Constructor & Destructor Documentation

◆ SparseSet() [1/4]

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

constexpr 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/4]

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 79 of file sparse_set.hpp.

80 : sparse_(SparseAllocator(alloc)), dense_(alloc) {}

◆ SparseSet() [3/4]

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

constexpr 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() [4/4]

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

constexpr 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>>

constexpr 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>>

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

inlineconstexprnoexcept

Definition at line 410 of file sparse_set.hpp.

410{ return dense_.begin(); }

◆ begin() [2/2]

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

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

inlineconstexprnoexcept

Definition at line 409 of file sparse_set.hpp.

409{ return dense_.begin(); }

◆ Capacity()

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

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

inlineconstexprnoexcept

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 378 of file sparse_set.hpp.

378{ return dense_.capacity(); }

◆ cbegin()

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

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

inlineconstexprnoexcept

Definition at line 411 of file sparse_set.hpp.

411{ return dense_.cbegin(); }

◆ cend()

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

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

inlineconstexprnoexcept

Definition at line 415 of file sparse_set.hpp.

415{ return dense_.cend(); }

◆ Clear()

template<typename T , typename IndexType , typename Allocator >

constexpr 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 432 of file sparse_set.hpp.

                                                                  {
  dense_.clear();
  reverse_map_.clear();
  std::ranges::fill(sparse_, kInvalidDenseIndex);
}

◆ Contains()

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 665 of file sparse_set.hpp.

                                                                                          {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to check if set contains index: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to check if set contains index: index cannot be negative!");
  }
  return static_cast<size_type>(index) < sparse_.size() && sparse_[index] != kInvalidDenseIndex &&
         static_cast<size_type>(sparse_[index]) < dense_.size() &&
         static_cast<size_type>(sparse_[index]) < reverse_map_.size() && reverse_map_[sparse_[index]] == index;
}

◆ crbegin()

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

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

inlineconstexprnoexcept

Definition at line 419 of file sparse_set.hpp.

419{ return dense_.crbegin(); }

◆ crend()

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

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

inlineconstexprnoexcept

Definition at line 423 of file sparse_set.hpp.

423{ return dense_.crend(); }

◆ Data() [1/2]

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

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

inlineconstexprnoexcept

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 407 of file sparse_set.hpp.

407{ return dense_; }

◆ Data() [2/2]

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

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

inlineconstexprnoexcept

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 397 of file sparse_set.hpp.

397{ return dense_; }

◆ Emplace()

template<typename T , typename IndexType , typename Allocator >

template<typename... Args>

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

inline

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

Definition at line 496 of file sparse_set.hpp.

                                     {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to emplace value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to emplace value: index cannot be negative!");
  }
 
  // Check if index already exists and replace the value
  if (Contains(index)) {
    const DenseIndexType dense_index = sparse_[index];
    dense_[dense_index] = T(std::forward<Args>(args)...);
    return dense_index;
  }
 
  // Ensure sparse array is large enough
  if (static_cast<size_type>(index) >= sparse_.size()) {
    sparse_.resize(static_cast<size_type>(index) + 1, kInvalidDenseIndex);
  }
 
  const auto dense_index = static_cast<DenseIndexType>(dense_.size());
  sparse_[index] = dense_index;
  dense_.emplace_back(std::forward<Args>(args)...);
  reverse_map_.push_back(index);
 
  return dense_index;
}

◆ Empty()

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

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

inlineconstexprnoexcept

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 310 of file sparse_set.hpp.

310{ return dense_.empty(); }

◆ end() [1/2]

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

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

inlineconstexprnoexcept

Definition at line 414 of file sparse_set.hpp.

414{ return dense_.end(); }

◆ end() [2/2]

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

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

inlineconstexprnoexcept

Definition at line 413 of file sparse_set.hpp.

413{ return dense_.end(); }

◆ Get() [1/2]

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 584 of file sparse_set.hpp.

                                                                                         {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to get value: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index), "Failed to get value: index does not exist!");
  return dense_[sparse_[index]];
}

◆ Get() [2/2]

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 574 of file sparse_set.hpp.

                                                                             {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to get value: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index), "Failed to get value: index does not exist!");
  return dense_[sparse_[index]];
}

◆ GetAllocator()

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

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

inlineconstexprnoexcept

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 340 of file sparse_set.hpp.

340{ return dense_.get_allocator(); }

◆ GetByDenseIndex() [1/2]

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 604 of file sparse_set.hpp.

                                                                                                                {
  HELIOS_ASSERT(dense_index != kInvalidDenseIndex, "Failed to get value: dense_index is invalid!");
  if constexpr (std::is_signed_v<DenseIndexType>) {
    HELIOS_ASSERT(dense_index >= 0, "Failed to get value: dense_index cannot be negative!");
  }
  HELIOS_ASSERT(dense_index < dense_.size(), "Failed to get value: dense_index is out of bounds!");
  return dense_[dense_index];
}

◆ GetByDenseIndex() [2/2]

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 594 of file sparse_set.hpp.

                                                                                                    {
  HELIOS_ASSERT(dense_index != kInvalidDenseIndex, "Failed to get value: dense_index is invalid!");
  if constexpr (std::is_signed_v<DenseIndexType>) {
    HELIOS_ASSERT(dense_index >= 0, "Failed to get value: dense_index cannot be negative!");
  }
  HELIOS_ASSERT(dense_index < dense_.size(), "Failed to get value: dense_index is out of bounds!");
  return dense_[dense_index];
}

◆ GetDenseIndex()

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 676 of file sparse_set.hpp.

                                    {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to get dense index: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to get dense index: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index), "Failed to get dense index: index does not exist!");
  return sparse_[index];
}

◆ Insert() [1/2]

template<typename T , typename IndexType , typename Allocator >

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

inline

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 439 of file sparse_set.hpp.

                                     {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to insert value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to insert value: index cannot be negative!");
  }
 
  // Check if index already exists and replace the value
  if (Contains(index)) {
    const DenseIndexType dense_index = sparse_[index];
    dense_[dense_index] = value;
    return dense_index;
  }
 
  // Ensure sparse array can accommodate this index
  if (index >= sparse_.size()) {
    sparse_.resize(index + 1, kInvalidDenseIndex);
  }
 
  const auto dense_index = static_cast<DenseIndexType>(dense_.size());
  dense_.push_back(value);
  reverse_map_.push_back(index);
  sparse_[index] = dense_index;
 
  return dense_index;
}

◆ Insert() [2/2]

template<typename T , typename IndexType , typename Allocator >

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

inline

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 467 of file sparse_set.hpp.

                                {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to insert value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to insert value: index cannot be negative!");
  }
 
  // Check if index already exists and replace the value
  if (Contains(index)) {
    const DenseIndexType dense_index = sparse_[index];
    dense_[dense_index] = std::move(value);
    return dense_index;
  }
 
  // Ensure sparse array is large enough
  if (static_cast<size_type>(index) >= sparse_.size()) {
    sparse_.resize(static_cast<size_type>(index) + 1, kInvalidDenseIndex);
  }
 
  const auto dense_index = static_cast<DenseIndexType>(dense_.size());
  sparse_[index] = dense_index;
  dense_.push_back(std::move(value));
  reverse_map_.push_back(index);
 
  return dense_index;
}

◆ IsValidIndex()

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

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

inlinestaticconstexprnoexcept

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 320 of file sparse_set.hpp.

320{ return index != kInvalidIndex; }

helios::container::SparseSet::kInvalidIndex

static constexpr IndexType kInvalidIndex

Definition sparse_set.hpp:62

◆ MaxSize()

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

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

inlineconstexprnoexcept

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 369 of file sparse_set.hpp.

369{ return dense_.max_size(); }

◆ operator=() [1/2]

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

constexpr 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>>

constexpr 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

inlinenoexcept

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 647 of file sparse_set.hpp.

{
  if (Size() != other.Size()) {
    return false;
  }
 
  for (size_type i = 0; i < dense_.size(); ++i) {
    const IndexType index = reverse_map_[i];
    if (!other.Contains(index) || dense_[i] != other.Get(index)) {
      return false;
    }
  }
 
  return true;
}

◆ rbegin() [1/2]

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

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

inlineconstexprnoexcept

Definition at line 418 of file sparse_set.hpp.

418{ return dense_.rbegin(); }

◆ rbegin() [2/2]

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

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

inlineconstexprnoexcept

Definition at line 417 of file sparse_set.hpp.

417{ return dense_.rbegin(); }

◆ Remove()

template<typename T , typename IndexType , typename Allocator >

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

inlinenoexcept

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 524 of file sparse_set.hpp.

                                                                               {
  HELIOS_ASSERT(IsValidIndex(index), "Failed to remove value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to remove value: index cannot be negative!");
  }
  HELIOS_ASSERT(Contains(index), "Failed to remove value: index does not exist!");
 
  const DenseIndexType dense_index = sparse_[index];
  const auto last_dense_index = static_cast<DenseIndexType>(dense_.size() - 1);
 
  if (dense_index != last_dense_index) {
    // Swap with last element to maintain dense packing
    const IndexType last_index = reverse_map_[last_dense_index];
    dense_[dense_index] = std::move(dense_[last_dense_index]);
    reverse_map_[dense_index] = last_index;
    sparse_[last_index] = dense_index;
  }
 
  dense_.pop_back();
  reverse_map_.pop_back();
  sparse_[index] = kInvalidDenseIndex;
}

◆ rend() [1/2]

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

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

inlineconstexprnoexcept

Definition at line 422 of file sparse_set.hpp.

422{ return dense_.rend(); }

◆ rend() [2/2]

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

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

inlineconstexprnoexcept

Definition at line 421 of file sparse_set.hpp.

421{ return dense_.rend(); }

◆ Reserve()

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

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

inline

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 197 of file sparse_set.hpp.

197{ dense_.reserve(n); }

◆ ReserveSparse()

template<typename T , typename IndexType , typename Allocator >

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

inline

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 548 of file sparse_set.hpp.

                                                                                 {
  HELIOS_ASSERT(IsValidIndex(max_index), "Failed to reserve sparse: max_index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(max_index >= 0, "Failed to reserve sparse: max_index cannot be negative!");
  }
  if (static_cast<size_type>(max_index) + 1 > sparse_.size()) {
    sparse_.resize(static_cast<size_type>(max_index) + 1, kInvalidDenseIndex);
  }
}

◆ ShrinkToFit()

template<typename T , typename IndexType , typename Allocator >

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

inline

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 559 of file sparse_set.hpp.

                                                            {
  dense_.shrink_to_fit();
  reverse_map_.shrink_to_fit();
 
  // Find the maximum index in use to determine minimum sparse size needed
  if (reverse_map_.empty()) {
    sparse_.clear();
  } else {
    const IndexType max_index = *std::ranges::max_element(reverse_map_);
    sparse_.resize(static_cast<size_type>(max_index) + 1);
  }
  sparse_.shrink_to_fit();
}

◆ Size()

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

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

inlineconstexprnoexcept

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 360 of file sparse_set.hpp.

360{ return dense_.size(); }

◆ SparseCapacity()

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

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

inlineconstexprnoexcept

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 387 of file sparse_set.hpp.

387{ return sparse_.capacity(); }

◆ Swap()

template<typename T , typename IndexType , typename Allocator >

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

inlinenoexcept

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 640 of file sparse_set.hpp.

                                                                              {
  std::swap(sparse_, other.sparse_);
  std::swap(dense_, other.dense_);
  std::swap(reverse_map_, other.reverse_map_);
}

◆ TryGet() [1/2]

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 627 of file sparse_set.hpp.

                                                                                            {
  HELIOS_ASSERT(index != kInvalidIndex, "Failed to get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to try get value: index cannot be negative!");
  }
 
  if (!Contains(index)) {
    return nullptr;
  }
  return &dense_[sparse_[index]];
}

◆ TryGet() [2/2]

template<typename T , typename IndexType , typename Allocator >

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

constexprnoexcept

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 614 of file sparse_set.hpp.

                                                                                {
  HELIOS_ASSERT(index != kInvalidIndex, "Failed to try get value: index is invalid!");
  if constexpr (std::is_signed_v<IndexType>) {
    HELIOS_ASSERT(index >= 0, "Failed to try get value: index cannot be negative!");
  }
 
  if (!Contains(index)) {
    return nullptr;
  }
  return &dense_[sparse_[index]];
}

Member Data Documentation

◆ kInvalidDenseIndex

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

constexpr DenseIndexType helios::container::SparseSet< T, IndexType, Allocator >::kInvalidDenseIndex = std::numeric_limits<DenseIndexType>::max()

staticconstexpr

Definition at line 63 of file sparse_set.hpp.

◆ kInvalidIndex

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

constexpr IndexType helios::container::SparseSet< T, IndexType, Allocator >::kInvalidIndex = std::numeric_limits<IndexType>::max()

staticconstexpr

Definition at line 62 of file sparse_set.hpp.

	Helios Engine 0.1.0 A modular ECS based data-oriented C++23 game engine

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ dense_container_type

◆ dense_index_type

◆ index_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ sparse_container_type

◆ value_type

Constructor & Destructor Documentation

◆ SparseSet() [1/4]

◆ SparseSet() [2/4]

◆ SparseSet() [3/4]

◆ SparseSet() [4/4]

◆ ~SparseSet()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ Capacity()

◆ cbegin()

◆ cend()

◆ Clear()

◆ Contains()

◆ crbegin()

◆ crend()

◆ Data() [1/2]

◆ Data() [2/2]

◆ Emplace()

◆ 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]

Member Data Documentation

◆ kInvalidDenseIndex

◆ kInvalidIndex