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>
void	clear () override
	Clears all elements from the sparse set. 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.

Definition at line 126 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 153 of file SparseSet.ixx.

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 160 of file SparseSet.ixx.

160 explicit SparseSet(const size_t capacity) {

161 sparse_.reserve(capacity);

162 storage_.reserve(capacity);

163 denseToSparse_.reserve(capacity);

164 };

SparseSet()

template <typename T>

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

delete

Copy operations are deleted to prevent accidental duplication.

Definition at line 169 of file SparseSet.ixx.

SparseSet()

template <typename T>

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

noexcept default

Move constructor.

Definition at line 179 of file SparseSet.ixx.

Public Operators

operator=()

template <typename T>

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

delete

Copy assignment is deleted.

Definition at line 174 of file SparseSet.ixx.

operator=()

template <typename T>

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

noexcept default

Move assignment operator.

Definition at line 184 of file SparseSet.ixx.

Public Member Functions

begin()

template <typename T>

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

inline

Returns an iterator to the beginning of the dense storage.

Returns

Iterator pointing to the first element.

Definition at line 466 of file SparseSet.ixx.

466 [[nodiscard]] Iterator begin() {

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

468 }

begin()

template <typename T>

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

inline

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

Returns

ConstIterator pointing to the first element.

Definition at line 484 of file SparseSet.ixx.

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

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

486 }

clear()

template <typename T>

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

inline virtual

Clears all elements from the sparse set.

This operation removes all elements and resets the internal data structures, effectively making the set empty.

Definition at line 347 of file SparseSet.ixx.

347 void clear() override {

348 sparse_.clear();

349 denseToSparse_.clear();

350 storage_.clear();

351 }

contains()

template <typename T>

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

inline 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 332 of file SparseSet.ixx.

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

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

334 }

Reference helios::ecs::Tombstone.

emplace()

template <typename... Args>

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

inline

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 200 of file SparseSet.ixx.

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

201

202 // already in use

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

204 return nullptr;

205 }

206

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

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

209 }

210

211 const auto denseIndex = storage_.size();

212

213 denseToSparse_.push_back(idx);

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

215

216 sparse_[idx] = denseIndex;

217

218 return &storage_.back();

219 }

Reference helios::ecs::Tombstone.

end()

template <typename T>

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

inline

Returns an iterator to the end of the dense storage.

Returns

Iterator pointing past the last element.

Definition at line 475 of file SparseSet.ixx.

475 [[nodiscard]] Iterator end() {

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

477 }

end()

template <typename T>

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

inline

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

Returns

ConstIterator pointing past the last element.

Definition at line 493 of file SparseSet.ixx.

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

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

495 }

get()

template <typename T>

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

inline

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 299 of file SparseSet.ixx.

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

300

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

302 return nullptr;

303 }

304

305 return &storage_[sparse_[idx]];

306 }

Reference helios::ecs::Tombstone.

Referenced by helios::ecs::EntityManager< THandle, TEntityRegistry, TCapacity >::get and helios::ecs::SparseSet< T >::raw.

get()

template <typename T>

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

inline

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 315 of file SparseSet.ixx.

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

316

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

318 return nullptr;

319 }

320

321 return &storage_[sparse_[idx]];

322 }

Reference helios::ecs::Tombstone.

insert()

template <typename T>

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

inline

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 232 of file SparseSet.ixx.

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

233

234 // already in use

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

236 return nullptr;

237 }

238

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

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

241 }

242

243 const auto denseIndex = storage_.size();

244

245 denseToSparse_.push_back(idx);

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

247

248 sparse_[idx] = denseIndex;

249

250 return &storage_.back();

251 }

Reference helios::ecs::Tombstone.

raw()

template <typename T>

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

inline 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 339 of file SparseSet.ixx.

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

340 T* ptr = get(id);

341 return static_cast<void*>(ptr);

342 }

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

remove()

template <typename T>

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

inline 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 266 of file SparseSet.ixx.

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

267

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

269 return false;

270 }

271

272 const auto denseIndex = sparse_[idx];

273 const auto sparseIdx = denseToSparse_[denseIndex];

274

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

276

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

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

279 const auto newSparseIndex = denseToSparse_.back();

280 sparse_[newSparseIndex] = denseIndex;

281 denseToSparse_[denseIndex] = newSparseIndex;

282 }

283

284 storage_.pop_back();

285 denseToSparse_.pop_back();

286

287 sparse_[idx] = Tombstone;

288

289 return true;

290 }

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 141 of file SparseSet.ixx.

141 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 134 of file SparseSet.ixx.

134 std::vector<size_t> sparse_;

storage_

template <typename T>

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

Contiguous storage of elements.

Definition at line 146 of file SparseSet.ixx.

146 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.9.8.