HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD > Class Template Reference

#include <hybridmap.h>

Inheritance diagram for HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >:

Detailed Description

template<typename K, typename V, typename SMALL, typename LARGE, Int THRESHOLD, Int REVERSE_THRESHOLD>
class maxon::HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >

A HybridMap allows to take advantage of two different map implementations. For example, in a typical setting an ArrayMap may perform better with a low number of entries, while a BurstTrieMap gets better when the number of entries increases. If you cannot predict that the number of entries will always be small (to use an ArrayMap) or large (to use a BurstTrieMap), you can use the HybridMap which automatically switches between two implementations based on the number of entries:

HybridMap<UInt, String, ArrayMapSelector<>, BurstTrieMapSelector<>, 64, 16> map;

See HashMap for more examples on how to use maps in general.

Template Parameters
KType of keys.
VType of values.
SMALLA map selector template to choose the map implementation to use for a small number of entries.
LARGEA map selector template to choose the map implementation to use for a large number of entries.
THRESHOLDWhen the number of entries reaches THRESHOLD, HybridMap switches to the LARGE implementation.
REVERSE_THRESHOLDWhen the number of entries falls below REVERSE_THRESHOLD, HybridMap switches back to the SMALL implementation. If this is negative, this will never happen.
See also
$ref maps

Classes

class  EntryIteratorBase
 
class  IteratorBase
 
class  IteratorTemplate
 
class  KeyIteratorBase
 
class  NonConstIteratorBase
 
class  ValueIteratorBase
 

Public Types

using SmallType = typename SMALL::template Type< K, V >
 
using LargeType = typename LARGE::template Type< K, V >
 
using IsHybridMap = std::true_type
 
using Iterator = IteratorTemplate< false, EntryIteratorBase >
 
using ConstIterator = IteratorTemplate< true, EntryIteratorBase >
 
using KeyIterator = IteratorTemplate< false, KeyIteratorBase >
 
using ConstKeyIterator = IteratorTemplate< true, KeyIteratorBase >
 
using ValueIterator = IteratorTemplate< false, ValueIteratorBase >
 
using ConstValueIterator = IteratorTemplate< true, ValueIteratorBase >
 
- Public Types inherited from MapBase0< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, K, V, EmptyClass, DefaultCompare >
using MapType = HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >
 
using Super = BaseCollection< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, EmptyClass >
 
using KeyType = K
 
using ValueType = V
 
- Public Types inherited from BaseCollection< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, EmptyClass >
using IsCollection = std::true_type
 

Public Member Functions

Iterator Begin ()
 
Iterator End ()
 
ConstIterator Begin () const
 
ConstIterator End () const
 
KeyIterator GetKeys ()
 
ConstKeyIterator GetKeys () const
 
ValueIterator GetValues ()
 
ConstValueIterator GetValues () const
 
 HybridMap ()
 
 ~HybridMap ()
 
 HybridMap (HybridMap &&src)
 
 MAXON_OPERATOR_MOVE_ASSIGNMENT (HybridMap)
 
template<typename MAP >
Result< void > CopyFromImpl (MAP &&src, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank0)
 
template<typename MAP >
SFINAEHelper< Result< void >, typename std::remove_reference< MAP >::type::IsHybridMap >::type CopyFromImpl (MAP &&src, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank1)
 
void Flush ()
 
void Reset ()
 
Int GetCount () const
 
Int GetOperationCountForSearch () const
 
Int GetMemorySize () const
 
