#include <bursttriemap.h>

Inheritance diagram for BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >:

[legend]

Detailed Description

template<typename K, typename V, Int GROUP_BITS = 4, Int BUCKET_SIZE = 16, BURSTTRIE_SORT SORT = BURSTTRIE_SORT::LINEAR_SEARCH, template< typename, typename > class POOL = PointerBurstTriePool>
class maxon::BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >

A BurstTrieMap maps unsigned integral keys to values using three levels:

At first, keys are divided based on their number of leading zero bits.
Then, a tree is traversed using groups of GROUP_BITS bits as indices into child nodes.
Finally, a leaf node contains a small array-map-like map of at most BUCKET_SIZE entries. When a full leaf node (BUCKET_SIZE entries) needs to get a further entry, it is split into an inner node with children. Likewise, if after erasure an inner node has less than two-thirds of BUCKET_SIZE key-value-pairs in its descendants, those pairs will be combined to a single leaf node which then replaces the inner node and its descendants.

Performance characteristics: Like an ArrayMap, a BurstTrieMap allows an iteration in the order of the keys. But it performs much better than an ArrayMap when the number of entries gets large (say, more than 100): The number of inner nodes to visit is bounded by the maximum bit length of a key, so operations like insertion, erasure or searching are bounded by a constant time cost, too: O(1).

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

Template Parameters

K	Type of keys. This must be an unsigned integral type.
V	Type of values.
GROUP_BITS	Number of bits which shall be grouped to form an index into the children array of an inner node. This shouldn't exceed 4.
BUCKET_SIZE	Maximum size of a bucket of a leaf node. Reasonable values are between 4 and 40.
SORT	Mode for sorting of the buckets.
POOL	Memory pool for the nodes.

See also: $ref maps

Classes
class	EntryIteratorBase

class	IteratorBase

class	IteratorTemplate

class	KeyIteratorBase

class	NonConstIteratorBase

class	ValueIteratorBase

Public Types
using	IsBurstTrieMap = std::true_type

using	Bucket = BurstTrieBucket< K, V, BUCKET_SIZE >

using	Node = BurstTrieNode< GROUP_BITS, typename POOL< Int, Int >::Index >

using	Pool = POOL< Node, Bucket >

using	Index = typename Pool::Index

using	Super = MapBase< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, K, V, Pool, DefaultCompare >

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< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, K, V, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > >, DefaultCompare >
using	MapType = BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >

using	Super = BaseCollection< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > > >

using	KeyType = K

using	ValueType = V

Public Types inherited from BaseCollection< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > > >
using	IsCollection = std::true_type

Public Member Functions
	BurstTrieMap ()

	BurstTrieMap (Pool &&a)

	BurstTrieMap (const Pool &a)

	BurstTrieMap (BurstTrieMap &&src)

	MAXON_OPERATOR_MOVE_ASSIGNMENT (BurstTrieMap)

	~BurstTrieMap ()

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

void	Reset ()

void	Flush ()

