`SparseSet` Class Template

A generic sparse set providing O(1) insertion, lookup, and removal. More...

Declaration

template <typename T> class helios::engine::ecs::SparseSet<T> { ... }

Base class

class	SparseSetBase
	Abstract base class for type-erased sparse set access. More...

Public Constructors Index

template <typename T>
SparseSet ()=default
	Default constructor creating an empty sparse set. More...

template <typename T>
SparseSet (const size_t capacity)
	Constructs a sparse set with pre-allocated capacity. More...

template <typename T>
SparseSet (const SparseSet &)=delete
	Copy operations are deleted to prevent accidental duplication. More...

template <typename T>
SparseSet (SparseSet &&) noexcept=default
	Move constructor. More...

Public Operators Index

template <typename T>
SparseSet &	operator= (const SparseSet &)=delete
	Copy assignment is deleted. More...

template <typename T>
SparseSet &	operator= (SparseSet &&) noexcept=default
	Move assignment operator. More...

Public Member Functions Index

template <typename... Args>
T *	emplace (const EntityId idx, Args &&...args)
	Constructs and inserts an element at the given index. More...

template <typename T>
T *	insert (const EntityId idx, T &&obj)
	Inserts an element at the given index. More...

template <typename T>
bool	remove (const EntityId idx) override
	Removes the element at the given index using swap-and-pop. More...

template <typename T>
T *	get (const EntityId idx)
	Retrieves the element at the given index. More...

template <typename T>
const T *	get (const EntityId idx) const
	Retrieves the element at the given index. More...

template <typename T>
bool	contains (const EntityId idx) const override
	Checks whether an element is registered for the specified EntityId. More...

template <typename T>
void *	raw (const helios::engine::ecs::types::EntityId id) override
	Returns a raw void pointer to the element at the given index. More...

template <typename T>
Iterator	begin ()
	Returns an iterator to the beginning of the dense storage. More...

template <typename T>
Iterator	end ()
	Returns an iterator to the end of the dense storage. More...

template <typename T>
ConstIterator	begin () const
	Returns a const iterator to the beginning of the dense storage. More...

template <typename T>
ConstIterator	end () const
	Returns a const iterator to the end of the dense storage. More...

Private Member Attributes Index

template <typename T>
std::vector< size_t >	sparse_
	Maps EntityId to dense storage index. More...

template <typename T>
std::vector< EntityId >	denseToSparse_
	Reverse mapping from dense index to EntityId. More...

template <typename T>
std::vector< T >	storage_
	Contiguous storage of elements. More...

Description

A generic sparse set providing O(1) insertion, lookup, and removal.

`SparseSet` implements the sparse set data structure pattern, commonly used in Entity Component Systems (ECS) for efficient component storage. It maps `EntityId` indices to densely packed data of type `T`.

## Data Structure

``` ┌─────────────────────────────────────────────────────────────┐ │ SPARSE SET LAYOUT │ ├─────────────────────────────────────────────────────────────┤ │ │ │ SPARSE ARRAY (indexed by EntityId) │ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │ │ 2 │ × │ 0 │ × │ 1 │ × │ × │ (dense idx) │ │ └──┬──┴─────┴──┬──┴─────┴──┬──┴─────┴─────┘ │ │ │ │ │ │ │ │ │ ┌────────┘ │ │ │ ┌───────┘ │ │ │ └───│──────────│────────┐ │ │ ▼ ▼ ▼ │ │ DENSE STORAGE (contiguous) │ │ ┌─────────┬─────────┬─────────┐ │ │ │ T[0] │ T[1] │ T[2] │ │ │ │ (id=2) │ (id=4) │ (id=0) │ │ │ └─────────┴─────────┴─────────┘ │ │ │ │ DENSE-TO-SPARSE (reverse mapping for swap-and-pop) │ │ ┌─────┬─────┬─────┐ │ │ │ 2 │ 4 │ 0 │ (EntityId) │ │ └─────┴─────┴─────┘ │ │ │ │ × = Tombstone (empty slot) │ └─────────────────────────────────────────────────────────────┘ ```

## Complexity

| Operation | Time | Space | |-----------|---------|--------------| | emplace | O(1)* | O(max_id) | | insert | O(1)* | O(max_id) | | get | O(1) | - | | remove | O(1) | - |

