SparseSet Class Template

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

Declaration

template <typename T> class helios::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 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 storage. It maps `EntityId` indices to densely packed data of type `T`.

## Data Structure

``` SPARSE ARRAY (indexed by EntityId) [ 2 | x | 0 | x | 1 | x | x ] (dense idx)

DENSE STORAGE (contiguous) [ T[0] (id=2) | T[1] (id=4) | T[2] (id=0) ]

DENSE-TO-SPARSE (reverse mapping for swap-and-pop) [ 2 | 4 | 0 ] (EntityId)

x = 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.

Template Parameters

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

See Also

SparseSetBase

See Also

EntityId

See Also

EntityTombstone

Definition at line 117 of file SparseSet.ixx.

Public Constructors

SparseSet()

template <typename T>

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

default

Default constructor creating an empty sparse set.

Definition at line 144 of file SparseSet.ixx.

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

SparseSet()

template <typename T>

helios::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 151 of file SparseSet.ixx.

151 explicit SparseSet(const size_t capacity) {

152 sparse_.reserve(capacity);

153 storage_.reserve(capacity);

154 denseToSparse_.reserve(capacity);

155 };

SparseSet()

template <typename T>

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

delete

Copy operations are deleted to prevent accidental duplication.

Definition at line 161 of file SparseSet.ixx.

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

SparseSet()

template <typename T>

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

noexcept default

Move constructor.

Definition at line 171 of file SparseSet.ixx.

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

Public Operators

operator=()

template <typename T>

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

delete

Copy assignment is deleted.

Definition at line 166 of file SparseSet.ixx.

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

operator=()

template <typename T>

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

noexcept default

Move assignment operator.

Definition at line 176 of file SparseSet.ixx.

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

Public Member Functions

begin()

template <typename T>

Iterator helios::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 449 of file SparseSet.ixx.

449 [[nodiscard]] Iterator begin() {

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

451 }

begin()

template <typename T>

ConstIterator helios::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 467 of file SparseSet.ixx.

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

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

469 }

contains()

template <typename T>

bool helios::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.

Definition at line 324 of file SparseSet.ixx.

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

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

326 }

Reference helios::ecs::Tombstone.

emplace()

template <typename... Args>

T * helios::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 192 of file SparseSet.ixx.

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

193

194 // already in use

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

196 return nullptr;

197 }

198

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

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

201 }

202

203 const auto denseIndex = storage_.size();

204

205 denseToSparse_.push_back(idx);

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

207

208 sparse_[idx] = denseIndex;

209

210 return &storage_.back();

211 }

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

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

end()

template <typename T>

Iterator helios::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 458 of file SparseSet.ixx.

458 [[nodiscard]] Iterator end() {

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

460 }

end()

template <typename T>

ConstIterator helios::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 476 of file SparseSet.ixx.

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

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

478 }

get()

template <typename T>

T * helios::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 291 of file SparseSet.ixx.

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

292

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

294 return nullptr;

295 }

296

297 return &storage_[sparse_[idx]];

298 }

Reference helios::ecs::Tombstone.

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

get()

template <typename T>

const T * helios::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 307 of file SparseSet.ixx.

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

308

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

310 return nullptr;

311 }

312

313 return &storage_[sparse_[idx]];

314 }

Reference helios::ecs::Tombstone.

insert()

template <typename T>

T * helios::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 224 of file SparseSet.ixx.

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

225

226 // already in use

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

228 return nullptr;

229 }

230

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

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

233 }

234

235 const auto denseIndex = storage_.size();

236

237 denseToSparse_.push_back(idx);

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

239

240 sparse_[idx] = denseIndex;

241

242 return &storage_.back();

243 }

Reference helios::ecs::Tombstone.

raw()

template <typename T>

void * helios::ecs::SparseSet< T >::raw (const 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 331 of file SparseSet.ixx.

331 [[nodiscard]] void* raw(const EntityId id) override {

332 T* ptr = get(id);

333 return static_cast<void*>(ptr);

334 }

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

remove()

template <typename T>

bool helios::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 258 of file SparseSet.ixx.

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

259

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

261 return false;

262 }

263

264 const auto denseIndex = sparse_[idx];

265 const auto sparseIdx = denseToSparse_[denseIndex];

266

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

268

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

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

271 const auto newSparseIndex = denseToSparse_.back();

272 sparse_[newSparseIndex] = denseIndex;

273 denseToSparse_[denseIndex] = newSparseIndex;

274 }

275

276 storage_.pop_back();

277 denseToSparse_.pop_back();

278

279 sparse_[idx] = Tombstone;

280

281 return true;

282 }

Reference helios::ecs::Tombstone.

Private Member Attributes

denseToSparse_

template <typename T>

std::vector<EntityId> helios::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 132 of file SparseSet.ixx.

132 std::vector<EntityId> denseToSparse_;

sparse_

template <typename T>

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

Maps EntityId to dense storage index.

Contains `Tombstone` for empty slots.

Definition at line 125 of file SparseSet.ixx.

125 std::vector<size_t> sparse_;

storage_

template <typename T>

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

Contiguous storage of elements.

Definition at line 137 of file SparseSet.ixx.

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