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.

Definition at line 118 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 145 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 152 of file SparseSet.ixx.

152 explicit SparseSet(const size_t capacity) {

153 sparse_.reserve(capacity);

154 storage_.reserve(capacity);

155 denseToSparse_.reserve(capacity);

156 };

SparseSet()

template <typename T>

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

delete

Copy operations are deleted to prevent accidental duplication.

Definition at line 162 of file SparseSet.ixx.

SparseSet()

template <typename T>

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

noexcept default

Move constructor.

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

operator=()

template <typename T>

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

noexcept default

Move assignment operator.

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

450 [[nodiscard]] Iterator begin() {

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

452 }

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

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

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

470 }

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

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

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

327 }

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

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

194

195 // already in use

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

197 return nullptr;

198 }

199

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

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

202 }

203

204 const auto denseIndex = storage_.size();

205

206 denseToSparse_.push_back(idx);

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

208

209 sparse_[idx] = denseIndex;

210

211 return &storage_.back();

212 }

Reference helios::ecs::Tombstone.

Referenced by helios::ecs::EntityManager< THandle, TEntityRegistry, TCapacity >::emplace.

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

459 [[nodiscard]] Iterator end() {

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

461 }

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

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

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

479 }

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

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

293

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

295 return nullptr;

296 }

297

298 return &storage_[sparse_[idx]];

299 }

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

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

309

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

311 return nullptr;

312 }

313

314 return &storage_[sparse_[idx]];

315 }

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

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

226

227 // already in use

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

229 return nullptr;

230 }

231

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

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

234 }

235

236 const auto denseIndex = storage_.size();

237

238 denseToSparse_.push_back(idx);

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

240

241 sparse_[idx] = denseIndex;

242

243 return &storage_.back();

244 }

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

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

333 T* ptr = get(id);

334 return static_cast<void*>(ptr);

335 }

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

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

260

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

262 return false;

263 }

264

265 const auto denseIndex = sparse_[idx];

266 const auto sparseIdx = denseToSparse_[denseIndex];

267

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

269

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

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

272 const auto newSparseIndex = denseToSparse_.back();

273 sparse_[newSparseIndex] = denseIndex;

274 denseToSparse_[denseIndex] = newSparseIndex;

275 }

276

277 storage_.pop_back();

278 denseToSparse_.pop_back();

279

280 sparse_[idx] = Tombstone;

281

282 return true;

283 }

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

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

126 std::vector<size_t> sparse_;

storage_

template <typename T>

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

Contiguous storage of elements.

Definition at line 138 of file SparseSet.ixx.

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