#include <arraymap.h>

Inheritance diagram for ArraySet< T, SORTED, COMPARE, ARRAY >:

[legend]

Detailed Description

template<typename T, Bool SORTED = true, typename COMPARE = DefaultCompare, typename ARRAY = BaseArraySelector<>>
class maxon::ArraySet< T, SORTED, COMPARE, ARRAY >

An ArraySet is an implementation of a set using an underlying array. An element is in the set if it is in the array. ArraySet is based on ArrayMap and takes care of not inserting an element twice in the array. Like ArrayMap, ArraySet may be either sorted or unsorted. For very small sets, unsorted array sets are generally faster. For large sets (exceeding about 100 entries), you should consider using another implementation such as HashSet or BurstTrieSet because especially insertion and erasure become slow with array sets: For a sorted ArraySet, those operations have a time cost of O(N), while searching has a time cost of O(log N).

Of all sets, the ArraySet is the most efficient with respect to memory usage as it really only stores the contained values.

See HashSet for more examples on how to use sets in general.

Template Parameters

T	Type of elements of the set.
SORTED	Use true for a sorted array.
COMPARE	Class to be used to compare the values.
ARRAY	An array selector template to choose the array implementation to use.

See also: ArrayMap; $ref sets

Public Types
using	MapType = ArrayMap< T, UnitType, SORTED, COMPARE, ARRAY >

using	IsArrayMap = std::true_type

using	IsArraySet = std::true_type

using	Iterator = typename Super::KeyIterator

using	ConstIterator = typename Super::ConstKeyIterator

Public Types inherited from SetBase0< COLLECTION, VALUETYPE, SUPER, HASH >
using	SetType = COLLECTION

Public Types inherited from Collection< COLLECTION, VALUETYPE, SUPER >
using	Super = BaseCollection< COLLECTION, SUPER >

using	ValueType = VALUETYPE

Public Types inherited from BaseCollection< COLLECTION, SUPER >
using	IsCollection = std::true_type

using	IsBaseArray = std::false_type

Public Member Functions
	ArraySet ()

	ArraySet (ArraySet &&src)

	MAXON_OPERATOR_MOVE_ASSIGNMENT (ArraySet)

MapType &	GetMap ()

const MapType &	GetMap () const

Bool	Contains (typename ByValueParam< T >::type value) const

ResultMemT< Iterator >	Insert (const T &value, Bool &added=BoolLValue())

ResultMemT< Iterator >	Insert (T &&value, Bool &added=BoolLValue())

ResultRef< const T >	InsertKey (const T &value, Bool &added=BoolLValue())

ResultRef< const T >	InsertKey (T &&value, Bool &added=BoolLValue())

ResultOk< Bool >	Erase (const T &value)

ConstIterator	Begin () const

ConstIterator	End () const

Iterator	Begin ()

Iterator	End ()

Iterator	Erase (const Iterator &it)

const ARRAY::template Type< T > &	GetUnderlyingArray () const

ARRAY::template Type< T > &	GetUnderlyingArray ()

template<typename KEYCOMPARE = COMPARE, typename KEY = K>
Iterator	Find (const KEY &key)

template<typename KEYCOMPARE = COMPARE, typename KEY = K>
ConstIterator	Find (const KEY &key) const

template<typename KEYCOMPARE = COMPARE, typename KEY = K>
Iterator	FindFloor (const KEY &key)

template<typename KEYCOMPARE = COMPARE, typename KEY = K>
ConstIterator	FindFloor (const KEY &key) const

template<typename KEYCOMPARE = COMPARE, typename KEY = K>
Iterator	FindCeiling (const KEY &key)

template<typename KEYCOMPARE = COMPARE, typename KEY = K>
ConstIterator	FindCeiling (const KEY &key) const

Int	GetOperationCountForSearch () const

Public Member Functions inherited from SetBase< ArraySet< T, true, DefaultCompare, BaseArraySelector<> >, T, Protected< ArrayMap< T, UnitType, true, DefaultCompare, BaseArraySelector<> > >, DefaultCompare >
MAXON_ATTRIBUTE_FORCE_INLINE	SetBase (ARGS &&... args)

