EnTT  3.7.0
Classes | Public Types | Public Member Functions | Protected Member Functions | List of all members
entt::basic_sparse_set< Entity > Class Template Reference

Basic sparse set implementation. More...

#include <sparse_set.hpp>

Inheritance diagram for entt::basic_sparse_set< Entity >:
Inheritance graph
[legend]

Public Types

using entity_type = Entity
 Underlying entity identifier.
 
using size_type = std::size_t
 Unsigned integer type.
 
using iterator = sparse_set_iterator
 Random access iterator type.
 
using reverse_iterator = const entity_type *
 Reverse iterator type.
 

Public Member Functions

 basic_sparse_set ()=default
 Default constructor.
 
 basic_sparse_set (basic_sparse_set &&)=default
 Default move constructor.
 
virtual ~basic_sparse_set ()=default
 Default destructor.
 
basic_sparse_setoperator= (basic_sparse_set &&)=default
 Default move assignment operator. More...
 
void reserve (const size_type cap)
 Increases the capacity of a sparse set. More...
 
size_type capacity () const noexcept
 Returns the number of elements that a sparse set has currently allocated space for. More...
 
void shrink_to_fit ()
 Requests the removal of unused capacity.
 
size_type extent () const noexcept
 Returns the extent of a sparse set. More...
 
size_type size () const noexcept
 Returns the number of elements in a sparse set. More...
 
bool empty () const noexcept
 Checks whether a sparse set is empty. More...
 
const entity_typedata () const noexcept
 Direct access to the internal packed array. More...
 
iterator begin () const noexcept
 Returns an iterator to the beginning. More...
 
iterator end () const noexcept
 Returns an iterator to the end. More...
 
reverse_iterator rbegin () const noexcept
 Returns a reverse iterator to the beginning. More...
 
reverse_iterator rend () const noexcept
 Returns a reverse iterator to the end. More...
 
iterator find (const entity_type entt) const
 Finds an entity. More...
 
bool contains (const entity_type entt) const
 Checks if a sparse set contains an entity. More...
 
size_type index (const entity_type entt) const
 Returns the position of an entity in a sparse set. More...
 
entity_type at (const size_type pos) const
 Returns the entity at specified location, with bounds checking. More...
 
entity_type operator[] (const size_type pos) const
 Returns the entity at specified location, without bounds checking. More...
 
void emplace (const entity_type entt)
 Assigns an entity to a sparse set. More...
 
template<typename It >
void insert (It first, It last)
 Assigns one or more entities to a sparse set. More...
 
void remove (const entity_type entt, void *ud=nullptr)
 Removes an entity from a sparse set. More...
 
template<typename It >
void remove (It first, It last, void *ud=nullptr)
 Removes multiple entities from a pool. More...
 
void swap (const entity_type lhs, const entity_type rhs)
 Swaps two entities in the internal packed array. More...
 
template<typename Compare , typename Sort = std_sort, typename... Args>
void sort_n (const size_type count, Compare compare, Sort algo=Sort{}, Args &&... args)
 Sort the first count elements according to the given comparison function. More...
 
template<typename Compare , typename Sort = std_sort, typename... Args>
void sort (Compare compare, Sort algo=Sort{}, Args &&... args)
 Sort all elements according to the given comparison function. More...
 
void respect (const basic_sparse_set &other)
 Sort entities according to their order in another sparse set. More...
 
void clear (void *ud=nullptr) noexcept
 Clears a sparse set. More...
 

Protected Member Functions

virtual void swap_at (const std::size_t, const std::size_t)
 Swaps two entities in the internal packed array.
 
virtual void swap_and_pop (const std::size_t, void *)
 Attempts to remove an entity from the internal packed array.
 

Detailed Description

template<typename Entity>
class entt::basic_sparse_set< Entity >

Basic sparse set implementation.

Sparse set or packed array or whatever is the name users give it.
Two arrays: an external one and an internal one; a sparse one and a packed one; one used for direct access through contiguous memory, the other one used to get the data through an extra level of indirection.
This is largely used by the registry to offer users the fastest access ever to the components. Views and groups in general are almost entirely designed around sparse sets.

This type of data structure is widely documented in the literature and on the web. This is nothing more than a customized implementation suitable for the purpose of the framework.

Note
Internal data structures arrange elements to maximize performance. There are no guarantees that entities are returned in the insertion order when iterate a sparse set. Do not make assumption on the order in any case.
Template Parameters
EntityA valid entity type (see entt_traits for more details).

Definition at line 43 of file sparse_set.hpp.

Member Function Documentation

◆ at()

template<typename Entity >
entity_type entt::basic_sparse_set< Entity >::at ( const size_type  pos) const
inline

Returns the entity at specified location, with bounds checking.

Parameters
posThe position for which to return the entity.
Returns
The entity at specified location if any, a null entity otherwise.

Definition at line 385 of file sparse_set.hpp.

◆ begin()

template<typename Entity >
iterator entt::basic_sparse_set< Entity >::begin ( ) const
inlinenoexcept

Returns an iterator to the beginning.