*Amortized due to potential sparse array resize.

## Usage

```cpp SparseSet<TransformComponent> transforms;

// In-place construction auto* transform = transforms.emplace(42, glm::vec3{0.0f}, glm::quat{}, glm::vec3{1.0f});

// Or insert a pre-constructed object auto* inserted = transforms.insert(43, TransformComponent{...});

// Mutable access if (auto* t = transforms.get(42)) { t->position = glm::vec3{10.0f, 0.0f, 0.0f}; }

// Const access const auto& constSet = transforms; if (const auto* t = constSet.get(42)) { }

// Remove component transforms.remove(42); ```

Template Parameters

T	The type of elements stored in the set. Must be move-assignable.

See Also: EntityId

See Also: EntityTombstone

Definition at line 156 of file SparseSet.ixx.

Public Constructors

SparseSet()

template <typename T>

helios::engine::ecs::SparseSet< T >::SparseSet ()

default

Default constructor creating an empty sparse set.

Definition at line 183 of file SparseSet.ixx.

Referenced by helios::engine::ecs::SparseSet< T >::operator=, helios::engine::ecs::SparseSet< T >::operator=, helios::engine::ecs::SparseSet< T >::SparseSet and helios::engine::ecs::SparseSet< T >::SparseSet.

SparseSet()

template <typename T>

helios::engine::ecs::SparseSet< T >::SparseSet (const size_t capacity)

inline explicit

Constructs a sparse set with pre-allocated capacity.

Parameters

capacity

The initial capacity to reserve for all internal vectors.

Definition at line 190 of file SparseSet.ixx.

190 explicit SparseSet(const size_t capacity) {

191 sparse_.reserve(capacity);

192 storage_.reserve(capacity);

193 denseToSparse_.reserve(capacity);

194 };

SparseSet()

template <typename T>

helios::engine::ecs::SparseSet< T >::SparseSet (const SparseSet &)

delete

Copy operations are deleted to prevent accidental duplication.

Definition at line 199 of file SparseSet.ixx.

Reference helios::engine::ecs::SparseSet< T >::SparseSet.

SparseSet()

template <typename T>

helios::engine::ecs::SparseSet< T >::SparseSet (SparseSet &&)

noexcept default

Move constructor.

Definition at line 209 of file SparseSet.ixx.

Reference helios::engine::ecs::SparseSet< T >::SparseSet.

Public Operators

operator=()

template <typename T>

SparseSet & helios::engine::ecs::SparseSet< T >::operator= (const SparseSet &)

delete

Copy assignment is deleted.

Definition at line 204 of file SparseSet.ixx.

Reference helios::engine::ecs::SparseSet< T >::SparseSet.

operator=()

template <typename T>

SparseSet & helios::engine::ecs::SparseSet< T >::operator= (SparseSet &&)

noexcept default

Move assignment operator.

Definition at line 214 of file SparseSet.ixx.

Reference helios::engine::ecs::SparseSet< T >::SparseSet.

Public Member Functions

begin()

template <typename T>

Iterator helios::engine::ecs::SparseSet< T >::begin ()

inline nodiscard

Returns an iterator to the beginning of the dense storage.

Returns: Iterator pointing to the first element.

Definition at line 475 of file SparseSet.ixx.

475 [[nodiscard]] Iterator begin() {

476 return Iterator(storage_.begin(), denseToSparse_.begin());

477 }

begin()

template <typename T>

ConstIterator helios::engine::ecs::SparseSet< T >::begin ()

inline nodiscard

Returns a const iterator to the beginning of the dense storage.

Returns: ConstIterator pointing to the first element.

Definition at line 493 of file SparseSet.ixx.

493 [[nodiscard]] ConstIterator begin() const {

494 return ConstIterator(storage_.begin(), denseToSparse_.begin());

495 }

contains()

template <typename T>

bool helios::engine::ecs::SparseSet< T >::contains (const EntityId idx)

inline nodiscard virtual

Checks whether an element is registered for the specified EntityId.

Parameters

idx	The entityId to test.

Returns: True if this sparse set contains the entityId, otherwise false.

Definition at line 363 of file SparseSet.ixx.

363 [[nodiscard]] bool contains(const EntityId idx) const override {

364 return idx < sparse_.size() && sparse_[idx] != Tombstone;

365 }