SetImpl< ArraySet< T, true, DefaultCompare, BaseArraySelector<> > & >	ToSet ()

SetImpl< const ArraySet< T, true, DefaultCompare, BaseArraySelector<> > & >	ToSet () const

MAXON_ATTRIBUTE_FORCE_INLINE	operator SetImpl< ArraySet< T, true, DefaultCompare, BaseArraySelector<> > & > ()

MAXON_ATTRIBUTE_FORCE_INLINE	operator SetImpl< const ArraySet< T, true, DefaultCompare, BaseArraySelector<> > & > () const

Public Member Functions inherited from SetBase0< COLLECTION, VALUETYPE, SUPER, HASH >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	SetBase0 (ARGS &&... args)

MAXON_ATTRIBUTE_FORCE_INLINE ResultRef< const VALUETYPE >	Append (typename ByValueParam< VALUETYPE >::type v)

template<typename COLLECTION2 >
Bool	ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Add (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)

template<typename COLLECTION2 >
Result< void >	SubtractImpl (COLLECTION2 &&other, OverloadRank0)

template<typename COLLECTION2 , typename COMPARE >
Bool	IsEqualImpl (const COLLECTION2 &other, COMPARE &&cmp, OverloadRank0) const

HashInt	GetHashCode () const

UniqueHash	GetUniqueHashCode () const

Public Member Functions inherited from Collection< COLLECTION, VALUETYPE, SUPER >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	Collection (ARGS &&... args)

ResultOk< void >	VariadicAppend ()

template<typename V , typename... VALUES>
Result< void >	VariadicAppend (V &&value, VALUES &&... rest)

	operator ValueReceiver< const VALUETYPE & > ()

	operator ValueReceiver< VALUETYPE && > ()

	operator ValueReceiver< typename std::conditional< STD_IS_REPLACEMENT (scalar, VALUETYPE)

DummyParamType &	type ()

template<typename FN >
Result< Bool >	ForEach (FN &&callback) const

template<typename FN >
Result< Bool >	ForEach (FN &&callback)

template<typename H = COLLECTION>
H::Iterator	Find (typename ByValueParam< VALUETYPE >::type v)

template<typename H = COLLECTION>
H::ConstIterator	Find (typename ByValueParam< VALUETYPE >::type v) const

Int	FindIndex (typename ByValueParam< VALUETYPE >::type v) const

MAXON_ATTRIBUTE_FORCE_INLINE Bool	Contains (typename ByValueParam< VALUETYPE >::type v) const

Public Member Functions inherited from BaseCollection< COLLECTION, SUPER >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	BaseCollection (ARGS &&... args)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type	operator== (const COLLECTION2 &other) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type	operator!= (const COLLECTION2 &other) const

template<typename COMPARE = EqualityCompare, typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value &&!STD_IS_REPLACEMENT(same, typename std::decay< COMPARE >::type, EQUALITY), Bool >::type	IsEqual (const COLLECTION2 &other, COMPARE &&cmp=COMPARE()) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Subtract (COLLECTION2 &&other)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Intersect (const COLLECTION2 &other)

template<typename COLLECTION2 >
Bool	Intersects (const COLLECTION2 &other) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFromImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank0)

template<typename COLLECTION2 >
Result< void >	AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)

template<typename COLLECTION2 >
Result< void >	IntersectImpl (COLLECTION2 &&other, OverloadRank0)

MAXON_ATTRIBUTE_FORCE_INLINE Bool	IsEmpty () const

MAXON_ATTRIBUTE_FORCE_INLINE Bool	IsPopulated () const

String	ToString (const FormatStatement *formatStatement=nullptr) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Bool	ContainsAll (COLLECTION2 &&other) const

template<typename COLLECTION2 >
Bool	ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const

Private Types
using	Super = SetBase< ArraySet< T, SORTED, COMPARE, ARRAY >, T, Protected< MapType >, COMPARE >

Private Member Functions
	MAXON_DISALLOW_COPY_AND_ASSIGN (ArraySet)

Additional Inherited Members
Static Public Member Functions inherited from Collection< COLLECTION, VALUETYPE, SUPER >
static const VALUETYPE &	GetMapKey (const VALUETYPE &key)

