EnTT  3.10.0
sparse_set.hpp
1 #ifndef ENTT_ENTITY_SPARSE_SET_HPP
2 #define ENTT_ENTITY_SPARSE_SET_HPP
3 
4 #include <cstddef>
5 #include <iterator>
6 #include <memory>
7 #include <type_traits>
8 #include <utility>
9 #include <vector>
10 #include "../config/config.h"
11 #include "../core/algorithm.hpp"
12 #include "../core/any.hpp"
13 #include "../core/memory.hpp"
14 #include "../core/type_info.hpp"
15 #include "entity.hpp"
16 #include "fwd.hpp"
17 
18 namespace entt {
19 
25 namespace internal {
26 
27 template<typename Container>
28 struct sparse_set_iterator final {
29  using value_type = typename Container::value_type;
30  using pointer = typename Container::const_pointer;
31  using reference = typename Container::const_reference;
32  using difference_type = typename Container::difference_type;
33  using iterator_category = std::random_access_iterator_tag;
34 
35  sparse_set_iterator() ENTT_NOEXCEPT
36  : packed{},
37  offset{} {}
38 
39  sparse_set_iterator(const Container &ref, const difference_type idx) ENTT_NOEXCEPT
40  : packed{std::addressof(ref)},
41  offset{idx} {}
42 
43  sparse_set_iterator &operator++() ENTT_NOEXCEPT {
44  return --offset, *this;
45  }
46 
47  sparse_set_iterator operator++(int) ENTT_NOEXCEPT {
48  sparse_set_iterator orig = *this;
49  return ++(*this), orig;
50  }
51 
52  sparse_set_iterator &operator--() ENTT_NOEXCEPT {
53  return ++offset, *this;
54  }
55 
56  sparse_set_iterator operator--(int) ENTT_NOEXCEPT {
57  sparse_set_iterator orig = *this;
58  return operator--(), orig;
59  }
60 
61  sparse_set_iterator &operator+=(const difference_type value) ENTT_NOEXCEPT {
62  offset -= value;
63  return *this;
64  }
65 
66  sparse_set_iterator operator+(const difference_type value) const ENTT_NOEXCEPT {
67  sparse_set_iterator copy = *this;
68  return (copy += value);
69  }
70 
71  sparse_set_iterator &operator-=(const difference_type value) ENTT_NOEXCEPT {
72  return (*this += -value);
73  }
74 
75  sparse_set_iterator operator-(const difference_type value) const ENTT_NOEXCEPT {
76  return (*this + -value);
77  }
78 
79  [[nodiscard]] reference operator[](const difference_type value) const ENTT_NOEXCEPT {
80  return packed->data()[index() - value];
81  }
82 
83  [[nodiscard]] pointer operator->() const ENTT_NOEXCEPT {
84  return packed->data() + index();
85  }
86 
87  [[nodiscard]] reference operator*() const ENTT_NOEXCEPT {
88  return *operator->();
89  }
90 
91  [[nodiscard]] difference_type index() const ENTT_NOEXCEPT {
92  return offset - 1;
93  }
94 
95 private:
96  const Container *packed;
97  difference_type offset;
98 };
99 
100 template<typename Type, typename Other>
101 [[nodiscard]] std::ptrdiff_t operator-(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
102  return rhs.index() - lhs.index();
103 }
104 
105 template<typename Type, typename Other>
106 [[nodiscard]] bool operator==(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
107  return lhs.index() == rhs.index();
108 }
109 
110 template<typename Type, typename Other>
111 [[nodiscard]] bool operator!=(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
112  return !(lhs == rhs);
113 }
114 
115 template<typename Type, typename Other>
116 [[nodiscard]] bool operator<(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
117  return lhs.index() > rhs.index();
118 }
119 
120 template<typename Type, typename Other>
121 [[nodiscard]] bool operator>(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
122  return lhs.index() < rhs.index();
123 }
124 
125 template<typename Type, typename Other>
126 [[nodiscard]] bool operator<=(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
127  return !(lhs > rhs);
128 }
129 
130 template<typename Type, typename Other>
131 [[nodiscard]] bool operator>=(const sparse_set_iterator<Type> &lhs, const sparse_set_iterator<Other> &rhs) ENTT_NOEXCEPT {
132  return !(lhs < rhs);
133 }
134 
135 } // namespace internal
136 
143 enum class deletion_policy : std::uint8_t {
145  swap_and_pop = 0u,
147  in_place = 1u
148 };
149 
173 template<typename Entity, typename Allocator>
175  using alloc_traits = std::allocator_traits<Allocator>;
176  static_assert(std::is_same_v<typename alloc_traits::value_type, Entity>, "Invalid value type");
177  using sparse_container_type = std::vector<typename alloc_traits::pointer, typename alloc_traits::template rebind_alloc<typename alloc_traits::pointer>>;
178  using packed_container_type = std::vector<Entity, Allocator>;
180 
181  [[nodiscard]] auto sparse_ptr(const Entity entt) const {
182  const auto pos = static_cast<size_type>(entity_traits::to_entity(entt));
183  const auto page = pos / entity_traits::page_size;
184  return (page < sparse.size() && sparse[page]) ? (sparse[page] + fast_mod(pos, entity_traits::page_size)) : nullptr;
185  }
186 
187  [[nodiscard]] auto &sparse_ref(const Entity entt) const {
188  ENTT_ASSERT(sparse_ptr(entt), "Invalid element");
189  const auto pos = static_cast<size_type>(entity_traits::to_entity(entt));
190  return sparse[pos / entity_traits::page_size][fast_mod(pos, entity_traits::page_size)];
191  }
192 
193  [[nodiscard]] auto &assure_at_least(const Entity entt) {
194  const auto pos = static_cast<size_type>(entity_traits::to_entity(entt));
195  const auto page = pos / entity_traits::page_size;
196 
197  if(!(page < sparse.size())) {
198  sparse.resize(page + 1u, nullptr);
199  }
200 
201  if(!sparse[page]) {
202  auto page_allocator{packed.get_allocator()};
203  sparse[page] = alloc_traits::allocate(page_allocator, entity_traits::page_size);
204  std::uninitialized_fill(sparse[page], sparse[page] + entity_traits::page_size, null);
205  }
206 
207  auto &elem = sparse[page][fast_mod(pos, entity_traits::page_size)];
208  ENTT_ASSERT(entity_traits::to_version(elem) == entity_traits::to_version(tombstone), "Slot not available");
209  return elem;
210  }
211 
212  void release_sparse_pages() {
213  auto page_allocator{packed.get_allocator()};
214 
215  for(auto &&page: sparse) {
216  if(page != nullptr) {
217  std::destroy(page, page + entity_traits::page_size);
218  alloc_traits::deallocate(page_allocator, page, entity_traits::page_size);
219  page = nullptr;
220  }
221  }
222  }
223 
224 private:
225  virtual const void *get_at(const std::size_t) const {
226  return nullptr;
227  }
228 
229  virtual void swap_at(const std::size_t, const std::size_t) {}
230  virtual void move_element(const std::size_t, const std::size_t) {}
231 
232 protected:
234  using basic_iterator = internal::sparse_set_iterator<packed_container_type>;
235 
241  virtual void swap_and_pop(basic_iterator first, basic_iterator last) {
242  for(; first != last; ++first) {
243  sparse_ref(packed.back()) = entity_traits::combine(static_cast<typename entity_traits::entity_type>(first.index()), entity_traits::to_integral(packed.back()));
244  const auto entt = std::exchange(packed[first.index()], packed.back());
245  // unnecessary but it helps to detect nasty bugs
246  ENTT_ASSERT((packed.back() = tombstone, true), "");
247  // lazy self-assignment guard
248  sparse_ref(entt) = null;
249  packed.pop_back();
250  }
251  }
252 
258  virtual void in_place_pop(basic_iterator first, basic_iterator last) {
259  for(; first != last; ++first) {
260  sparse_ref(*first) = null;
261  packed[first.index()] = std::exchange(free_list, entity_traits::combine(static_cast<typename entity_traits::entity_type>(first.index()), entity_traits::reserved));
262  }
263  }
264 
271  virtual basic_iterator try_emplace(const Entity entt, const bool force_back, const void * = nullptr) {
272  ENTT_ASSERT(!contains(entt), "Set already contains entity");
273 
274  if(auto &elem = assure_at_least(entt); free_list == null || force_back) {
275  packed.push_back(entt);
276  elem = entity_traits::combine(static_cast<typename entity_traits::entity_type>(packed.size() - 1u), entity_traits::to_integral(entt));
277  return begin();
278  } else {
279  const auto pos = static_cast<size_type>(entity_traits::to_entity(free_list));
281  free_list = std::exchange(packed[pos], entt);
282  return --(end() - pos);
283  }
284  }
285 
286 public:
288  using allocator_type = Allocator;
290  using entity_type = Entity;
294  using size_type = typename packed_container_type::size_type;
296  using pointer = typename packed_container_type::const_pointer;
302  using reverse_iterator = std::reverse_iterator<iterator>;
305 
308  : basic_sparse_set{type_id<void>()} {}
309 
314  explicit basic_sparse_set(const allocator_type &allocator)
315  : basic_sparse_set{type_id<void>(), deletion_policy::swap_and_pop, allocator} {}
316 
322  explicit basic_sparse_set(deletion_policy pol, const allocator_type &allocator = {})
323  : basic_sparse_set{type_id<void>(), pol, allocator} {}
324 
332  explicit basic_sparse_set(const type_info &value, deletion_policy pol = deletion_policy::swap_and_pop, const allocator_type &allocator = {})
333  : sparse{allocator},
334  packed{allocator},
335  info{&value},
336  free_list{tombstone},
337  mode{pol} {}
338 
343  basic_sparse_set(basic_sparse_set &&other) ENTT_NOEXCEPT
344  : sparse{std::move(other.sparse)},
345  packed{std::move(other.packed)},
346  info{other.info},
347  free_list{std::exchange(other.free_list, tombstone)},
348  mode{other.mode} {}
349 
355  basic_sparse_set(basic_sparse_set &&other, const allocator_type &allocator) ENTT_NOEXCEPT
356  : sparse{std::move(other.sparse), allocator},
357  packed{std::move(other.packed), allocator},
358  info{other.info},
359  free_list{std::exchange(other.free_list, tombstone)},
360  mode{other.mode} {
361  ENTT_ASSERT(alloc_traits::is_always_equal::value || packed.get_allocator() == other.packed.get_allocator(), "Copying a sparse set is not allowed");
362  }
363 
365  virtual ~basic_sparse_set() {
366  release_sparse_pages();
367  }
368 
374  basic_sparse_set &operator=(basic_sparse_set &&other) ENTT_NOEXCEPT {
375  ENTT_ASSERT(alloc_traits::is_always_equal::value || packed.get_allocator() == other.packed.get_allocator(), "Copying a sparse set is not allowed");
376 
377  release_sparse_pages();
378  sparse = std::move(other.sparse);
379  packed = std::move(other.packed);
380  info = other.info;
381  free_list = std::exchange(other.free_list, tombstone);
382  mode = other.mode;
383  return *this;
384  }
385 
390  void swap(basic_sparse_set &other) {
391  using std::swap;
392  swap(sparse, other.sparse);
393  swap(packed, other.packed);
394  swap(info, other.info);
395  swap(free_list, other.free_list);
396  swap(mode, other.mode);
397  }
398 
403  [[nodiscard]] constexpr allocator_type get_allocator() const ENTT_NOEXCEPT {
404  return packed.get_allocator();
405  }
406 
411  [[nodiscard]] deletion_policy policy() const ENTT_NOEXCEPT {
412  return mode;
413  }
414 
423  virtual void reserve(const size_type cap) {
424  packed.reserve(cap);
425  }
426 
432  [[nodiscard]] virtual size_type capacity() const ENTT_NOEXCEPT {
433  return packed.capacity();
434  }
435 
437  virtual void shrink_to_fit() {
438  packed.shrink_to_fit();
439  }
440 
451  [[nodiscard]] size_type extent() const ENTT_NOEXCEPT {
452  return sparse.size() * entity_traits::page_size;
453  }
454 
465  [[nodiscard]] size_type size() const ENTT_NOEXCEPT {
466  return packed.size();
467  }
468 
473  [[nodiscard]] bool empty() const ENTT_NOEXCEPT {
474  return packed.empty();
475  }
476 
481  [[nodiscard]] pointer data() const ENTT_NOEXCEPT {
482  return packed.data();
483  }
484 
494  [[nodiscard]] const_iterator begin() const ENTT_NOEXCEPT {
495  const auto pos = static_cast<typename iterator::difference_type>(packed.size());
496  return iterator{packed, pos};
497  }
498 
500  [[nodiscard]] const_iterator cbegin() const ENTT_NOEXCEPT {
501  return begin();
502  }
503 
514  [[nodiscard]] iterator end() const ENTT_NOEXCEPT {
515  return iterator{packed, {}};
516  }
517 
519  [[nodiscard]] const_iterator cend() const ENTT_NOEXCEPT {
520  return end();
521  }
522 
533  [[nodiscard]] const_reverse_iterator rbegin() const ENTT_NOEXCEPT {
534  return std::make_reverse_iterator(end());
535  }
536 
538  [[nodiscard]] const_reverse_iterator crbegin() const ENTT_NOEXCEPT {
539  return rbegin();
540  }
541 
552  [[nodiscard]] reverse_iterator rend() const ENTT_NOEXCEPT {
553  return std::make_reverse_iterator(begin());
554  }
555 
557  [[nodiscard]] const_reverse_iterator crend() const ENTT_NOEXCEPT {
558  return rend();
559  }
560 
567  [[nodiscard]] iterator find(const entity_type entt) const ENTT_NOEXCEPT {
568  return contains(entt) ? --(end() - index(entt)) : end();
569  }
570 
576  [[nodiscard]] bool contains(const entity_type entt) const ENTT_NOEXCEPT {
577  const auto elem = sparse_ptr(entt);
578  constexpr auto cap = entity_traits::to_entity(null);
579  // testing versions permits to avoid accessing the packed array
580  return elem && (((~cap & entity_traits::to_integral(entt)) ^ entity_traits::to_integral(*elem)) < cap);
581  }
582 
589  [[nodiscard]] version_type current(const entity_type entt) const ENTT_NOEXCEPT {
590  const auto elem = sparse_ptr(entt);
591  constexpr auto fallback = entity_traits::to_version(tombstone);
592  return elem ? entity_traits::to_version(*elem) : fallback;
593  }
594 
605  [[nodiscard]] size_type index(const entity_type entt) const ENTT_NOEXCEPT {
606  ENTT_ASSERT(contains(entt), "Set does not contain entity");
607  return static_cast<size_type>(entity_traits::to_entity(sparse_ref(entt)));
608  }
609 
615  [[nodiscard]] entity_type at(const size_type pos) const ENTT_NOEXCEPT {
616  return pos < packed.size() ? packed[pos] : null;
617  }
618 
624  [[nodiscard]] entity_type operator[](const size_type pos) const ENTT_NOEXCEPT {
625  ENTT_ASSERT(pos < packed.size(), "Position is out of bounds");
626  return packed[pos];
627  }
628 
639  const void *get(const entity_type entt) const ENTT_NOEXCEPT {
640  return get_at(index(entt));
641  }
642 
644  void *get(const entity_type entt) ENTT_NOEXCEPT {
645  return const_cast<void *>(std::as_const(*this).get(entt));
646  }
647 
660  iterator emplace(const entity_type entt, const void *value = nullptr) {
661  return try_emplace(entt, false, value);
662  }
663 
673  void bump(const entity_type entt) {
674  auto &entity = sparse_ref(entt);
676  packed[static_cast<size_type>(entity_traits::to_entity(entity))] = entt;
677  }
678 
692  template<typename It>
693  iterator insert(It first, It last) {
694  for(auto it = first; it != last; ++it) {
695  try_emplace(*it, true);
696  }
697 
698  return first == last ? end() : find(*first);
699  }
700 
710  void erase(const entity_type entt) {
711  const auto it = --(end() - index(entt));
712  (mode == deletion_policy::in_place) ? in_place_pop(it, it + 1u) : swap_and_pop(it, it + 1u);
713  }
714 
724  template<typename It>
725  void erase(It first, It last) {
726  if constexpr(std::is_same_v<It, basic_iterator>) {
727  (mode == deletion_policy::in_place) ? in_place_pop(first, last) : swap_and_pop(first, last);
728  } else {
729  for(; first != last; ++first) {
730  erase(*first);
731  }
732  }
733  }
734 
740  bool remove(const entity_type entt) {
741  return contains(entt) && (erase(entt), true);
742  }
743 
751  template<typename It>
752  size_type remove(It first, It last) {
753  size_type count{};
754 
755  for(; first != last; ++first) {
756  count += remove(*first);
757  }
758 
759  return count;
760  }
761 
763  void compact() {
764  size_type from = packed.size();
765  for(; from && packed[from - 1u] == tombstone; --from) {}
766 
767  for(auto *it = &free_list; *it != null && from; it = std::addressof(packed[entity_traits::to_entity(*it)])) {
768  if(const size_type to = entity_traits::to_entity(*it); to < from) {
769  --from;
770  move_element(from, to);
771 
772  using std::swap;
773  swap(packed[from], packed[to]);
774 
775  const auto entity = static_cast<typename entity_traits::entity_type>(to);
776  sparse_ref(packed[to]) = entity_traits::combine(entity, entity_traits::to_integral(packed[to]));
778  for(; from && packed[from - 1u] == tombstone; --from) {}
779  }
780  }
781 
782  free_list = tombstone;
783  packed.resize(from);
784  }
785 
799  void swap_elements(const entity_type lhs, const entity_type rhs) {
800  ENTT_ASSERT(contains(lhs) && contains(rhs), "Set does not contain entities");
801 
802  auto &entt = sparse_ref(lhs);
803  auto &other = sparse_ref(rhs);
804 
805  const auto from = entity_traits::to_entity(entt);
806  const auto to = entity_traits::to_entity(other);
807 
808  // basic no-leak guarantee (with invalid state) if swapping throws
809  swap_at(static_cast<size_type>(from), static_cast<size_type>(to));
811  other = entity_traits::combine(from, entity_traits::to_integral(packed[to]));
812 
813  using std::swap;
814  swap(packed[from], packed[to]);
815  }
816 
847  template<typename Compare, typename Sort = std_sort, typename... Args>
848  void sort_n(const size_type length, Compare compare, Sort algo = Sort{}, Args &&...args) {
849  ENTT_ASSERT(!(length > packed.size()), "Length exceeds the number of elements");
850  ENTT_ASSERT(free_list == null, "Partial sorting with tombstones is not supported");
851 
852  algo(packed.rend() - length, packed.rend(), std::move(compare), std::forward<Args>(args)...);
853 
854  for(size_type pos{}; pos < length; ++pos) {
855  auto curr = pos;
856  auto next = index(packed[curr]);
857 
858  while(curr != next) {
859  const auto idx = index(packed[next]);
860  const auto entt = packed[curr];
861 
862  swap_at(next, idx);
863  const auto entity = static_cast<typename entity_traits::entity_type>(curr);
864  sparse_ref(entt) = entity_traits::combine(entity, entity_traits::to_integral(packed[curr]));
865  curr = std::exchange(next, idx);
866  }
867  }
868  }
869 
882  template<typename Compare, typename Sort = std_sort, typename... Args>
883  void sort(Compare compare, Sort algo = Sort{}, Args &&...args) {
884  compact();
885  sort_n(packed.size(), std::move(compare), std::move(algo), std::forward<Args>(args)...);
886  }
887 
903  void respect(const basic_sparse_set &other) {
904  compact();
905 
906  const auto to = other.end();
907  auto from = other.begin();
908 
909  for(size_type pos = packed.size() - 1; pos && from != to; ++from) {
910  if(contains(*from)) {
911  if(*from != packed[pos]) {
912  // basic no-leak guarantee (with invalid state) if swapping throws
913  swap_elements(packed[pos], *from);
914  }
915 
916  --pos;
917  }
918  }
919  }
920 
922  void clear() {
923  if(const auto last = end(); free_list == null) {
924  in_place_pop(begin(), last);
925  } else {
926  for(auto &&entity: *this) {
927  // tombstone filter on itself
928  if(const auto it = find(entity); it != last) {
929  in_place_pop(it, it + 1u);
930  }
931  }
932  }
933 
934  free_list = tombstone;
935  packed.clear();
936  }
937 
942  const type_info &type() const ENTT_NOEXCEPT {
943  return *info;
944  }
945 
947  virtual void bind(any) ENTT_NOEXCEPT {}
948 
949 private:
950  sparse_container_type sparse;
951  packed_container_type packed;
952  const type_info *info;
953  entity_type free_list;
954  deletion_policy mode;
955 };
956 
957 } // namespace entt
958 
959 #endif
Basic sparse set implementation.
Definition: sparse_set.hpp:174
deletion_policy policy() const
Returns the deletion policy of a sparse set.
Definition: sparse_set.hpp:411
void erase(const entity_type entt)
Erases an entity from a sparse set.
Definition: sparse_set.hpp:710
void swap(basic_sparse_set &other)
Exchanges the contents with those of a given sparse set.
Definition: sparse_set.hpp:390
const_reverse_iterator crbegin() const
Returns a reverse iterator to the beginning.
Definition: sparse_set.hpp:538
size_type index(const entity_type entt) const
Returns the position of an entity in a sparse set.
Definition: sparse_set.hpp:605
basic_sparse_set(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition: sparse_set.hpp:314
reverse_iterator rend() const
Returns a reverse iterator to the end.
Definition: sparse_set.hpp:552
virtual basic_iterator try_emplace(const Entity entt, const bool force_back, const void *=nullptr)
Assigns an entity to a sparse set.
Definition: sparse_set.hpp:271
void erase(It first, It last)
Erases entities from a set.
Definition: sparse_set.hpp:725
const_reverse_iterator crend() const
Returns a reverse iterator to the end.
Definition: sparse_set.hpp:557
void swap_elements(const entity_type lhs, const entity_type rhs)
Swaps two entities in a sparse set.
Definition: sparse_set.hpp:799
iterator end() const
Returns an iterator to the end.
Definition: sparse_set.hpp:514
bool empty() const
Checks whether a sparse set is empty.
Definition: sparse_set.hpp:473
iterator const_iterator
Constant random access iterator type.
Definition: sparse_set.hpp:300
entity_type operator[](const size_type pos) const
Returns the entity at specified location, without bounds checking.
Definition: sparse_set.hpp:624
virtual void bind(any)
Forwards variables to mixins, if any.
Definition: sparse_set.hpp:947
basic_sparse_set(const type_info &value, deletion_policy pol=deletion_policy::swap_and_pop, const allocator_type &allocator={})
Constructs an empty container with the given value type, policy and allocator.
Definition: sparse_set.hpp:332
void sort_n(const size_type length, Compare compare, Sort algo=Sort{}, Args &&...args)
Sort the first count elements according to the given comparison function.
Definition: sparse_set.hpp:848
reverse_iterator const_reverse_iterator
Constant reverse iterator type.
Definition: sparse_set.hpp:304
version_type current(const entity_type entt) const
Returns the contained version for an identifier.
Definition: sparse_set.hpp:589
virtual void reserve(const size_type cap)
Increases the capacity of a sparse set.
Definition: sparse_set.hpp:423
iterator emplace(const entity_type entt, const void *value=nullptr)
Assigns an entity to a sparse set.
Definition: sparse_set.hpp:660
const void * get(const entity_type entt) const
Returns the element assigned to an entity, if any.
Definition: sparse_set.hpp:639
void clear()
Clears a sparse set.
Definition: sparse_set.hpp:922
basic_iterator iterator
Random access iterator type.
Definition: sparse_set.hpp:298
typename packed_container_type::size_type size_type
Unsigned integer type.
Definition: sparse_set.hpp:294
size_type size() const
Returns the number of elements in a sparse set.
Definition: sparse_set.hpp:465
virtual void shrink_to_fit()
Requests the removal of unused capacity.
Definition: sparse_set.hpp:437
virtual void swap_and_pop(basic_iterator first, basic_iterator last)
Erases entities from a sparse set.
Definition: sparse_set.hpp:241
iterator find(const entity_type entt) const
Finds an entity.
Definition: sparse_set.hpp:567
typename packed_container_type::const_pointer pointer
Pointer type to contained entities.
Definition: sparse_set.hpp:296
basic_sparse_set(deletion_policy pol, const allocator_type &allocator={})
Constructs an empty container with the given policy and allocator.
Definition: sparse_set.hpp:322
typename entity_traits::version_type version_type
Underlying version type.
Definition: sparse_set.hpp:292
Entity entity_type
Underlying entity identifier.
Definition: sparse_set.hpp:290
iterator insert(It first, It last)
Assigns one or more entities to a sparse set.
Definition: sparse_set.hpp:693
basic_sparse_set(basic_sparse_set &&other, const allocator_type &allocator)
Allocator-extended move constructor.
Definition: sparse_set.hpp:355
size_type extent() const
Returns the extent of a sparse set.
Definition: sparse_set.hpp:451
entity_type at(const size_type pos) const
Returns the entity at specified location, with bounds checking.
Definition: sparse_set.hpp:615
const_iterator begin() const
Returns an iterator to the beginning.
Definition: sparse_set.hpp:494
const_iterator cbegin() const
Returns an iterator to the beginning.
Definition: sparse_set.hpp:500
size_type remove(It first, It last)
Removes entities from a sparse set if they exist.
Definition: sparse_set.hpp:752
basic_sparse_set(basic_sparse_set &&other)
Move constructor.
Definition: sparse_set.hpp:343
const type_info & type() const
Returned value type, if any.
Definition: sparse_set.hpp:942
virtual size_type capacity() const
Returns the number of elements that a sparse set has currently allocated space for.
Definition: sparse_set.hpp:432
internal::sparse_set_iterator< packed_container_type > basic_iterator
Random access iterator type.
Definition: sparse_set.hpp:234
virtual ~basic_sparse_set()
Default destructor.
Definition: sparse_set.hpp:365
bool contains(const entity_type entt) const
Checks if a sparse set contains an entity.
Definition: sparse_set.hpp:576
void respect(const basic_sparse_set &other)
Sort entities according to their order in another sparse set.
Definition: sparse_set.hpp:903
pointer data() const
Direct access to the internal packed array.
Definition: sparse_set.hpp:481
void bump(const entity_type entt)
Bump the version number of an entity.
Definition: sparse_set.hpp:673
constexpr allocator_type get_allocator() const
Returns the associated allocator.
Definition: sparse_set.hpp:403
void sort(Compare compare, Sort algo=Sort{}, Args &&...args)
Sort all elements according to the given comparison function.
Definition: sparse_set.hpp:883
const_reverse_iterator rbegin() const
Returns a reverse iterator to the beginning.
Definition: sparse_set.hpp:533
const_iterator cend() const
Returns an iterator to the end.
Definition: sparse_set.hpp:519
bool remove(const entity_type entt)
Removes an entity from a sparse set if it exists.
Definition: sparse_set.hpp:740
void * get(const entity_type entt)
Returns the element assigned to an entity, if any.
Definition: sparse_set.hpp:644
void compact()
Removes all tombstones from the packed array of a sparse set.
Definition: sparse_set.hpp:763
Allocator allocator_type
Allocator type.
Definition: sparse_set.hpp:288
basic_sparse_set()
Default constructor.
Definition: sparse_set.hpp:307
basic_sparse_set & operator=(basic_sparse_set &&other)
Move assignment operator.
Definition: sparse_set.hpp:374
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator type.
Definition: sparse_set.hpp:302
virtual void in_place_pop(basic_iterator first, basic_iterator last)
Erases entities from a sparse set.
Definition: sparse_set.hpp:258
Entity traits.
Definition: entity.hpp:62
static constexpr auto page_size
Page size, default is ENTT_SPARSE_PAGE.
Definition: entity.hpp:75
typename base_type::entity_type entity_type
Underlying entity type.
Definition: entity.hpp:69
static constexpr entity_type reserved
Reserved identifier.
Definition: entity.hpp:73
static constexpr entity_type to_integral(const value_type value)
Converts an entity to its underlying type.
Definition: entity.hpp:82
static constexpr entity_type to_entity(const value_type value)
Returns the entity part once converted to the underlying type.
Definition: entity.hpp:91
static constexpr value_type combine(const entity_type lhs, const entity_type rhs)
Combines two identifiers in a single one.
Definition: entity.hpp:128
typename base_type::version_type version_type
Underlying version type.
Definition: entity.hpp:71
static constexpr version_type to_version(const value_type value)
Returns the version part once converted to the underlying type.
Definition: entity.hpp:100
EnTT default namespace.
Definition: dense_map.hpp:22
constexpr bool operator==(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
entity
Default entity identifier.
Definition: fwd.hpp:47
constexpr std::size_t fast_mod(const std::size_t value, const std::size_t mod)
Fast module utility function (powers of two only).
Definition: memory.hpp:102
const type_info & type_id()
Returns the type info object associated to a given type.
Definition: type_info.hpp:257
constexpr bool operator<=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
constexpr bool operator>=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
constexpr tombstone_t tombstone
Compile-time constant for tombstone entities.
Definition: entity.hpp:335
constexpr type_list< Type..., Other... > operator+(type_list< Type... >, type_list< Other... >)
Concatenates multiple type lists.
constexpr bool operator<(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
deletion_policy
Sparse set deletion policy.
Definition: sparse_set.hpp:143
@ swap_and_pop
Swap-and-pop deletion policy.
@ in_place
In-place deletion policy.
bool operator!=(const basic_any< Len, Align > &lhs, const basic_any< Len, Align > &rhs)
Checks if two wrappers differ in their content.
Definition: any.hpp:402
constexpr bool operator>(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
Function object to wrap std::sort in a class type.
Definition: algorithm.hpp:21
Implementation specific information about a type.
Definition: type_info.hpp:141