ResultMem	SetCapacityHint (Int, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

Int	GetCount () const

Int	GetOperationCountForSearch () const

Int	GetDepth () const

Int	GetMemorySize () const

Iterator	Begin ()

Iterator	End ()

ConstIterator	Begin () const

ConstIterator	End () const

KeyIterator	GetKeys ()

ConstKeyIterator	GetKeys () const

ValueIterator	GetValues ()

ConstValueIterator	GetValues () const

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

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

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

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

const V *	FindValue (K key) const

V *	FindValue (K key)

Iterator	Find (K key)

ConstIterator	Find (K key) const

Iterator	FindFloor (K key)

ConstIterator	FindFloor (K key) const

ResultOk< Bool >	Erase (K key)

template<template< Bool > class SUPER>
MAXON_WARN_UNUSED IteratorTemplate< false, SUPER >	Erase (const IteratorTemplate< false, SUPER > &position, Int eraseCnt=1)

Public Member Functions inherited from MapBase< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, K, V, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > >, DefaultCompare >
MAXON_ATTRIBUTE_FORCE_INLINE	MapBase (ARGS &&... args)

MapImpl< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > & >	ToMap ()

MapImpl< const BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > & >	ToMap () const

MAXON_ATTRIBUTE_FORCE_INLINE	operator MapImpl< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > & > ()

MAXON_ATTRIBUTE_FORCE_INLINE	operator MapImpl< const BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > & > () const

Public Member Functions inherited from MapBase0< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, K, V, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > >, 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< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > > >
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

Static Public Attributes
static const Int	GROUP_SIZE

static const Int	GROUP_MASK

static const Int	MAX_LEN

Static Public Attributes inherited from MapBase0< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, K, V, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > >, DefaultCompare >
static const COLLECTION_KIND	KIND

Private Member Functions
	MAXON_DISALLOW_COPY_AND_ASSIGN (BurstTrieMap)

void	ClearRoots ()

Int	GetDepthImpl (Index idx) const

Int	GetMemorySizeImpl (Index idx) const

void	DestructNodes (Index idx)

Result< void >	CopyNodes (Index &dest, const BurstTrieMap &srcMap, Index src)

Private Attributes
friend	Pool

Index	_roots [MAX_LEN+1]

Int	_size

Friends
class	BurstTrieMapUtils

Additional Inherited Members
Static Public Member Functions inherited from MapBase0< BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, K, V, POOL< BurstTrieNode< GROUP_BITS, POOL< Int, Int >::Index >, BurstTrieBucket< K, V, BUCKET_SIZE > >, DefaultCompare >
static const K &	GetMapKey (const K &key)

static const K &	GetMapKey (const PAIR &pair)

Member Typedef Documentation

◆ IsBurstTrieMap

using IsBurstTrieMap = std::true_type

◆ Bucket

using Bucket = BurstTrieBucket<K, V, BUCKET_SIZE>

◆ Node

using Node = BurstTrieNode<GROUP_BITS, typename POOL<Int, Int>::Index>

◆ Pool

using Pool = POOL<Node, Bucket>

◆ Index

using Index = typename Pool::Index

◆ Super

using Super = MapBase<BurstTrieMap<K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL>, K, V, Pool, DefaultCompare>

◆ Iterator

using Iterator = IteratorTemplate<false, EntryIteratorBase>

◆ ConstIterator

using ConstIterator = IteratorTemplate<true, EntryIteratorBase>

◆ KeyIterator

using KeyIterator = IteratorTemplate<false, KeyIteratorBase>

◆ ConstKeyIterator

using ConstKeyIterator = IteratorTemplate<true, KeyIteratorBase>

◆ ValueIterator

using ValueIterator = IteratorTemplate<false, ValueIteratorBase>

◆ ConstValueIterator

using ConstValueIterator = IteratorTemplate<true, ValueIteratorBase>

Constructor & Destructor Documentation

◆ BurstTrieMap() [1/4]

BurstTrieMap ( )

◆ BurstTrieMap() [2/4]

BurstTrieMap ( Pool && a )

explicit

◆ BurstTrieMap() [3/4]

BurstTrieMap ( const Pool & a )

explicit

◆ BurstTrieMap() [4/4]

BurstTrieMap ( BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > && src )

◆ ~BurstTrieMap()

~BurstTrieMap ( )

Member Function Documentation

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT ( BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > )

◆ CopyFromImpl()

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

◆ Reset()

void Reset ( void )

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

◆ Flush()

void Flush ( void )

Flushes the map. For a BurstTrieMap, this does the same as Reset(), namely it destructs all entries and frees any memory held by the map.

◆ SetCapacityHint()

ResultMem SetCapacityHint	(	Int	,
		COLLECTION_RESIZE_FLAGS	resizeFlags = `COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY`
	)

Does nothing for a BurstTrieMap.

Returns: Always true.

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

◆ GetDepth()

Int GetDepth ( ) const

Returns the maximum depth of this trie.

Returns: Maximum trie depth.

◆ GetMemorySize()

Int GetMemorySize ( void ) const

Returns the memory usage of this map.

Returns: Memory size in bytes.

◆ Begin() [1/2]

Iterator Begin ( )

Returns an iterator pointing to the first entry of this map. Unless the sorting mode is BURSTTRIE_SORT::NONE, the iteration order corresponds to the order of the keys.

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. Unless the sorting mode is BURSTTRIE_SORT::NONE, the iteration order corresponds to the order of the keys.

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. Unless the sorting mode is BURSTTRIE_SORT::NONE, the iteration order corresponds to the order of the keys.

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. Unless the sorting mode is BURSTTRIE_SORT::NONE, the iteration order corresponds to the order of the keys.

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. Unless the sorting mode is BURSTTRIE_SORT::NONE, this will yield all keys in ascending order.

Returns: Foreach iterator over all keys.

◆ GetKeys() [2/2]

ConstKeyIterator GetKeys ( ) const

Returns a foreach iterator to iterate over all keys of this map. Unless the sorting mode is BURSTTRIE_SORT::NONE, this will yield all keys in ascending order.

Returns: Foreach iterator over all keys.

◆ GetValues() [1/2]

ValueIterator GetValues ( )

Returns a foreach iterator to iterate over all values of this map. Unless the sorting mode is BURSTTRIE_SORT::NONE, this will yield all values in ascending order of the corresponding keys.

Returns: Foreach iterator over all values.

◆ GetValues() [2/2]

ConstValueIterator GetValues ( ) const

Returns a foreach iterator to iterate over all values of this map. Unless the sorting mode is BURSTTRIE_SORT::NONE, this will yield all values in ascending order of the corresponding keys.

Returns: Foreach iterator over all values.

◆ InsertEntry()

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]	key	Key of the entry to find or create.
[out]	created	This 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/2]

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, Then the value of the entry is set to the given value, whether the entry existed before or not.

Parameters