Reference helios::engine::ecs::Tombstone.

emplace()

template <typename... Args>

T * helios::engine::ecs::SparseSet< T >::emplace (const EntityId idx, Args &&... args)

inline nodiscard

Constructs and inserts an element at the given index.

Forwards arguments to construct `T` in-place.

Template Parameters

Args	Constructor argument types.

Parameters

idx	The EntityId to associate with the element.
args	Arguments forwarded to the `T` constructor.

Returns: Pointer to the inserted element, or `nullptr` if the index is already occupied.

Definition at line 230 of file SparseSet.ixx.

230 [[nodiscard]] T* emplace(const EntityId idx, Args&& ...args) {

231

232 // already in use

233 if (idx < sparse_.size() && sparse_[idx] != Tombstone) {

234 return nullptr;

235 }

236

237 if (idx >= sparse_.size()) {

238 sparse_.resize(idx + 1, Tombstone);

239 }

240

241 const auto denseIndex = storage_.size();

242

243 denseToSparse_.push_back(idx);

244 storage_.emplace_back(std::forward<Args>(args)...);

245

246 sparse_[idx] = denseIndex;

247

248 return &storage_.back();

249 }

References helios::engine::ecs::SparseSet< T >::emplace and helios::engine::ecs::Tombstone.

Referenced by helios::engine::ecs::SparseSet< T >::emplace.

end()

template <typename T>

Iterator helios::engine::ecs::SparseSet< T >::end ()

inline nodiscard

Returns an iterator to the end of the dense storage.

Returns: Iterator pointing past the last element.

Definition at line 484 of file SparseSet.ixx.

484 [[nodiscard]] Iterator end() {

485 return Iterator(storage_.end(), denseToSparse_.end());

486 }

end()

template <typename T>

ConstIterator helios::engine::ecs::SparseSet< T >::end ()

inline nodiscard

Returns a const iterator to the end of the dense storage.

Returns: ConstIterator pointing past the last element.

Definition at line 502 of file SparseSet.ixx.

502 [[nodiscard]] ConstIterator end() const {

503 return ConstIterator(storage_.end(), denseToSparse_.end());

504 }

get()

template <typename T>

T * helios::engine::ecs::SparseSet< T >::get (const EntityId idx)

inline nodiscard

Retrieves the element at the given index.

Parameters

idx	The EntityId to look up.

Returns: Pointer to the element, or `nullptr` if not found.

Definition at line 330 of file SparseSet.ixx.

330 [[nodiscard]] T* get(const EntityId idx) {

331

332 if (idx >= sparse_.size() || sparse_[idx] == Tombstone) {

333 return nullptr;

334 }

335

336 return &storage_[sparse_[idx]];

337 }

Reference helios::engine::ecs::Tombstone.

Referenced by helios::engine::ecs::SparseSet< T >::raw.

get()

template <typename T>

const T * helios::engine::ecs::SparseSet< T >::get (const EntityId idx)

inline nodiscard

Retrieves the element at the given index.

Parameters

idx	The EntityId to look up.

Returns: Const Pointer to the element, or `nullptr` if not found.

Definition at line 346 of file SparseSet.ixx.

346 [[nodiscard]] const T* get(const EntityId idx) const {

347

348 if (idx >= sparse_.size() || sparse_[idx] == Tombstone) {

349 return nullptr;

350 }

351

352 return &storage_[sparse_[idx]];

353 }

Reference helios::engine::ecs::Tombstone.

insert()

template <typename T>

T * helios::engine::ecs::SparseSet< T >::insert (const EntityId idx, T && obj)

inline nodiscard

Inserts an element at the given index.

If the sparse array is too small, it is resized to accommodate the index. Empty slots are filled with `Tombstone`.

Parameters

idx	The EntityId to associate with the element.
obj	The element to insert (moved).

Returns: Pointer to the inserted element, or `nullptr` if the index is already occupied.

Definition at line 262 of file SparseSet.ixx.

262 [[nodiscard]] T* insert(const EntityId idx, T&& obj) {

263

264 // already in use

265 if (idx < sparse_.size() && sparse_[idx] != Tombstone) {

266 return nullptr;

267 }

268

269 if (idx >= sparse_.size()) {

270 sparse_.resize(idx + 1, Tombstone);

271 }

272

273 const auto denseIndex = storage_.size();

274

275 denseToSparse_.push_back(idx);

276 storage_.emplace_back(std::move(obj));

277

278 sparse_[idx] = denseIndex;

279

280 return &storage_.back();

281 }

