A red-black tree–based associative container for key/value pairs. More...

#include <Map.h>

Inheritance diagram for xiiMapBase< KeyType, ValueType, Comparer >:

Public Types
using	ConstIterator = xiiMapBaseConstIteratorBase<KeyType, ValueType, Comparer, false>

using	ConstReverseIterator = xiiMapBaseConstIteratorBase<KeyType, ValueType, Comparer, true>

using	Iterator = xiiMapBaseIteratorBase<KeyType, ValueType, Comparer, false>

using	ReverseIterator = xiiMapBaseIteratorBase<KeyType, ValueType, Comparer, true>

Public Member Functions
bool	IsEmpty () const
	Returns whether there are no elements in the map. O(1) operation.

xiiUInt32	GetCount () const
	Returns the number of elements currently stored in the map. O(1) operation.

void	Clear ()
	Destroys all elements in the map and resets its size to zero.

Iterator	GetIterator ()
	Returns an Iterator to the very first element.

ReverseIterator	GetReverseIterator ()
	Returns a ReverseIterator to the very last element.

ConstIterator	GetIterator () const
	Returns a constant Iterator to the very first element.

ConstReverseIterator	GetReverseIterator () const
	Returns a constant ReverseIterator to the very last element.

template<typename CompatibleKeyType, typename CompatibleValueType>
Iterator	Insert (CompatibleKeyType &&key, CompatibleValueType &&value)
	Inserts the key/value pair into the tree and returns an Iterator to it. O(log n) operation.

template<typename CompatibleKeyType>
bool	Remove (const CompatibleKeyType &key)
	Erases the key/value pair with the given key, if it exists. O(log n) operation.

Iterator	Remove (const Iterator &pos)
	Erases the key/value pair at the given Iterator. O(log n) operation. Returns an iterator to the element after the given iterator.

template<typename CompatibleKeyType>
Iterator	FindOrAdd (CompatibleKeyType &&key, bool *out_pExisted=nullptr)
	Searches for the given key and returns an iterator to it. If it did not exist yet, it is default-created. bExisted is set to true, if the key was found, false if it needed to be created.

template<typename CompatibleKeyType>
ValueType &	operator[] (const CompatibleKeyType &key)
	Allows read/write access to the value stored under the given key. If there is no such key, a new element is default-constructed.

template<typename CompatibleKeyType>
bool	TryGetValue (const CompatibleKeyType &key, ValueType &out_value) const
	Returns whether an entry with the given key was found and if found writes out the corresponding value to out_value.

template<typename CompatibleKeyType>
bool	TryGetValue (const CompatibleKeyType &key, const ValueType *&out_pValue) const
	Returns whether an entry with the given key was found and if found writes out the pointer to the corresponding value to out_pValue.

template<typename CompatibleKeyType>
bool	TryGetValue (const CompatibleKeyType &key, ValueType *&out_pValue) const
	Returns whether an entry with the given key was found and if found writes out the pointer to the corresponding value to out_pValue.

template<typename CompatibleKeyType>
const ValueType *	GetValue (const CompatibleKeyType &key) const
	Returns a pointer to the value of the entry with the given key if found, otherwise returns nullptr.

template<typename CompatibleKeyType>
ValueType *	GetValue (const CompatibleKeyType &key)
	Returns a pointer to the value of the entry with the given key if found, otherwise returns nullptr.

template<typename CompatibleKeyType>
const ValueType &	GetValueOrDefault (const CompatibleKeyType &key, const ValueType &defaultValue) const
	Either returns the value of the entry with the given key, if found, or the provided default value.

template<typename CompatibleKeyType>
Iterator	Find (const CompatibleKeyType &key)
	Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found. O(log n) operation.

template<typename CompatibleKeyType>
Iterator	LowerBound (const CompatibleKeyType &key)
	Returns an Iterator to the element with a key equal or larger than the given key. Returns an invalid iterator, if there is no such element.

template<typename CompatibleKeyType>
Iterator	UpperBound (const CompatibleKeyType &key)
	Returns an Iterator to the element with a key that is LARGER than the given key. Returns an invalid iterator, if there is no such element.