ResultMem SetCapacityHint (Int capacity, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
ResultRef< V > InsertKey (const K &key, Bool &created=BoolLValue())
 
ResultRef< V > InsertKey (K &&key, Bool &created=BoolLValue())
 
ResultMemT< IteratorInsertEntry (const K &key, Bool &created=BoolLValue())
 
ResultMemT< IteratorInsertEntry (K &&key, Bool &created=BoolLValue())
 
ResultMemT< IteratorInsert (const K &key, const V &value, Bool &created=BoolLValue())
 
ResultMemT< IteratorInsert (K &&key, const V &value, Bool &created=BoolLValue())
 
ResultMemT< IteratorInsert (const K &key, V &&value, Bool &created=BoolLValue())
 
ResultMemT< IteratorInsert (K &&key, V &&value, Bool &created=BoolLValue())
 
const V * FindValue (const K &key) const
 
V * FindValue (const K &key)
 
Iterator Find (const K &key)
 
ConstIterator Find (const K &key) const
 
Iterator FindFloor (const K &key)
 
ConstIterator FindFloor (const K &key) const
 
Result< BoolErase (const K &key)
 
template<template< Bool > class SUPER>
IteratorTemplate< false, SUPER > Erase (const IteratorTemplate< false, SUPER > &position)
 
Result< void > UseLargeMap ()
 
Result< void > UseSmallMap ()
 
- Public Member Functions inherited from MapBase< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, K, V, EmptyClass, DefaultCompare >
MAXON_ATTRIBUTE_FORCE_INLINE MapBase (ARGS &&... args)
 
MapImpl< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD > &> ToMap ()
 
MapImpl< const HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD > &> ToMap () const
 
MAXON_ATTRIBUTE_FORCE_INLINE operator MapImpl< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD > &> ()
 
MAXON_ATTRIBUTE_FORCE_INLINE operator MapImpl< const HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD > &> () const
 
- Public Member Functions inherited from MapBase0< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, K, V, EmptyClass, DefaultCompare >
MAXON_ATTRIBUTE_FORCE_INLINE MapBase0 (ARGS &&... args)
 
MAXON_ATTRIBUTE_FORCE_INLINE Bool Contains (typename ByValueParam< K >::type key) const
 
MAXON_ATTRIBUTE_FORCE_INLINE SFINAEHelper< Bool, typename PAIR::KeyType >::type Contains (const PAIR &pair) const
 
ResultRef< V > Append (const K &key)
 
SFINAEHelper< ResultRef< V >, typename PAIR::KeyType >::type Append (const PAIR &pair)
 
Result< void > Add (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
Result< void > AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
Result< void > AppendAllInverse (COLLECTION2 &&other)
 
Bool ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const
 
Result< void > SubtractImpl (COLLECTION2 &&other, OverloadRank0)
 
Bool IsEqualImpl (const COLLECTION2 &other, COMPARE &&cmp, OverloadRank0) const
 
UInt GetHashCode () const
 
- Public Member Functions inherited from BaseCollection< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, EmptyClass >
MAXON_ATTRIBUTE_FORCE_INLINE BaseCollection (ARGS &&... args)
 
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type operator== (const COLLECTION2 &other) const
 
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type operator!= (const COLLECTION2 &other) const
 
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value &&!std::is_same< typename std::decay< COMPARE >::type, EQUALITY >::value, Bool >::type IsEqual (const COLLECTION2 &other, COMPARE &&cmp=COMPARE()) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > Subtract (COLLECTION2 &&other)
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > Intersect (const COLLECTION2 &other)
 
Bool Intersects (const COLLECTION2 &other) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > CopyFromImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank0)
 
Result< void > AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)
 
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) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Bool ContainsAll (COLLECTION2 &&other) const
 
Bool ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const
 

Protected Member Functions

SmallTypeGetSmall ()
 
LargeTypeGetLarge ()
 
const SmallTypeGetSmall () const
 
const LargeTypeGetLarge () const
 

Protected Attributes

Bool _small
 
std::aligned_union2< 0, SmallType, LargeType >::type _union [1]
 

Private Member Functions

 MAXON_DISALLOW_COPY_AND_ASSIGN (HybridMap)
 

Additional Inherited Members

- Static Public Member Functions inherited from MapBase0< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, K, V, EmptyClass, DefaultCompare >
static const K & GetMapKey (const K &key)
 
static const K & GetMapKey (const PAIR &pair)
 
- Static Public Attributes inherited from MapBase0< HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >, K, V, EmptyClass, DefaultCompare >
static const COLLECTION_KIND KIND
 

Member Typedef Documentation

◆ SmallType

using SmallType = typename SMALL::template Type<K, V>

◆ LargeType

using LargeType = typename LARGE::template Type<K, V>

◆ IsHybridMap

using IsHybridMap = std::true_type

◆ Iterator

◆ ConstIterator

◆ KeyIterator

◆ ConstKeyIterator

◆ ValueIterator

◆ ConstValueIterator

Constructor & Destructor Documentation

◆ HybridMap() [1/2]

HybridMap ( )

◆ ~HybridMap()

~HybridMap ( )

◆ HybridMap() [2/2]

HybridMap ( HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD > &&  src)

Member Function Documentation