Reference helios::engine::ecs::Tombstone.

raw()

template <typename T>

void * helios::engine::ecs::SparseSet< T >::raw (const helios::engine::ecs::types::EntityId id)

inline nodiscard virtual

Returns a raw void pointer to the element at the given index.

Parameters

id	The EntityId to look up.

Returns: Raw pointer to the element, or `nullptr` if not found.

Definition at line 370 of file SparseSet.ixx.

370 [[nodiscard]] void* raw(const helios::engine::ecs::types::EntityId id) override {

371

372 T* ptr = get(id);

373 return static_cast<void*>(ptr);

374 }

Reference helios::engine::ecs::SparseSet< T >::get.

remove()

template <typename T>

bool helios::engine::ecs::SparseSet< T >::remove (const EntityId idx)

inline nodiscard virtual

Removes the element at the given index using swap-and-pop.

Uses the swap-and-pop technique for O(1) removal: 1. Move the last element to the position of the removed element 2. Update the sparse array entry for the moved element 3. Pop the last element from dense storage 4. Mark the removed slot as Tombstone

Parameters

idx	The EntityId of the element to remove.

Returns: `true` if the element was removed, `false` if not found.

Definition at line 297 of file SparseSet.ixx.

297 [[nodiscard]] bool remove(const EntityId idx) override {

298

299 if (idx >= sparse_.size() || sparse_[idx] == Tombstone) {

300 return false;

301 }

302

303 const auto denseIndex = sparse_[idx];

304 const auto sparseIdx = denseToSparse_[denseIndex];

305

306 assert(sparseIdx == idx && "Sparse index mismatch");

307

308 if (denseIndex != storage_.size() - 1) {

309 storage_[denseIndex] = std::move(storage_.back());

310 const auto newSparseIndex = denseToSparse_.back();

311 sparse_[newSparseIndex] = denseIndex;

312 denseToSparse_[denseIndex] = newSparseIndex;

313 }

314

315 storage_.pop_back();

316 denseToSparse_.pop_back();

317

318 sparse_[idx] = Tombstone;

319

320 return true;

321 }

Reference helios::engine::ecs::Tombstone.

Private Member Attributes

denseToSparse_

template <typename T>

std::vector<EntityId> helios::engine::ecs::SparseSet< T >::denseToSparse_

Reverse mapping from dense index to EntityId.

Used during swap-and-pop removal to update the sparse array.

Definition at line 171 of file SparseSet.ixx.

171 std::vector<EntityId> denseToSparse_;

sparse_

template <typename T>

std::vector<size_t> helios::engine::ecs::SparseSet< T >::sparse_

Maps EntityId to dense storage index.

Contains `Tombstone` for empty slots.

Definition at line 164 of file SparseSet.ixx.

164 std::vector<size_t> sparse_;

storage_

template <typename T>

std::vector<T> helios::engine::ecs::SparseSet< T >::storage_

Contiguous storage of elements.

Definition at line 176 of file SparseSet.ixx.

176 std::vector<T> storage_;

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

SparseSet.ixx

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.15.0.

Declaration​

Base class​

Public Constructors Index​

Public Operators Index​

Public Member Functions Index​

Private Member Attributes Index​

Description​

Public Constructors​

SparseSet()​

SparseSet()​

SparseSet()​

SparseSet()​

Public Operators​

operator=()​

operator=()​

Public Member Functions​

begin()​

begin()​

contains()​

emplace()​

end()​

end()​

get()​

get()​

insert()​

raw()​

remove()​

Private Member Attributes​

denseToSparse_​

sparse_​

storage_​

Declaration

Base class

Public Constructors Index

Public Operators Index

Public Member Functions Index

Private Member Attributes Index

Description

Public Constructors

SparseSet()

SparseSet()

SparseSet()

SparseSet()

Public Operators

operator=()

operator=()

Public Member Functions

begin()

begin()

contains()

emplace()

end()

end()

get()

get()

insert()

raw()

remove()

Private Member Attributes

denseToSparse_

sparse_

storage_