The returned iterator points to the first entity of the internal packed array. If the sparse set is empty, the returned iterator will be equal to end().

Returns
An iterator to the first entity of the internal packed array.

Definition at line 297 of file sparse_set.hpp.

◆ capacity()

template<typename Entity >
size_type entt::basic_sparse_set< Entity >::capacity ( ) const
inlinenoexcept

Returns the number of elements that a sparse set has currently allocated space for.

Returns
Capacity of the sparse set.

Definition at line 221 of file sparse_set.hpp.

◆ clear()

template<typename Entity >
void entt::basic_sparse_set< Entity >::clear ( void *  ud = nullptr)
inlinenoexcept

Clears a sparse set.

Parameters
udOptional user data that are forwarded as-is to derived classes.

Definition at line 606 of file sparse_set.hpp.

◆ contains()

template<typename Entity >
bool entt::basic_sparse_set< Entity >::contains ( const entity_type  entt) const
inline

Checks if a sparse set contains an entity.

Parameters
enttA valid entity identifier.
Returns
True if the sparse set contains the entity, false otherwise.

Definition at line 359 of file sparse_set.hpp.

◆ data()

template<typename Entity >
const entity_type* entt::basic_sparse_set< Entity >::data ( ) const
inlinenoexcept

Direct access to the internal packed array.

The returned pointer is such that range [data(), data() + size()) is always a valid range, even if the container is empty.

Note
Entities are in the reverse order as returned by the begin/end iterators.
Returns
A pointer to the internal packed array.

Definition at line 284 of file sparse_set.hpp.

◆ emplace()

template<typename Entity >
void entt::basic_sparse_set< Entity >::emplace ( const entity_type  entt)
inline

Assigns an entity to a sparse set.

Warning
Attempting to assign an entity that already belongs to the sparse set results in undefined behavior.
Parameters
enttA valid entity identifier.

Definition at line 408 of file sparse_set.hpp.

◆ empty()

template<typename Entity >
bool entt::basic_sparse_set< Entity >::empty ( ) const
inlinenoexcept

Checks whether a sparse set is empty.

Returns
True if the sparse set is empty, false otherwise.

Definition at line 268 of file sparse_set.hpp.

◆ end()

template<typename Entity >
iterator entt::basic_sparse_set< Entity >::end ( ) const
inlinenoexcept

Returns an iterator to the end.

The returned iterator points to the element following the last entity in the internal packed array. Attempting to dereference the returned iterator results in undefined behavior.

Returns
An iterator to the element following the last entity of the internal packed array.

Definition at line 312 of file sparse_set.hpp.

◆ extent()

template<typename Entity >
size_type entt::basic_sparse_set< Entity >::extent ( ) const
inlinenoexcept

Returns the extent of a sparse set.

The extent of a sparse set is also the size of the internal sparse array. There is no guarantee that the internal packed array has the same size. Usually the size of the internal sparse array is equal or greater than the one of the internal packed array.

Returns
Extent of the sparse set.

Definition at line 246 of file sparse_set.hpp.

◆ find()

template<typename Entity >
iterator entt::basic_sparse_set< Entity >::find ( const entity_type  entt) const
inline

Finds an entity.

Parameters
enttA valid entity identifier.
Returns
An iterator to the given entity if it's found, past the end iterator otherwise.

Definition at line 350 of file sparse_set.hpp.

◆ index()

template<typename Entity >
size_type entt::basic_sparse_set< Entity >::index ( const entity_type  entt) const
inline

Returns the position of an entity in a sparse set.

Warning
Attempting to get the position of an entity that doesn't belong to the sparse set results in undefined behavior.
Parameters
enttA valid entity identifier.
Returns
The position of the entity in the sparse set.

Definition at line 375 of file sparse_set.hpp.

◆ insert()

template<typename Entity >
template<typename It >
void entt::basic_sparse_set< Entity >::insert ( It  first,
It  last 
)
inline

Assigns one or more entities to a sparse set.

Warning
Attempting to assign an entity that already belongs to the sparse set results in undefined behavior.
Template Parameters
ItType of input iterator.
Parameters
firstAn iterator to the first element of the range of entities.
lastAn iterator past the last element of the range of entities.

Definition at line 426 of file sparse_set.hpp.

◆ operator=()

template<typename Entity >
basic_sparse_set& entt::basic_sparse_set< Entity >::operator= ( basic_sparse_set< Entity > &&  )
default

Default move assignment operator.

Returns
This sparse set.

◆ operator[]()

template<typename Entity >
entity_type entt::basic_sparse_set< Entity >::operator[] ( const size_type  pos) const
inline

Returns the entity at specified location, without bounds checking.

Parameters
posThe position for which to return the entity.
Returns
The entity at specified location.

Definition at line 394 of file sparse_set.hpp.

◆ rbegin()

template<typename Entity >
reverse_iterator entt::basic_sparse_set< Entity >::rbegin ( ) const
inlinenoexcept

Returns a reverse iterator to the beginning.

The returned iterator points to the first entity of the reversed internal packed array. If the sparse set is empty, the returned iterator will be equal to rend().

Returns
An iterator to the first entity of the reversed internal packed array.

