Skip to main content

ecs/SparseSet.ixx File

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

Included Headers​

#include <cassert> #include <functional> #include <vector> #include <helios.ecs.types.TypeDefs> #include <helios.ecs.types.EntityHandle>

Namespaces Index​

namespacehelios
namespaceecs

Generic, reusable ECS primitives. 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-keyed 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-keyed storage.
4 */
5module;
6
7#include <cassert>
8#include <functional>
9#include <vector>
10
11export module helios.ecs.SparseSet;
12
13import helios.ecs.types.EntityHandle;
14import helios.ecs.types.TypeDefs;
15
16
17using namespace helios::ecs::types;
18export namespace helios::ecs {
19
20 /**
21 * @brief Abstract base class for type-erased sparse set access.
22 *
23 * `SparseSetBase` provides a non-templated interface for polymorphic
24 * operations on sparse sets. This enables containers to store
25 * heterogeneous pools and perform common operations (e.g., removal)
26 * without knowing the concrete element type.
27 *
28 * @see SparseSet
29 */
30 class SparseSetBase {
31
32 public:
33
34 /**
35 * @brief Virtual destructor for proper cleanup of derived classes.
36 */
37 virtual ~SparseSetBase() = default;
38
39 /**
40 * @brief Removes the element at the given index.
41 *
42 * @param id The EntityId of the element to remove.
43 *
44 * @return True if the element was removed, false if not found or
45 * removal was cancelled.
46 */
47 virtual bool remove(EntityId id) = 0;
48
49 /**
50 * @brief Checks whether an element exists for the specified EntityId.
51 *
52 * @param id The EntityId to test.
53 *
54 * @return True if the set contains the EntityId.
55 */
56 [[nodiscard]] virtual bool contains(EntityId id) const = 0;
57
58 /**
59 * @brief Returns a raw void pointer to the element at the given index.
60 *
61 * @param id The EntityId to look up.
62 *
63 * @return Raw pointer to the element, or `nullptr` if not found.
64 */
65 [[nodiscard]] virtual void* raw(EntityId id) = 0;
66 };
67
68
69 /**
70 * @brief Sentinel value indicating an empty slot in the sparse array.
71 *
72 * Aliased from `helios::core::types::EntityTombstone`.
73 */
74 constexpr auto Tombstone = EntityTombstone;
75
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 storage. It maps `EntityId`
82 * indices to densely packed data of type `T`.
83 *
84 * ## Data Structure
85 *
86 * ```
87 * SPARSE ARRAY (indexed by EntityId)
88 * [ 2 | x | 0 | x | 1 | x | x ] (dense idx)
89 *
90 * DENSE STORAGE (contiguous)
91 * [ T[0] (id=2) | T[1] (id=4) | T[2] (id=0) ]
92 *
93 * DENSE-TO-SPARSE (reverse mapping for swap-and-pop)
94 * [ 2 | 4 | 0 ] (EntityId)
95 *
96 * x = Tombstone (empty slot)
97 * ```
98 *
99 * ## Complexity
100 *
101 * | Operation | Time | Space |
102 * |-----------|---------|--------------|
103 * | emplace | O(1)* | O(max_id) |
104 * | insert | O(1)* | O(max_id) |
105 * | get | O(1) | - |
106 * | remove | O(1) | - |
107 *
108 * *Amortized due to potential sparse array resize.
109 *
110 * @tparam T The type of elements stored in the set. Must be move-assignable.
111 *
112 * @see SparseSetBase
113 * @see EntityId
114 * @see EntityTombstone
115 */
116 template <typename T>
117 class SparseSet : public SparseSetBase {
118
119
120 /**
121 * @brief Maps EntityId to dense storage index.
122 *
123 * Contains `Tombstone` for empty slots.
124 */
125 std::vector<size_t> sparse_;
126
127 /**
128 * @brief Reverse mapping from dense index to EntityId.
129 *
130 * Used during swap-and-pop removal to update the sparse array.
131 */
132 std::vector<EntityId> denseToSparse_;
133
134 /**
135 * @brief Contiguous storage of elements.
136 */
137 std::vector<T> storage_;
138
139 public:
140
141 /**
142 * @brief Default constructor creating an empty sparse set.
143 */
144 SparseSet() = default;
145
146 /**
147 * @brief Constructs a sparse set with pre-allocated capacity.
148 *
149 * @param capacity The initial capacity to reserve for all internal vectors.
150 */
151 explicit SparseSet(const size_t capacity) {
152 sparse_.reserve(capacity);
153 storage_.reserve(capacity);
154 denseToSparse_.reserve(capacity);
155 };
156
157
158 /**
159 * @brief Copy operations are deleted to prevent accidental duplication.
160 */
161 SparseSet(const SparseSet&) = delete;
162
163 /**
164 * @brief Copy assignment is deleted.
165 */
166 SparseSet& operator=(const SparseSet&) = delete;
167
168 /**
169 * @brief Move constructor.
170 */
171 SparseSet(SparseSet&&) noexcept = default;
172
173 /**
174 * @brief Move assignment operator.
175 */
176 SparseSet& operator=(SparseSet&&) noexcept = default;
177
178
179 /**
180 * @brief Constructs and inserts an element at the given index.
181 *
182 * Forwards arguments to construct `T` in-place.
183 *
184 * @tparam Args Constructor argument types.
185 *
186 * @param idx The EntityId to associate with the element.
187 * @param args Arguments forwarded to the `T` constructor.
188 *
189 * @return Pointer to the inserted element, or `nullptr` if the index is already occupied.
190 */
191 template <typename... Args>
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 }
212
213 /**
214 * @brief Inserts an element at the given index.
215 *
216 * If the sparse array is too small, it is resized to accommodate the index.
217 * Empty slots are filled with `Tombstone`.
218 *
219 * @param idx The EntityId to associate with the element.
220 * @param obj The element to insert (moved).
221 *
222 * @return Pointer to the inserted element, or `nullptr` if the index is already occupied.
223 */
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 }
244
245 /**
246 * @brief Removes the element at the given index using swap-and-pop.
247 *
248 * @details Uses the swap-and-pop technique for O(1) removal:
249 * 1 Move the last element to the position of the removed element
250 * 2 Update the sparse array entry for the moved element
251 * 3 Pop the last element from dense storage
252 * 4 Mark the removed slot as Tombstone
253 *
254 * @param idx The EntityId of the element to remove.
255 *
256 * @return True if the element was removed, false if not found.
257 */
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 }
283
284 /**
285 * @brief Retrieves the element at the given index.
286 *
287 * @param idx The EntityId to look up.
288 *
289 * @return Pointer to the element, or `nullptr` if not found.
290 */
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 }
299
300 /**
301 * @brief Retrieves the element at the given index.
302 *
303 * @param idx The EntityId to look up.
304 *
305 * @return Const pointer to the element, or `nullptr` if not found.
306 */
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 }
315
316
317 /**
318 * @brief Checks whether an element is registered for the specified EntityId.
319 *
320 * @param idx The EntityId to test.
321 *
322 * @return True if this sparse set contains the EntityId.
323 */
324 [[nodiscard]] bool contains(const EntityId idx) const override {
325 return idx < sparse_.size() && sparse_[idx] != Tombstone;
326 }
327
328 /**
329 * @copydoc SparseSetBase::raw
330 */
331 [[nodiscard]] void* raw(const EntityId id) override {
332 T* ptr = get(id);
333 return static_cast<void*>(ptr);
334 }
335
336
337 /**
338 * @brief Forward iterator for traversing the sparse set.
339 *
340 * @details Iterates over the dense storage array, providing access to both
341 * the stored element and its associated EntityId.
342 */
343 struct Iterator {
344 using DataIt = typename std::vector<T>::iterator;
345 using IdIt = typename std::vector<EntityId>::iterator;
346
347 /**
348 * @brief Iterator into the dense data storage.
349 */
350 DataIt dataIt_;
351
352 /**
353 * @brief Iterator into the dense-to-sparse ID mapping.
354 */
355 IdIt idIt_;
356
357 using iterator_category = std::forward_iterator_tag;
358 using value_type = T;
359 using difference_type = std::ptrdiff_t;
360 using pointer = T*;
361 using reference = T&;
362
363 Iterator() = default;
364
365 Iterator(DataIt dataIt, IdIt idIt) : dataIt_(dataIt), idIt_(idIt) {}
366
367 reference operator*() const { return *dataIt_; }
368 pointer operator->() const { return &*dataIt_; }
369
370 /**
371 * @brief Returns the EntityId for the current element.
372 *
373 * @return The EntityId associated with the current element.
374 */
375 [[nodiscard]] EntityId entityId() const { return *idIt_; }
376
377 [[nodiscard]] bool operator==(const Iterator& other) const { return dataIt_ == other.dataIt_;}
378 [[nodiscard]] bool operator!=(const Iterator& other) const { return dataIt_ != other.dataIt_;}
379
380 Iterator operator++(int) {
381 Iterator tmp = *this;
382 ++(*this);
383 return tmp;
384 }
385
386 Iterator& operator++() {
387 ++dataIt_; ++idIt_; return *this;
388 }
389 };
390
391 /**
392 * @brief Const forward iterator for traversing the sparse set.
393 *
394 * @details Provides read-only access to elements and their EntityIds.
395 */
396 struct ConstIterator {
397 using DataIt = typename std::vector<T>::const_iterator;
398 using IdIt = typename std::vector<EntityId>::const_iterator;
399
400 /**
401 * @brief Const iterator into the dense data storage.
402 */
403 DataIt dataIt_;
404
405 /**
406 * @brief Const iterator into the dense-to-sparse ID mapping.
407 */
408 IdIt idIt_;
409
410 using iterator_category = std::forward_iterator_tag;
411 using value_type = T;
412 using difference_type = std::ptrdiff_t;
413 using pointer = const T*;
414 using reference = const T&;
415
416 ConstIterator() = default;
417
418 ConstIterator(DataIt dataIt, IdIt idIt) : dataIt_(dataIt), idIt_(idIt) {}
419
420 reference operator*() const { return *dataIt_; }
421 pointer operator->() const { return &*dataIt_; }
422
423 /**
424 * @brief Returns the EntityId for the current element.
425 *
426 * @return The EntityId associated with the current element.
427 */
428 [[nodiscard]] EntityId entityId() const { return *idIt_; }
429
430 [[nodiscard]] bool operator==(const ConstIterator& other) const { return dataIt_ == other.dataIt_;}
431 [[nodiscard]] bool operator!=(const ConstIterator& other) const { return dataIt_ != other.dataIt_;}
432
433 ConstIterator operator++(int) {
434 ConstIterator tmp = *this;
435 ++(*this);
436 return tmp;
437 }
438
439 ConstIterator& operator++() {
440 ++dataIt_; ++idIt_; return *this;
441 }
442 };
443
444 /**
445 * @brief Returns an iterator to the beginning of the dense storage.
446 *
447 * @return Iterator pointing to the first element.
448 */
449 [[nodiscard]] Iterator begin() {
450 return Iterator(storage_.begin(), denseToSparse_.begin());
451 }
452
453 /**
454 * @brief Returns an iterator to the end of the dense storage.
455 *
456 * @return Iterator pointing past the last element.
457 */
458 [[nodiscard]] Iterator end() {
459 return Iterator(storage_.end(), denseToSparse_.end());
460 }
461
462 /**
463 * @brief Returns a const iterator to the beginning of the dense storage.
464 *
465 * @return ConstIterator pointing to the first element.
466 */
467 [[nodiscard]] ConstIterator begin() const {
468 return ConstIterator(storage_.begin(), denseToSparse_.begin());
469 }
470
471 /**
472 * @brief Returns a const iterator to the end of the dense storage.
473 *
474 * @return ConstIterator pointing past the last element.
475 */
476 [[nodiscard]] ConstIterator end() const {
477 return ConstIterator(storage_.end(), denseToSparse_.end());
478 }
479
480 };
481
482
483
484}

Generated via doxygen2docusaurus 2.0.0 by Doxygen 1.15.0.