1.7.3Please send us your comment about this page
This class implements an efficient map based on key comparison, which stores key-value pairs.
It executes insertion, deletion and query operations in O(log(n)) time.
#include <fbxmap.h>
Classes |
|
| class | FbxKeyValuePair |
| This class defines the key-value pairs used
in
FbxMap. More... |
|
Public Types |
|
| typedef VALUE_TYPE | ValueType |
| typedef KEY_TYPE | KeyType |
| typedef StorageType::RecordType | RecordType |
| typedef StorageType::IteratorType | Iterator |
|
typedef StorageType::ConstIteratorType |
ConstIterator |
Public Member Functions |
|
| FbxMap () | |
| Constructor. |
|
| FbxMap (const FbxMap &pMap) | |
| Copy constructor. |
|
| ~FbxMap () | |
| Destructor. |
|
| void | Reserve (unsigned int pRecordCount) |
| Preallocate memory. |
|
| int | GetSize () const |
| Retrieve the number of key-value pairs it
holds. |
|
| FbxPair< RecordType *, bool > | Insert (const KeyType &pKey, const ValueType &pValue) |
| Insert a key-value pair. |
|
| int | Remove (const KeyType &pKey) |
| Delete a key-value pair. |
|
| void | Clear () |
| Clear the map. |
|
| bool | Empty () const |
| Query whether the map is empty. |
|
| Iterator | Begin () |
| Retrieve the begin iterator of the map.
|
|
| Iterator | End () |
| Retrieve the end iterator of the map.
|
|
| ConstIterator | Begin () const |
| Retrieve the begin iterator of the map.
|
|
| ConstIterator | End () const |
| Retrieve the end iterator of the map.
|
|
| const RecordType * | Find (const KeyType &pKey) const |
| Query a key. |
|
| RecordType * | Find (const KeyType &pKey) |
| Query a key. |
|
| const RecordType * | UpperBound (const KeyType &pKey) const |
| Find the key-value pair with the smallest
key greater than a specified key. |
|
| RecordType * | UpperBound (const KeyType &pKey) |
| Find the key-value pair with the smallest
key greater than a specified key. |
|
| ValueType & | operator[] (const KeyType &pKey) |
| Retrieve the reference of the value in the
key-value pairs in map. |
|
| const RecordType * | Minimum () const |
| Retrieve the key-value pair which is the
minimum key in map. |
|
| RecordType * | Minimum () |
| Retrieve the key-value pair which is the
minimum key in map. |
|
| const RecordType * | Maximum () const |
| Retrieve the key-value pair which is the
maximum key in map. |
|
| RecordType * | Maximum () |
| Retrieve the key-value pair which is the
maximum key in map. |
|
Protected Types |
|
| typedef
FbxRedBlackTree < FbxKeyValuePair, KEY_COMPARE_FUNCTOR, ALLOCATOR > |
StorageType |
Protected Attributes |
|
| StorageType | mTree |
typedef FbxRedBlackTree<FbxKeyValuePair,
KEY_COMPARE_FUNCTOR, ALLOCATOR> StorageType
[protected] |
| typedef VALUE_TYPE ValueType |
| typedef KEY_TYPE KeyType |
| typedef StorageType::RecordType RecordType |
| typedef StorageType::IteratorType Iterator |
| void Reserve | ( | unsigned int | pRecordCount | ) | [inline] |
Preallocate memory.
| pRecordCount | The number of elements. |
| int GetSize | ( | ) | const [inline] |
Retrieve the number of key-value pairs it holds.
| FbxPair<RecordType*, bool> Insert | ( | const KeyType & | pKey, |
| const ValueType & | pValue | ||
| ) | [inline] |
Insert a key-value pair.
| pKey | The key. |
| pValue | The value. |
| int Remove | ( | const KeyType & | pKey | ) | [inline] |
Delete a key-value pair.
| pKey | The key. |
true if success, false if key is not
found.| void Clear | ( | ) | [inline] |
Clear the map.
| bool Empty | ( | ) | const [inline] |
Query whether the map is empty.
| Iterator Begin | ( | ) | [inline] |
Retrieve the begin iterator of the map.
| Iterator End | ( | ) | [inline] |
| ConstIterator Begin | ( | ) | const [inline] |
Retrieve the begin iterator of the map.
Definition at line 1522 of file fbxmap.h.
{
return ConstIterator(Minimum());
}
| ConstIterator End | ( | ) | const [inline] |
Retrieve the end iterator of the map.
Definition at line 1528 of file fbxmap.h.
{
return ConstIterator();
}
| const RecordType* Find | ( | const KeyType & | pKey | ) | const [inline] |
Query a key.
| pKey | The key. |
| RecordType* Find | ( | const KeyType & | pKey | ) | [inline] |
Query a key.
| pKey | The key. |
| const RecordType* UpperBound | ( | const KeyType & | pKey | ) | const [inline] |
Find the key-value pair with the smallest key greater than a specified key.
| pKey | The key. |
Definition at line 1555 of file fbxmap.h.
{
return mTree.UpperBound(pKey);
}
| RecordType* UpperBound | ( | const KeyType & | pKey | ) | [inline] |
Find the key-value pair with the smallest key greater than a specified key.
| pKey | The key. |
Definition at line 1564 of file fbxmap.h.
{
return mTree.UpperBound(pKey);
}
Retrieve the reference of the value in the key-value pairs in map.
| pKey | The key. |
Definition at line 1574 of file fbxmap.h.
{
RecordType* lRecord = Find(pKey);
if( !lRecord )
{
lRecord = Insert(pKey, ValueType()).mFirst;
}
return lRecord->GetValue();
}
| const RecordType* Minimum | ( | ) | const [inline] |
Retrieve the key-value pair which is the minimum key in map.
| RecordType* Minimum | ( | ) | [inline] |
Retrieve the key-value pair which is the minimum key in map.
| const RecordType* Maximum | ( | ) | const [inline] |
Retrieve the key-value pair which is the maximum key in map.
| RecordType* Maximum | ( | ) | [inline] |
Retrieve the key-value pair which is the maximum key in map.
StorageType mTree
[protected] |