ezEngine  Milestone 7
ezMapBase< KeyType, ValueType, Comparer > Class Template Reference

An associative container. Similar to STL::map. More...

#include <Map.h>

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

Classes

struct  ConstIterator
 Base class for all iterators. More...
 
struct  Iterator
 Forward Iterator to iterate over all elements in sorted order. More...
 
struct  NilNode
 Only used by the sentinel node. More...
 
struct  Node
 A node storing the key/value pair. More...
 

Public Member Functions

bool IsEmpty () const
 Returns whether there are no elements in the map. O(1) operation.
 
ezUInt32 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.
 
ConstIterator GetIterator () const
 Returns a constant Iterator to the very first element.
 
Iterator GetLastIterator ()
 Returns an Iterator to the very last element. For reverse traversal.
 
ConstIterator GetLastIterator () const
 Returns a constant Iterator to the very last element. For reverse traversal.
 
Iterator Insert (const KeyType &key, const ValueType &value)
 Inserts the key/value pair into the tree and returns an Iterator to it. O(log n) operation.
 
bool Remove (const KeyType &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.
 
Iterator FindOrAdd (const KeyType &key, bool *bExisted=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.
 
ValueType & operator[] (const KeyType &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.
 
Iterator Find (const KeyType &key)
 Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found. O(log n) operation.
 
Iterator LowerBound (const KeyType &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.
 
Iterator UpperBound (const KeyType &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.
 
ConstIterator Find (const KeyType &key) const
 Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found. O(log n) operation.
 
bool Contains (const KeyType &key) const
 Checks whether the given key is in the container.
 
ConstIterator LowerBound (const KeyType &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.
 
ConstIterator UpperBound (const KeyType &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.
 
ezAllocatorBaseGetAllocator () const
 Returns the allocator that is used by this instance.
 
bool operator== (const ezMapBase< KeyType, ValueType, Comparer > &rhs) const
 Comparison operator.
 
bool operator!= (const ezMapBase< KeyType, ValueType, Comparer > &rhs) const
 Comparison operator.
 
ezUInt64 GetHeapMemoryUsage () const
 Returns the amount of bytes that are currently allocated on the heap.
 

Protected Member Functions

 ezMapBase (const Comparer &comparer, ezAllocatorBase *pAllocator)
 Initializes the map to be empty.
 
 ezMapBase (const ezMapBase< KeyType, ValueType, Comparer > &cc, ezAllocatorBase *pAllocator)
 Copies all key/value pairs from the given map into this one.
 
 ~ezMapBase ()
 Destroys all elements from the map.
 
void operator= (const ezMapBase< KeyType, ValueType, Comparer > &rhs)
 Copies all key/value pairs from the given map into this one.
 

Private Member Functions

NodeInternal_Find (const KeyType &key) const
 
NodeInternal_LowerBound (const KeyType &key) const
 
NodeInternal_UpperBound (const KeyType &key) const
 
void Constructor ()
 
NodeAcquireNode (const KeyType &key, const ValueType &value, int m_uiLevel, Node *pParent)
 Creates one new node and initializes it.
 
void ReleaseNode (Node *pNode)
 Destroys the given node.
 
NodeSkewNode (Node *root)
 
NodeSplitNode (Node *root)
 
void Insert (const KeyType &key, const ValueType &value, Node *&pInsertedNode)
 
NodeRemove (Node *root, const KeyType &key, bool &bRemoved)
 
NodeGetLeftMost () const
 Returns the left-most node of the tree(smallest key).
 
NodeGetRightMost () const
 Returns the right-most node of the tree(largest key).
 

Private Attributes

Nodem_pRoot
 Root node of the tree.
 
NilNode m_NilNode
 Sentinel node.
 
ezUInt32 m_uiCount
 Number of active nodes in the tree.
 
ezDeque< Node,
ezNullAllocatorWrapper, false > 
m_Elements
 Data store. Keeps all the nodes.
 
Nodem_pFreeElementStack
 Stack of recently discarded nodes to quickly acquire new nodes.
 
Comparer m_Comparer
 Comparer object.
 

Detailed Description

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

An associative container. Similar to STL::map.

A map allows to store key/value pairs. This in turn allows to search for values by looking them up with a certain key. Key/Value pairs can also be erased again. All insertion/erasure/lookup functions take O(log n) time. The map is implemented using a balanced tree (a red-black tree), which means the order of insertions/erasures is not important, since it can never create a degenerated tree, and performance will always stay the same.

KeyType is the key type. For example a string.
ValueType is the value type. For example int.
Comparer is a helper class that implements a strictly weak-ordering comparison for Key types.


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