template<typename CompatibleKeyType>
ConstIterator	Find (const CompatibleKeyType &key) const
	Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found. O(log n) operation.

template<typename CompatibleKeyType>
bool	Contains (const CompatibleKeyType &key) const
	Checks whether the given key is in the container.

template<typename CompatibleKeyType>
ConstIterator	LowerBound (const CompatibleKeyType &key) const
	Returns an Iterator to the element with a key equal or larger than the given key. Returns an invalid iterator, if there is no such element.

template<typename CompatibleKeyType>
ConstIterator	UpperBound (const CompatibleKeyType &key) const
	Returns an Iterator to the element with a key that is LARGER than the given key. Returns an invalid iterator, if there is no such element.

xiiAllocatorBase *	GetAllocator () const
	Returns the allocator that is used by this instance.

bool	operator== (const xiiMapBase< KeyType, ValueType, Comparer > &rhs) const
	Comparison operator.

xiiUInt64	GetHeapMemoryUsage () const
	Returns the amount of bytes that are currently allocated on the heap.

void	Swap (xiiMapBase< KeyType, ValueType, Comparer > &other)
	Swaps this map with the other one.

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE bool	TryGetValue (const CompatibleKeyType &key, ValueType &out_value) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE bool	TryGetValue (const CompatibleKeyType &key, const ValueType *&out_pValue) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE bool	TryGetValue (const CompatibleKeyType &key, ValueType *&out_pValue) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE const ValueType *	GetValue (const CompatibleKeyType &key) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE ValueType *	GetValue (const CompatibleKeyType &key)

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE const ValueType &	GetValueOrDefault (const CompatibleKeyType &key, const ValueType &defaultValue) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE xiiMapBase< KeyType, ValueType, Comparer >::Iterator	Find (const CompatibleKeyType &key)

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE xiiMapBase< KeyType, ValueType, Comparer >::ConstIterator	Find (const CompatibleKeyType &key) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE bool	Contains (const CompatibleKeyType &key) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE xiiMapBase< KeyType, ValueType, Comparer >::Iterator	LowerBound (const CompatibleKeyType &key)

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE xiiMapBase< KeyType, ValueType, Comparer >::ConstIterator	LowerBound (const CompatibleKeyType &key) const

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE xiiMapBase< KeyType, ValueType, Comparer >::Iterator	UpperBound (const CompatibleKeyType &key)

template<typename CompatibleKeyType>
XII_ALWAYS_INLINE xiiMapBase< KeyType, ValueType, Comparer >::ConstIterator	UpperBound (const CompatibleKeyType &key) const

Protected Member Functions
	xiiMapBase (const Comparer &comparer, xiiAllocatorBase *pAllocator)
	Initializes the map to be empty.

	xiiMapBase (const xiiMapBase< KeyType, ValueType, Comparer > &cc, xiiAllocatorBase *pAllocator)
	Copies all key/value pairs from the given map into this one.

	~xiiMapBase ()
	Destroys all elements from the map.

void	operator= (const xiiMapBase< KeyType, ValueType, Comparer > &rhs)
	Copies all key/value pairs from the given map into this one.

Detailed Description

template<typename KeyType, typename ValueType, typename Comparer>
class xiiMapBase< KeyType, ValueType, Comparer >

A red-black tree–based associative container for key/value pairs.

This container provides efficient storage and lookup of elements by key, similar to std::map. It supports dynamic insertion, lookup, and deletion in O(log n) time through the use of a balanced binary search tree (red-black tree). Key/value pairs are ordered automatically based on the provided comparison logic.

Template Parameters

KeyType	The type of the keys (e.g., `xiiString` or `xiiInt32`).
ValueType	The type of the mapped values associated with each key.
Comparer	A helper class that defines a strictly weak ordering for comparing `KeyType` values.

Note: The container automatically maintains balance regardless of insertion order, preventing degenerate tree performance scenarios.

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

/home/runner/work/XII/XII/Source/Engine/Foundation/Containers/Map.h
/home/runner/work/XII/XII/Source/Engine/Foundation/Containers/Implementation/Map_inl.h

Public Types

Public Member Functions

Protected Member Functions

Detailed Description