◆ Begin() [1/2]

Iterator Begin ( )

Returns an iterator pointing to the first entry of this map.

Returns
Iterator for this map pointing to the first element.

◆ End() [1/2]

Iterator End ( )

Returns an iterator pointing just behind the last entry of this map.

Returns
Iterator for this map pointing behind the last element.

◆ Begin() [2/2]

ConstIterator Begin ( ) const

Returns an iterator pointing to the first entry of this map.

Returns
Iterator for this map pointing to the first element.

◆ End() [2/2]

ConstIterator End ( ) const

Returns an iterator pointing just behind the last entry of this map.

Returns
Iterator for this map pointing behind the last element.

◆ GetKeys() [1/2]

KeyIterator GetKeys ( )

Returns a foreach iterator to iterate over all keys of this map.

Returns
Foreach iterator over all keys.

◆ GetKeys() [2/2]

ConstKeyIterator GetKeys ( ) const

Returns a foreach iterator to iterate over all keys of this map.

Returns
Foreach iterator over all keys.

◆ GetValues() [1/2]

ValueIterator GetValues ( )

Returns a foreach iterator to iterate over all values of this map.

Returns
Foreach iterator over all values.

◆ GetValues() [2/2]

ConstValueIterator GetValues ( ) const

Returns a foreach iterator to iterate over all values of this map.

Returns
Foreach iterator over all values.

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT ( HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >  )

◆ CopyFromImpl() [1/2]

Result<void> CopyFromImpl ( MAP &&  src,
COLLECTION_RESIZE_FLAGS  resizeFlags,
OverloadRank0   
)

◆ CopyFromImpl() [2/2]

SFINAEHelper<Result<void>, typename std::remove_reference<MAP>::type::IsHybridMap>::type CopyFromImpl ( MAP &&  src,
COLLECTION_RESIZE_FLAGS  resizeFlags,
OverloadRank1   
)

◆ Flush()

void Flush ( void  )

Flushes the map so that it is empty afterwards. Depending on the underlying implementations, memory may still be held for re-use. If REVERSE_THRESHOLD is non-negative, Flush() will also switch back to the SMALL implementation.

◆ Reset()

void Reset ( void  )

Resets the map. This destructs all entries and frees any memory held by the map. The map will also switch to the SMALL implementation if necessary, so it will be in a state as if it had been newly constructed.

◆ GetCount()

Int GetCount ( void  ) const

Returns the number of entries in this map.

Returns
Number of entries.

◆ GetOperationCountForSearch()

Int GetOperationCountForSearch ( ) const

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.

◆ GetMemorySize()

Int GetMemorySize ( void  ) const

Returns the memory usage of this map.

Returns
Memory size in bytes.

◆ SetCapacityHint()

Increases the internal capacity of the map so that it is prepared to hold at least the given number of elements. This is forwarded to the currently used underlying map implementation.

Parameters
[in]capacityThe desired capacity.
[in]resizeFlagsIf ON_GROW_FIT_TO_SIZE is set, the collection will use only as much memory as needed to hold the data.
Returns
False if allocation failed.

◆ InsertKey() [1/2]

ResultRef<V> InsertKey ( const K &  key,
Bool created = BoolLValue() 
)

Finds the value associated with the given key, or creates a corresponding entry if it doesn't exist yet. The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).

Parameters
[in]keyKey of the value to find or create.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Pointer to value for the given key, or nullptr if an entry didn't exist and allocation of a new entry failed.

◆ InsertKey() [2/2]

ResultRef<V> InsertKey ( K &&  key,
Bool created = BoolLValue() 
)

Finds the value associated with the given key, or creates a corresponding entry if it doesn't exist yet. The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).

Parameters
[in]keyKey of the value to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Pointer to value for the given key, or nullptr if an entry didn't exist and allocation of a new entry failed.

◆ InsertEntry() [1/2]

ResultMemT<Iterator> InsertEntry ( const K &  key,
Bool created = BoolLValue() 
)

Finds the entry with the given key, or creates such an entry if it doesn't exist yet, and returns an iterator pointing to the entry. The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).

Parameters
[in]keyKey of the entry to find or create.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ InsertEntry() [2/2]

ResultMemT<Iterator> InsertEntry ( K &&  key,
Bool created = BoolLValue() 
)

Finds the entry with the given key, or creates such an entry if it doesn't exist yet, and returns an iterator pointing to the entry. The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).

