Skip to main content

engine/ecs/SparseSet.ixx File

Generic sparse set data structure for efficient entity-component storage. More...

Included Headers​

#include <cassert> #include <functional> #include <vector> #include <helios.engine.ecs.Traits> #include <helios.engine.ecs.types>

Namespaces Index​

namespacehelios
namespaceengine

Main engine module aggregating core infrastructure and game systems. More...

namespaceecs

Core Entity-Component-System architecture. More...

Classes Index​

classSparseSetBase

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

classSparseSet<T>

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

structIterator

Forward iterator for traversing the sparse set. More...

structConstIterator

Const forward iterator for traversing the sparse set. More...

Description​

Generic sparse set data structure for efficient entity-component storage.

File Listing​

The file content with the documentation metadata removed is:

1/**
2 * @file SparseSet.ixx
3 * @brief Generic sparse set data structure for efficient entity-component storage.
4 */
5module;
6
7#include <cassert>
8#include <functional>
9#include <vector>
10
11export module helios.engine.ecs.SparseSet;
12
13import helios.engine.ecs.types;
14import helios.engine.ecs.Traits;
15
16export namespace helios::engine::ecs {
17
18 /**
19 * @brief Abstract base class for type-erased sparse set access.
20 *
21 * `SparseSetBase` provides a non-templated interface for polymorphic
22 * operations on sparse sets. This enables containers like `EntityManager`
23 * to store heterogeneous component pools and perform common operations
24 * (e.g., removal) without knowing the concrete component type.
25 *
26 * @see SparseSet
27 * @see EntityManager
28 */
29 class SparseSetBase {
30
31 public:
32
33 /**
34 * @brief Virtual destructor for proper cleanup of derived classes.
35 */
36 virtual ~SparseSetBase() = default;
37
38 /**
39 * @brief Removes the element at the given index.
40 *
41 * @param id The EntityId of the element to remove.
42 *
43 * @return `true` if the element was removed, `false` if not found or
44 * removal was cancelled.
45 */
46 virtual bool remove(helios::engine::ecs::types::EntityId id) = 0;
47
48 /**
49 * @brief Checks whether an element exists for the specified EntityId.
50 *
51 * @param id The EntityId to test.
52 *
53 * @return `true` if the set contains the EntityId, `false` otherwise.
54 */
55 [[nodiscard]] virtual bool contains(helios::engine::ecs::types::EntityId id) const = 0;
56
57 /**
58 * @brief Returns a raw void pointer to the element at the given index.
59 *
60 * @param id The EntityId to look up.
61 *
62 * @return Raw pointer to the element, or `nullptr` if not found.
63 */
64 [[nodiscard]] virtual void* raw(helios::engine::ecs::types::EntityId id) = 0;
65 };
66
67
68 /**
69 * @brief Sentinel value indicating an empty slot in the sparse array.
70 *
71 * Aliased from `helios::engine::ecs::types::EntityTombstone`.
72 */
73 constexpr auto Tombstone = helios::engine::ecs::types::EntityTombstone;
74
75 using namespace helios::engine::ecs::types;
76
77 /**
78 * @brief A generic sparse set providing O(1) insertion, lookup, and removal.
79 *
80 * `SparseSet` implements the sparse set data structure pattern, commonly used
81 * in Entity Component Systems (ECS) for efficient component storage. It maps
82 * `EntityId` indices to densely packed data of type `T`.
83 *
84 * ## Data Structure
85 *
86 * ```
87 * ┌─────────────────────────────────────────────────────────────┐
88 * │ SPARSE SET LAYOUT │
89 * ├─────────────────────────────────────────────────────────────┤
90 * │ │
91 * │ SPARSE ARRAY (indexed by EntityId) │
92 * │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │
93 * │ │ 2 │ × │ 0 │ × │ 1 │ × │ × │ (dense idx) │
94 * │ └──┬──┴─────┴──┬──┴─────┴──┬──┴─────┴─────┘ │
95 * │ │ │ │ │
96 * │ │ │ ┌────────┘ │
97 * │ │ ┌───────┘ │ │
98 * │ └───│──────────│────────┐ │
99 * │ ▼ ▼ ▼ │
100 * │ DENSE STORAGE (contiguous) │
101 * │ ┌─────────┬─────────┬─────────┐ │
102 * │ │ T[0] │ T[1] │ T[2] │ │
103 * │ │ (id=2) │ (id=4) │ (id=0) │ │
104 * │ └─────────┴─────────┴─────────┘ │
105 * │ │
106 * │ DENSE-TO-SPARSE (reverse mapping for swap-and-pop) │
107 * │ ┌─────┬─────┬─────┐ │
108 * │ │ 2 │ 4 │ 0 │ (EntityId) │
109 * │ └─────┴─────┴─────┘ │
110 * │ │
111 * │ × = Tombstone (empty slot) │
112 * └─────────────────────────────────────────────────────────────┘
113 * ```
114 *
115 * ## Complexity
116 *
117 * | Operation | Time | Space |
118 * |-----------|---------|--------------|
119 * | emplace | O(1)* | O(max_id) |
120 * | insert | O(1)* | O(max_id) |
121 * | get | O(1) | - |
122 * | remove | O(1) | - |
123 *
124 * *Amortized due to potential sparse array resize.
125 *
126 * ## Usage
127 *
128 * ```cpp
129 * SparseSet<TransformComponent> transforms;
130 *
131 * // In-place construction
132 * auto* transform = transforms.emplace(42, glm::vec3{0.0f}, glm::quat{}, glm::vec3{1.0f});
133 *
134 * // Or insert a pre-constructed object
135 * auto* inserted = transforms.insert(43, TransformComponent{...});
136 *
137 * // Mutable access
138 * if (auto* t = transforms.get(42)) {
139 * t->position = glm::vec3{10.0f, 0.0f, 0.0f};
140 * }
141 *
142 * // Const access
143 * const auto& constSet = transforms;
144 * if (const auto* t = constSet.get(42)) { }
145 *
146 * // Remove component
147 * transforms.remove(42);
148 * ```
149 *
150 * @tparam T The type of elements stored in the set. Must be move-assignable.
151 *
152 * @see EntityId
153 * @see EntityTombstone
154 */
155 template <typename T>
156 class SparseSet : public SparseSetBase {
157
158
159 /**
160 * @brief Maps EntityId to dense storage index.
161 *
162 * Contains `Tombstone` for empty slots.
163 */
164 std::vector<size_t> sparse_;
165
166 /**
167 * @brief Reverse mapping from dense index to EntityId.
168 *
169 * Used during swap-and-pop removal to update the sparse array.
170 */
171 std::vector<EntityId> denseToSparse_;
172
173 /**
174 * @brief Contiguous storage of elements.
175 */
176 std::vector<T> storage_;
177
178 public:
179
180 /**
181 * @brief Default constructor creating an empty sparse set.
182 */
183 SparseSet() = default;
184
185 /**
186 * @brief Constructs a sparse set with pre-allocated capacity.
187 *
188 * @param capacity The initial capacity to reserve for all internal vectors.
189 */
190 explicit SparseSet(const size_t capacity) {
191 sparse_.reserve(capacity);
192 storage_.reserve(capacity);
193 denseToSparse_.reserve(capacity);
194 };
195
196 /**
197 * @brief Copy operations are deleted to prevent accidental duplication.
198 */
199 SparseSet(const SparseSet&) = delete;
200
201 /**
202 * @brief Copy assignment is deleted.
203 */
204 SparseSet& operator=(const SparseSet&) = delete;
205
206 /**
207 * @brief Move constructor.
208 */
209 SparseSet(SparseSet&&) noexcept = default;
210
211 /**
212 * @brief Move assignment operator.
213 */
214 SparseSet& operator=(SparseSet&&) noexcept = default;
215
216
217 /**
218 * @brief Constructs and inserts an element at the given index.
219 *
220 * Forwards arguments to construct `T` in-place.
221 *
222 * @tparam Args Constructor argument types.
223 *
224 * @param idx The EntityId to associate with the element.
225 * @param args Arguments forwarded to the `T` constructor.
226 *
227 * @return Pointer to the inserted element, or `nullptr` if the index is already occupied.
228 */
229 template <typename... Args>
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 }
250
251 /**
252 * @brief Inserts an element at the given index.
253 *
254 * If the sparse array is too small, it is resized to accommodate the index.
255 * Empty slots are filled with `Tombstone`.
256 *
257 * @param idx The EntityId to associate with the element.
258 * @param obj The element to insert (moved).
259 *
260 * @return Pointer to the inserted element, or `nullptr` if the index is already occupied.
261 */
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 }
282
283
284 /**
285 * @brief Removes the element at the given index using swap-and-pop.
286 *
287 * @details Uses the swap-and-pop technique for O(1) removal:
288 * 1 Move the last element to the position of the removed element
289 * 2 Update the sparse array entry for the moved element
290 * 3 Pop the last element from dense storage
291 * 4 Mark the removed slot as Tombstone
292 *
293 * @param idx The EntityId of the element to remove.
294 *
295 * @return `true` if the element was removed, `false` if not found.
296 */
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 }
322
323 /**
324 * @brief Retrieves the element at the given index.
325 *
326 * @param idx The EntityId to look up.
327 *
328 * @return Pointer to the element, or `nullptr` if not found.
329 */
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 }
338
339 /**
340 * @brief Retrieves the element at the given index.
341 *
342 * @param idx The EntityId to look up.
343 *
344 * @return Const Pointer to the element, or `nullptr` if not found.
345 */
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 }
354
355
356 /**
357 * @brief Checks whether an element is registered for the specified EntityId.
358 *
359 * @param idx The entityId to test.
360 *
361 * @return True if this sparse set contains the entityId, otherwise false.
362 */
363 [[nodiscard]] bool contains(const EntityId idx) const override {
364 return idx < sparse_.size() && sparse_[idx] != Tombstone;
365 }
366
367 /**
368 * @copydoc SparseSetBase::raw
369 */
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 }
375
376
377 /**
378 * @brief Forward iterator for traversing the sparse set.
379 *
380 * @details Iterates over the dense storage array, providing access to both
381 * the stored element and its associated EntityId.
382 */
383 struct Iterator {
384 using DataIt = typename std::vector<T>::iterator;
385 using IdIt = typename std::vector<EntityId>::iterator;
386
387 DataIt dataIt_;
388 IdIt idIt_;
389
390 using iterator_category = std::forward_iterator_tag;
391 using value_type = T;
392 using difference_type = std::ptrdiff_t;
393 using pointer = T*;
394 using reference = T&;
395
396 Iterator() = default;
397
398 Iterator(DataIt dataIt, IdIt idIt) : dataIt_(dataIt), idIt_(idIt) {}
399
400 reference operator*() const { return *dataIt_; }
401 pointer operator->() const { return &*dataIt_; }
402
403 /**
404 * @brief Returns the EntityId for the current element.
405 *
406 * @return The EntityId associated with the current element.
407 */
408 [[nodiscard]] EntityId entityId() const { return *idIt_; }
409
410 [[nodiscard]] bool operator==(const Iterator& other) const { return dataIt_ == other.dataIt_;}
411 [[nodiscard]] bool operator!=(const Iterator& other) const { return dataIt_ != other.dataIt_;}
412
413 Iterator& operator++(int) {
414 Iterator tmp = *this;
415 ++(*this);
416 return tmp;
417 }
418
419 Iterator& operator++() {
420 ++dataIt_; ++idIt_; return *this;
421 }
422 };
423
424 /**
425 * @brief Const forward iterator for traversing the sparse set.
426 *
427 * @details Provides read-only access to elements and their EntityIds.
428 */
429 struct ConstIterator {
430 using DataIt = typename std::vector<T>::const_iterator;
431 using IdIt = typename std::vector<EntityId>::const_iterator;
432
433 DataIt dataIt_;
434 IdIt idIt_;
435
436 using iterator_category = std::forward_iterator_tag;
437 using value_type = T;
438 using difference_type = std::ptrdiff_t;
439 using pointer = const T*;
440 using reference = const T&;
441
442 ConstIterator() = default;
443
444 ConstIterator(DataIt dataIt, IdIt idIt) : dataIt_(dataIt), idIt_(idIt) {}
445
446 reference operator*() const { return *dataIt_; }
447 pointer operator->() const { return &*dataIt_; }
448
449 /**
450 * @brief Returns the EntityId for the current element.
451 *
452 * @return The EntityId associated with the current element.
453 */
454 [[nodiscard]] EntityId entityId() const { return *idIt_; }
455
456 [[nodiscard]] bool operator==(const ConstIterator& other) const { return dataIt_ == other.dataIt_;}
457 [[nodiscard]] bool operator!=(const ConstIterator& other) const { return dataIt_ != other.dataIt_;}
458
459 ConstIterator& operator++(int) {
460 ConstIterator tmp = *this;
461 ++(*this);
462 return tmp;
463 }
464
465 ConstIterator& operator++() {
466 ++dataIt_; ++idIt_; return *this;
467 }
468 };
469
470 /**
471 * @brief Returns an iterator to the beginning of the dense storage.
472 *
473 * @return Iterator pointing to the first element.
474 */
475 [[nodiscard]] Iterator begin() {
476 return Iterator(storage_.begin(), denseToSparse_.begin());
477 }
478
479 /**
480 * @brief Returns an iterator to the end of the dense storage.
481 *
482 * @return Iterator pointing past the last element.
483 */
484 [[nodiscard]] Iterator end() {
485 return Iterator(storage_.end(), denseToSparse_.end());
486 }
487
488 /**
489 * @brief Returns a const iterator to the beginning of the dense storage.
490 *
491 * @return ConstIterator pointing to the first element.
492 */
493 [[nodiscard]] ConstIterator begin() const {
494 return ConstIterator(storage_.begin(), denseToSparse_.begin());
495 }
496
497 /**
498 * @brief Returns a const iterator to the end of the dense storage.
499 *
500 * @return ConstIterator pointing past the last element.
501 */
502 [[nodiscard]] ConstIterator end() const {
503 return ConstIterator(storage_.end(), denseToSparse_.end());
504 }
505
506 };
507
508
509
510}

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.15.0.