[in]	key	Key of the value to find or create.
[in]	value	Value to which the key shall map.
[out]	created	This 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/2]

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, Then the value of the entry is set to the given value, whether the entry existed before or not.

Parameters

[in]	key	Key of the value to find or create.
[in]	value	Value to which the key shall map. It will be moved into the map.
[out]	created	This 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.

◆ InsertKey()

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]	key	Key of the value to find or create.
[out]	created	This 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.

◆ FindValue() [1/2]

const V* FindValue ( K key ) const

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

Parameters

[in] key Key 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 ( K key )

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

Parameters

[in] key Key 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 ( K key )

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 ( K key ) const

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 ( 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 not supported when the sorting mode is BURSTTRIE_SORT::NONE.

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 ( 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 not supported when the sorting mode is BURSTTRIE_SORT::NONE.

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.

◆ Erase() [1/2]

ResultOk<Bool> Erase ( K key )

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

Parameters

[in] key Key of the map entry to be be removed.

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

◆ Erase() [2/2]

MAXON_WARN_UNUSED IteratorTemplate<false, SUPER> Erase	(	const IteratorTemplate< false, SUPER > &	position,
		Int	eraseCnt = `1`
	)

Removes eraseCnt elements from this map starting at the position given by position. The returned iterator will point to the element behind the last removed element.

Parameters

[in]	position	Iterator pointing to the first element to be removed.
[in]	eraseCnt	Number of elements to remove.

Returns: Iterator pointing to the element behind the last removed element.

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > )

private

◆ ClearRoots()

void ClearRoots ( )

private

◆ GetDepthImpl()

Int GetDepthImpl ( Index idx ) const

private

◆ GetMemorySizeImpl()

Int GetMemorySizeImpl ( Index idx ) const

private

◆ DestructNodes()

void DestructNodes ( Index idx )

private

◆ CopyNodes()

Result<void> CopyNodes	(	Index &	dest,
		const BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL > &	srcMap,
		Index	src
	)

private

Friends And Related Function Documentation

◆ BurstTrieMapUtils

friend class BurstTrieMapUtils

friend

Member Data Documentation

◆ GROUP_SIZE

const Int GROUP_SIZE

static

◆ GROUP_MASK

const Int GROUP_MASK

static

◆ MAX_LEN

const Int MAX_LEN

static

◆ Pool

friend Pool

private

◆ _roots

Index _roots[MAX_LEN+1]

private

Trie roots, indexed by the position of the highest non-zero group of the key.

◆ _size

Int _size

private

Total number of key-value entries.

Detailed Description

template<typename K, typename V, Int GROUP_BITS = 4, Int BUCKET_SIZE = 16, BURSTTRIE_SORT SORT = BURSTTRIE_SORT::LINEAR_SEARCH, template< typename, typename > class POOL = PointerBurstTriePool> class maxon::BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Member Typedef Documentation

◆ IsBurstTrieMap

◆ Bucket

◆ Node

◆ Pool

◆ Index

◆ Super

◆ Iterator

◆ ConstIterator

◆ KeyIterator

◆ ConstKeyIterator

◆ ValueIterator

◆ ConstValueIterator

Constructor & Destructor Documentation

◆ BurstTrieMap() [1/4]

◆ BurstTrieMap() [2/4]

◆ BurstTrieMap() [3/4]

◆ BurstTrieMap() [4/4]

◆ ~BurstTrieMap()

Member Function Documentation

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

◆ CopyFromImpl()

◆ Reset()

◆ Flush()

◆ SetCapacityHint()

◆ GetCount()

◆ GetOperationCountForSearch()

◆ GetDepth()

◆ GetMemorySize()

◆ Begin() [1/2]

◆ End() [1/2]

◆ Begin() [2/2]

◆ End() [2/2]

◆ GetKeys() [1/2]

◆ GetKeys() [2/2]

◆ GetValues() [1/2]

◆ GetValues() [2/2]

◆ InsertEntry()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ InsertKey()

◆ FindValue() [1/2]

◆ FindValue() [2/2]

◆ Find() [1/2]

◆ Find() [2/2]

◆ FindFloor() [1/2]

◆ FindFloor() [2/2]

◆ Erase() [1/2]

◆ Erase() [2/2]

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

◆ ClearRoots()

◆ GetDepthImpl()

◆ GetMemorySizeImpl()

◆ DestructNodes()

◆ CopyNodes()

Friends And Related Function Documentation

◆ BurstTrieMapUtils

Member Data Documentation

◆ GROUP_SIZE

◆ GROUP_MASK

◆ MAX_LEN

◆ Pool

◆ _roots

◆ _size

template<typename K, typename V, Int GROUP_BITS = 4, Int BUCKET_SIZE = 16, BURSTTRIE_SORT SORT = BURSTTRIE_SORT::LINEAR_SEARCH, template< typename, typename > class POOL = PointerBurstTriePool>
class maxon::BurstTrieMap< K, V, GROUP_BITS, BUCKET_SIZE, SORT, POOL >