Parameters
[in]keyKey of the entry to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ Insert() [1/4]

ResultMemT<Iterator> Insert ( const K &  key,
const V &  value,
Bool created = BoolLValue() 
)

Finds the entry with the given key, or creates such an entry if it doesn't exist yet, and returns an iterator pointing to the entry. The value of the entry will be set to value in any case.

Parameters
[in]keyKey of the entry to find or create.
[in]valueThis will be copied to the value of the entry.
[out]createdThis will be set to true if a new entry has been created 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/4]

ResultMemT<Iterator> Insert ( K &&  key,
const V &  value,
Bool created = BoolLValue() 
)

Finds the entry with the given key, or creates such an entry if it doesn't exist yet, and returns an iterator pointing to the entry. The value of the entry will be set to value in any case.

Parameters
[in]keyKey of the entry to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
[in]valueThis will be copied to the value of the entry.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ Insert() [3/4]

ResultMemT<Iterator> Insert ( const K &  key,
V &&  value,
Bool created = BoolLValue() 
)

Finds the entry with the given key, or creates such an entry if it doesn't exist yet, and returns an iterator pointing to the entry. The value of the entry will be set to value in any case.

Parameters
[in]keyKey of the entry to find or create.
[in]valueThis will be moved to the value of the entry.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ Insert() [4/4]

ResultMemT<Iterator> Insert ( K &&  key,
V &&  value,
Bool created = BoolLValue() 
)

Finds the entry with the given key, or creates such an entry if it doesn't exist yet, and returns an iterator pointing to the entry. The value of the entry will be set to value in any case.

Parameters
[in]keyKey of the entry to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
[in]valueThis will be moved to the value of the entry.
[out]createdThis will be set to true if a new entry has been created successfully, otherwise it will be set to false.
Returns
Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

◆ FindValue() [1/2]

const V* FindValue ( const K &  key) const

Finds the value associated with the given key in this map.

Parameters
[in]keyKey to search for.
Returns
Pointer to value for the given key, or nullptr if no entry exists for the key.

◆ FindValue() [2/2]

V* FindValue ( const K &  key)

Finds the value associated with the given key in this map.

Parameters
[in]keyKey to search for.
Returns
Pointer to value for the given key, or nullptr if no entry exists for the key.

◆ Find() [1/2]

Iterator Find ( const K &  key)

Finds the entry for the given key in this map.

Parameters
[in]keyKey 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 ( const K &  key) const

Finds the entry for the given key in this map.

Parameters
[in]keyKey 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 ( const K &  key)

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 if both underlying implementations support it.

Parameters
[in]keyKey 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 ( const K &  key) const

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 if both underlying implementations support it.

Parameters
[in]keyKey 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.

◆ Erase() [1/2]

Result<Bool> Erase ( const K &  key)

Removes an entry with the given key from this map (if possible).

Parameters
[in]keyKey of the map entry to be be removed.
Returns
True if an entry was found and removed for #key, otherwise false or an error if a memory allocation failed.

◆ Erase() [2/2]

IteratorTemplate<false, SUPER> Erase ( const IteratorTemplate< false, SUPER > &  position)

Removes the element at position from this map. The returned iterator will point to the element behind the last removed element.

Parameters
[in]positionIterator pointing to the element to be removed.
Returns
Iterator pointing to the element behind the removed element.

◆ UseLargeMap()

Result<void> UseLargeMap ( )

Switches to the LARGE implementation.

Returns
False if some memory allocation failed. In this case the map content may be invalid.

◆ UseSmallMap()

Result<void> UseSmallMap ( )

Switches to the SMALL implementation.

Returns
False if some memory allocation failed. In this case the map content may be invalid.

◆ GetSmall() [1/2]

SmallType& GetSmall ( )
protected

◆ GetLarge() [1/2]

LargeType& GetLarge ( )
protected

◆ GetSmall() [2/2]

const SmallType& GetSmall ( ) const
protected

◆ GetLarge() [2/2]

const LargeType& GetLarge ( ) const
protected

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( HybridMap< K, V, SMALL, LARGE, THRESHOLD, REVERSE_THRESHOLD >  )
private

Member Data Documentation

◆ _small

Bool _small
protected

◆ _union

std::aligned_union2<0, SmallType, LargeType>::type _union[1]
protected