Definition at line 326 of file sparse_set.hpp.

◆ remove() [1/2]

template<typename Entity >
void entt::basic_sparse_set< Entity >::remove ( const entity_type  entt,
void *  ud = nullptr 
)
inline

Removes an entity from a sparse set.

Warning
Attempting to remove an entity that doesn't belong to the sparse set results in undefined behavior.
Parameters
enttA valid entity identifier.
udOptional user data that are forwarded as-is to derived classes.

Definition at line 446 of file sparse_set.hpp.

◆ remove() [2/2]

template<typename Entity >
template<typename It >
void entt::basic_sparse_set< Entity >::remove ( It  first,
It  last,
void *  ud = nullptr 
)
inline

Removes multiple entities from a pool.

Template Parameters
ItType of input iterator.
Parameters
firstAn iterator to the first element of the range of entities.
lastAn iterator past the last element of the range of entities.
udOptional user data that are forwarded as-is to derived classes.

Definition at line 471 of file sparse_set.hpp.

◆ rend()

template<typename Entity >
reverse_iterator entt::basic_sparse_set< Entity >::rend ( ) const
inlinenoexcept

Returns a reverse iterator to the end.

The returned iterator points to the element following the last entity in the reversed internal packed array. Attempting to dereference the returned iterator results in undefined behavior.

Returns
An iterator to the element following the last entity of the reversed internal packed array.

Definition at line 340 of file sparse_set.hpp.

◆ reserve()

template<typename Entity >
void entt::basic_sparse_set< Entity >::reserve ( const size_type  cap)
inline

Increases the capacity of a sparse set.

If the new capacity is greater than the current capacity, new storage is allocated, otherwise the method does nothing.

Parameters
capDesired capacity.

Definition at line 212 of file sparse_set.hpp.

◆ respect()

template<typename Entity >
void entt::basic_sparse_set< Entity >::respect ( const basic_sparse_set< Entity > &  other)
inline

Sort entities according to their order in another sparse set.

Entities that are part of both the sparse sets are ordered internally according to the order they have in other. All the other entities goes to the end of the list and there are no guarantees on their order.
In other terms, this function can be used to impose the same order on two sets by using one of them as a master and the other one as a slave.

Iterating the sparse set with a couple of iterators returns elements in the expected order after a call to respect. See begin and end for more details.

Parameters
otherThe sparse sets that imposes the order of the entities.

Definition at line 583 of file sparse_set.hpp.

◆ size()

template<typename Entity >
size_type entt::basic_sparse_set< Entity >::size ( ) const
inlinenoexcept

Returns the number of elements in a sparse set.

The number of elements is also the size of the internal packed array. There is no guarantee that the internal sparse array has the same size. Usually the size of the internal sparse array is equal or greater than the one of the internal packed array.

Returns
Number of elements.

Definition at line 260 of file sparse_set.hpp.

◆ sort()

template<typename Entity >
template<typename Compare , typename Sort = std_sort, typename... Args>
void entt::basic_sparse_set< Entity >::sort ( Compare  compare,
Sort  algo = Sort{},
Args &&...  args 
)
inline

Sort all elements according to the given comparison function.

See also
sort_n
Template Parameters
CompareType of comparison function object.
SortType of sort function object.
ArgsTypes of arguments to forward to the sort function object.
Parameters
compareA valid comparison function object.
algoA valid sort function object.
argsArguments to forward to the sort function object, if any.

Definition at line 564 of file sparse_set.hpp.

◆ sort_n()

template<typename Entity >
template<typename Compare , typename Sort = std_sort, typename... Args>
void entt::basic_sparse_set< Entity >::sort_n ( const size_type  count,
Compare  compare,
Sort  algo = Sort{},
Args &&...  args 
)
inline

Sort the first count elements according to the given comparison function.

The comparison function object must return true if the first element is less than the second one, false otherwise. The signature of the comparison function should be equivalent to the following:

bool(const Entity, const Entity);

Moreover, the comparison function object shall induce a strict weak ordering on the values.

The sort function object must offer a member function template operator() that accepts three arguments:

  • An iterator to the first element of the range to sort.
  • An iterator past the last element of the range to sort.
  • A comparison function to use to compare the elements.
Template Parameters
CompareType of comparison function object.
SortType of sort function object.
ArgsTypes of arguments to forward to the sort function object.
Parameters
countNumber of elements to sort.
compareA valid comparison function object.
algoA valid sort function object.
argsArguments to forward to the sort function object, if any.

Definition at line 529 of file sparse_set.hpp.

◆ swap()

template<typename Entity >
void entt::basic_sparse_set< Entity >::swap ( const entity_type  lhs,
const entity_type  rhs 
)
inline

Swaps two entities in the internal packed array.

For what it's worth, this function affects both the internal sparse array and the internal packed array. Users should not care of that anyway.

Warning
Attempting to swap entities that don't belong to the sparse set results in undefined behavior.
Parameters
lhsA valid entity identifier.
rhsA valid entity identifier.

Definition at line 490 of file sparse_set.hpp.


The documentation for this class was generated from the following files: