Basic sparse set implementation. More...

#include <entt.hpp>

Inheritance diagram for entt::sparse_set< Entity >:

Public Types
using	entity_type = Entity
	Underlying entity identifier. More...

using	size_type = std::size_t
	Unsigned integer type. More...

using	iterator_type = iterator
	Random access iterator type. More...

Public Member Functions
	sparse_set ()=default
	Default constructor. More...

	sparse_set (const sparse_set &other)
	Copy constructor. More...

	sparse_set (sparse_set &&)=default
	Default move constructor. More...

virtual	~sparse_set () ENTT_NOEXCEPT=default
	Default destructor. More...

sparse_set &	operator= (const sparse_set &other)
	Copy assignment operator. More...

sparse_set &	operator= (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 ENTT_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. More...

size_type	extent () const ENTT_NOEXCEPT
	Returns the extent of a sparse set. More...

size_type	size () const ENTT_NOEXCEPT
	Returns the number of elements in a sparse set. More...

bool	empty () const ENTT_NOEXCEPT
	Checks whether a sparse set is empty. More...

const entity_type *	data () const ENTT_NOEXCEPT
	Direct access to the internal packed array. More...

iterator_type	begin () const ENTT_NOEXCEPT
	Returns an iterator to the beginning. More...

iterator_type	end () const ENTT_NOEXCEPT
	Returns an iterator to the end. More...

iterator_type	find (const entity_type entt) const ENTT_NOEXCEPT
	Finds an entity. More...

bool	has (const entity_type entt) const ENTT_NOEXCEPT
	Checks if a sparse set contains an entity. More...

size_type	index (const entity_type entt) const ENTT_NOEXCEPT
	Returns the position of an entity in a sparse set. More...

void	construct (const entity_type entt)
	Assigns an entity to a sparse set. More...

template<typename It >
void	batch (It first, It last)
	Assigns one or more entities to a sparse set. More...

void	destroy (const entity_type entt)
	Removes an entity from a sparse set. More...

virtual void	swap (const entity_type lhs, const entity_type rhs) ENTT_NOEXCEPT
	Swaps two entities in the internal packed array. More...

template<typename Compare , typename Sort = std_sort, typename... Args>
void	sort (iterator_type first, iterator_type last, Compare compare, Sort algo=Sort{}, Args &&... args)
	Sort elements according to the given comparison function. More...

template<typename Apply , typename Compare , typename Sort = std_sort, typename... Args>
void	arrange (iterator_type first, iterator_type last, Apply apply, Compare compare, Sort algo=Sort{}, Args &&... args)
	Sort elements according to the given comparison function. More...

void	respect (const sparse_set &other) ENTT_NOEXCEPT
	Sort entities according to their order in another sparse set. More...

void	reset ()
	Resets a sparse set. More...

Detailed Description

template<typename Entity>
class entt::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: 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.; Internal data structures arrange elements to maximize performance. Because of that, there are no guarantees that elements have the expected order when iterate directly the internal packed array (see data and size member functions for that). Use begin and end instead.

Template Parameters

Entity A valid entity type (see entt_traits for more details).

Member Typedef Documentation

◆ entity_type

template<typename Entity >

using entt::sparse_set< Entity >::entity_type = Entity

Underlying entity identifier.

◆ iterator_type

template<typename Entity >

using entt::sparse_set< Entity >::iterator_type = iterator

Random access iterator type.

◆ size_type

template<typename Entity >

using entt::sparse_set< Entity >::size_type = std::size_t

Unsigned integer type.

Constructor & Destructor Documentation

◆ sparse_set() [1/3]

template<typename Entity >

entt::sparse_set< Entity >::sparse_set ( )

default

Default constructor.

◆ sparse_set() [2/3]

template<typename Entity >

entt::sparse_set< Entity >::sparse_set ( const sparse_set< Entity > & other )

inline

Copy constructor.

Parameters

other The instance to copy from.

◆ sparse_set() [3/3]

template<typename Entity >

entt::sparse_set< Entity >::sparse_set ( sparse_set< Entity > && )

default

Default move constructor.

◆ ~sparse_set()

template<typename Entity >

virtual entt::sparse_set< Entity >::~sparse_set ( )

virtualdefault

Default destructor.

Member Function Documentation

◆ arrange()

template<typename Entity >

template<typename Apply , typename Compare , typename Sort = std_sort, typename... Args>

void entt::sparse_set< Entity >::arrange	(	iterator_type	first,
		iterator_type	last,
		Apply	apply,
		Compare	compare,
		Sort	algo = `Sort{}`,
		Args &&...	args
	)

inline

Sort elements according to the given comparison function.

See also: sort

This function is a slightly slower version of sort that invokes the caller to indicate which entities are swapped.
It's recommended when the caller wants to sort its own data structures to align them with the order induced in the sparse set.

The signature of the callback should be equivalent to the following:

bool(const Entity, const Entity);

Template Parameters

Apply	Type of function object to invoke to notify the caller.
Compare	Type of comparison function object.
Sort	Type of sort function object.
Args	Types of arguments to forward to the sort function object.

Parameters

first	An iterator to the first element of the range to sort.
last	An iterator past the last element of the range to sort.
apply	A valid function object to use as a callback.
compare	A valid comparison function object.
algo	A valid sort function object.
args	Arguments to forward to the sort function object, if any.

◆ batch()

template<typename Entity >

template<typename It >

void entt::sparse_set< Entity >::batch	(	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.
An assertion will abort the execution at runtime in debug mode if the sparse set already contains the given entity.

Template Parameters

It	Type of forward iterator.

Parameters

first	An iterator to the first element of the range of entities.
last	An iterator past the last element of the range of entities.

◆ begin()

template<typename Entity >

iterator_type entt::sparse_set< Entity >::begin ( ) const

inline

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().

Note: Random access iterators stay true to the order imposed by a call to respect.

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

◆ capacity()

template<typename Entity >

size_type entt::sparse_set< Entity >::capacity ( ) const

inline

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

Returns: Capacity of the sparse set.

◆ construct()

template<typename Entity >

void entt::sparse_set< Entity >::construct ( 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.
An assertion will abort the execution at runtime in debug mode if the sparse set already contains the given entity.

Parameters

entt	A valid entity identifier.

◆ data()

template<typename Entity >

const entity_type* entt::sparse_set< Entity >::data ( ) const

inline

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: There are no guarantees on the order, even though respect has been previously invoked. Internal data structures arrange elements to maximize performance. Accessing them directly gives a performance boost but less guarantees. Use begin and end if you want to iterate the sparse set in the expected order.

Returns: A pointer to the internal packed array.

◆ destroy()

template<typename Entity >

void entt::sparse_set< Entity >::destroy ( const entity_type entt )

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.
An assertion will abort the execution at runtime in debug mode if the sparse set doesn't contain the given entity.

Parameters

entt	A valid entity identifier.

◆ empty()

template<typename Entity >

bool entt::sparse_set< Entity >::empty ( ) const

inline

Checks whether a sparse set is empty.

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

◆ end()

template<typename Entity >

iterator_type entt::sparse_set< Entity >::end ( ) const

inline

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.

Note: Random access iterators stay true to the order imposed by a call to respect.

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

◆ extent()

template<typename Entity >

size_type entt::sparse_set< Entity >::extent ( ) const

inline

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.

◆ find()

template<typename Entity >

iterator_type entt::sparse_set< Entity >::find ( const entity_type entt ) const

inline

Finds an entity.

Parameters

entt	A valid entity identifier.

Returns: An iterator to the given entity if it's found, past the end iterator otherwise.

◆ has()

template<typename Entity >

bool entt::sparse_set< Entity >::has ( const entity_type entt ) const

inline

Checks if a sparse set contains an entity.

Parameters

entt	A valid entity identifier.

Returns: True if the sparse set contains the entity, false otherwise.

◆ index()

template<typename Entity >

size_type entt::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.
An assertion will abort the execution at runtime in debug mode if the sparse set doesn't contain the given entity.

Parameters

entt	A valid entity identifier.

Returns: The position of the entity in the sparse set.

◆ operator=() [1/2]

template<typename Entity >

sparse_set& entt::sparse_set< Entity >::operator= ( const sparse_set< Entity > & other )

inline

Copy assignment operator.

Parameters

other The instance to copy from.

Returns: This sparse set.

◆ operator=() [2/2]

template<typename Entity >

sparse_set& entt::sparse_set< Entity >::operator= ( sparse_set< Entity > && )

default

Default move assignment operator.

Returns: This sparse set.

◆ reserve()

template<typename Entity >

void entt::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

cap	Desired capacity.

◆ reset()

template<typename Entity >

void entt::sparse_set< Entity >::reset ( )

inline

Resets a sparse set.

◆ respect()

template<typename Entity >

void entt::sparse_set< Entity >::respect ( const 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.

Note: Attempting to iterate elements using a raw pointer returned by a call to data gives no guarantees on the order, even though respect has been invoked.

Parameters

other The sparse sets that imposes the order of the entities.

◆ shrink_to_fit()

template<typename Entity >

void entt::sparse_set< Entity >::shrink_to_fit ( )

inline

Requests the removal of unused capacity.

◆ size()

template<typename Entity >

size_type entt::sparse_set< Entity >::size ( ) const

inline

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.

◆ sort()

template<typename Entity >

template<typename Compare , typename Sort = std_sort, typename... Args>

void entt::sparse_set< Entity >::sort	(	iterator_type	first,
		iterator_type	last,
		Compare	compare,
		Sort	algo = `Sort{}`,
		Args &&...	args
	)

inline

Sort elements according to the given comparison function.

Sort the elements so that iterating the range with a couple of iterators returns them in the expected order. See begin and end for more details.

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

Note: Attempting to iterate elements using a raw pointer returned by a call to data gives no guarantees on the order, even though sort has been invoked.

Template Parameters

Compare	Type of comparison function object.
Sort	Type of sort function object.
Args	Types of arguments to forward to the sort function object.

Parameters

first	An iterator to the first element of the range to sort.
last	An iterator past the last element of the range to sort.
compare	A valid comparison function object.
algo	A valid sort function object.
args	Arguments to forward to the sort function object, if any.

◆ swap()

template<typename Entity >

virtual void entt::sparse_set< Entity >::swap	(	const entity_type	lhs,
		const entity_type	rhs
	)

inlinevirtual

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.
An assertion will abort the execution at runtime in debug mode if the sparse set doesn't contain the given entities.

Parameters

lhs	A valid entity identifier.
rhs	A valid entity identifier.

Reimplemented in entt::basic_storage< Entity, Type, typename >, entt::basic_storage< Entity, Type >, entt::basic_storage< Entity, Component >, and entt::basic_storage< entity_type, payload_type >.

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

D:/CadworkJobs/SoftwareProjekte/Lexocad/LexoGit/Lexocad/lexocad/Base/include/Base/entt.hpp

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ entity_type

◆ iterator_type

◆ size_type

Constructor & Destructor Documentation

◆ sparse_set() [1/3]

◆ sparse_set() [2/3]

◆ sparse_set() [3/3]

◆ ~sparse_set()

Member Function Documentation

◆ arrange()

◆ batch()

◆ begin()

◆ capacity()

◆ construct()

◆ data()

◆ destroy()

◆ empty()

◆ end()

◆ extent()

◆ find()

◆ has()

◆ index()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ reserve()

◆ reset()

◆ respect()

◆ shrink_to_fit()

◆ size()

◆ sort()

◆ swap()

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