Public Attributes inherited from Collection< COLLECTION, VALUETYPE, SUPER >
	VALUETYPE

Static Public Attributes inherited from SetBase0< COLLECTION, VALUETYPE, SUPER, HASH >
static const COLLECTION_KIND	KIND

Member Typedef Documentation

◆ MapType

using MapType = ArrayMap<T, UnitType, SORTED, COMPARE, ARRAY>

◆ Super

using Super = SetBase<ArraySet<T, SORTED, COMPARE, ARRAY>, T, Protected<MapType>, COMPARE>

private

◆ IsArrayMap

using IsArrayMap = std::true_type

◆ IsArraySet

using IsArraySet = std::true_type

◆ Iterator

using Iterator = typename Super::KeyIterator

◆ ConstIterator

using ConstIterator = typename Super::ConstKeyIterator

Constructor & Destructor Documentation

◆ ArraySet() [1/2]

ArraySet ( )

◆ ArraySet() [2/2]

ArraySet ( ArraySet< T, SORTED, COMPARE, ARRAY > && src )

Member Function Documentation

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( ArraySet< T, SORTED, COMPARE, ARRAY > )

private

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT ( ArraySet< T, SORTED, COMPARE, ARRAY > )

◆ GetMap() [1/2]

MapType& GetMap ( )

◆ GetMap() [2/2]

const MapType& GetMap ( ) const

◆ Contains()

Bool Contains ( typename ByValueParam< T >::type value ) const

Checks if this set contains value.

Parameters

[in] value The value to check.

Returns: True if this set contains value.

◆ Insert() [1/2]

ResultMemT<Iterator> Insert	(	const T &	value,
		Bool &	added = `BoolLValue()`
	)

Adds value to this set. If value is already contained in this set, nothing happens, and added is set to false.

Parameters

[in]	value	Value to add to this set.
[out]	added	This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.

Returns: Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ Insert() [2/2]

ResultMemT<Iterator> Insert	(	T &&	value,
		Bool &	added = `BoolLValue()`
	)

Adds value to this set. If value is already contained in this set, nothing happens, and added is set to false.

Parameters

[in]	value	Value to add to this set. When a new element has to be added, `value` will be moved into the new element.
[out]	added	This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.

Returns: Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ InsertKey() [1/2]

ResultRef<const T> InsertKey	(	const T &	value,
		Bool &	added = `BoolLValue()`
	)

Adds value to this set. If value is already contained in this set, nothing happens, and added is set to false.

Parameters

[in]	value	Value to add to this set.
[out]	added	This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.

Returns: Pointer to the value in the set, or nullptr if the element had to be added, but the allocation failed.

◆ InsertKey() [2/2]

ResultRef<const T> InsertKey	(	T &&	value,
		Bool &	added = `BoolLValue()`
	)

Adds value to this set. If value is already contained in this set, nothing happens, and added is set to false.

Parameters

[in]	value	Value to add to this set. When a new element has to be added, `value` will be moved into the new element.
[out]	added	This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.

Returns: Pointer to the value in the set, or nullptr if the element had to be added, but the allocation failed.

◆ Erase() [1/2]

ResultOk<Bool> Erase ( const T & value )

Remove value from this set. If value isn't contained in this set, nothing happens.

Parameters

[in] value Value to remove from this set.

Returns: True if an entry was found and removed for value, otherwise false.

◆ Begin() [1/2]

ConstIterator Begin ( ) const

◆ End() [1/2]

ConstIterator End ( ) const

◆ Begin() [2/2]

Iterator Begin ( )

◆ End() [2/2]

Iterator End ( )

◆ Erase() [2/2]

Iterator Erase ( const Iterator & it )

◆ GetUnderlyingArray() [1/2]

const ARRAY::template Type<T>& GetUnderlyingArray ( ) const

◆ GetUnderlyingArray() [2/2]

ARRAY::template Type<T>& GetUnderlyingArray ( )

◆ Find() [1/2]

Iterator Find	(	typename KEYCOMPARE	= `COMPARE`,
		typename KEY	= `K`
	)

Finds the entry for the given key in this map.

Parameters

[in] key Key to search for.

Returns: Iterator pointing to the entry with the given key, or an invalid iterator if this doesn't exist.

◆ Find() [2/2]

ConstIterator Find	(	typename KEYCOMPARE	= `COMPARE`,
		typename KEY	= `K`
	)

Finds the entry for the given key in this map.

Parameters

[in] key Key to search for.

Returns: Iterator pointing to the entry with the given key, or an invalid iterator if this doesn't exist.

◆ FindFloor() [1/2]

Iterator FindFloor	(	typename KEYCOMPARE	= `COMPARE`,
		typename KEY	= `K`
	)

Finds the entry with the greatest key less than or equal to the given key. If no such entry exists, the returned iterator will be invalid (its operator Bool will return false). This function is only supported by sorted array maps.

Parameters

[in] key Key to search for.

Returns: Iterator pointing to the entry with greatest key less than or equal to the given key, or an invalid iterator if this doesn't exist.

◆ FindFloor() [2/2]

ConstIterator FindFloor	(	typename KEYCOMPARE	= `COMPARE`,
		typename KEY	= `K`
	)

Finds the entry with the greatest key less than or equal to the given key. If no such entry exists, the returned iterator will be invalid (its operator Bool will return false). This function is only supported by sorted array maps.

Parameters

[in] key Key to search for.

Returns: Iterator pointing to the entry with greatest key less than or equal to the given key, or an invalid iterator if this doesn't exist.

◆ FindCeiling() [1/2]

Iterator FindCeiling	(	typename KEYCOMPARE	= `COMPARE`,
		typename KEY	= `K`
	)

Finds the entry with the smallest key greater than or equal to the given key. If no such entry exists, the returned iterator will be invalid (its operator Bool will return false). This function is only supported by sorted array maps.

Parameters

[in] key Key to search for.

Returns: Iterator pointing to the entry with smallest key greater than or equal to the given key, or an invalid iterator if this doesn't exist.

◆ FindCeiling() [2/2]

ConstIterator FindCeiling	(	typename KEYCOMPARE	= `COMPARE`,
		typename KEY	= `K`
	)

Finds the entry with the smallest key greater than or equal to the given key. If no such entry exists, the returned iterator will be invalid (its operator Bool will return false). This function is only supported by sorted array maps.

Parameters

[in] key Key to search for.

Returns: Iterator pointing to the entry with smallest key greater than or equal to the given key, or an invalid iterator if this doesn't exist.

◆ GetOperationCountForSearch()

Int GetOperationCountForSearch

Returns an estimate of the number of operations needed to locate a given key in this map. This is used when two collections are compared: The iteration goes over the collection which would require more operations for search, and each entry is searched in the other collection.

Returns: Estimate for the number of operations.

Detailed Description

template<typename T, Bool SORTED = true, typename COMPARE = DefaultCompare, typename ARRAY = BaseArraySelector<>> class maxon::ArraySet< T, SORTED, COMPARE, ARRAY >

Public Types

Public Member Functions

Private Types

Private Member Functions

Additional Inherited Members

Member Typedef Documentation

◆ MapType

◆ Super

◆ IsArrayMap

◆ IsArraySet

◆ Iterator

◆ ConstIterator

Constructor & Destructor Documentation

◆ ArraySet() [1/2]

◆ ArraySet() [2/2]

Member Function Documentation

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

◆ GetMap() [1/2]

◆ GetMap() [2/2]

◆ Contains()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ InsertKey() [1/2]

◆ InsertKey() [2/2]

◆ Erase() [1/2]

◆ Begin() [1/2]

◆ End() [1/2]

◆ Begin() [2/2]

◆ End() [2/2]

◆ Erase() [2/2]

◆ GetUnderlyingArray() [1/2]

◆ GetUnderlyingArray() [2/2]

◆ Find() [1/2]

◆ Find() [2/2]

◆ FindFloor() [1/2]

◆ FindFloor() [2/2]

◆ FindCeiling() [1/2]

◆ FindCeiling() [2/2]

◆ GetOperationCountForSearch()

template<typename T, Bool SORTED = true, typename COMPARE = DefaultCompare, typename ARRAY = BaseArraySelector<>>
class maxon::ArraySet< T, SORTED, COMPARE, ARRAY >