template<typename TKey, typename TValue, typename TKeyCompareFunctor, typename TValueCompareFunctor, typename TKeyPrepareCompareFunctor>
class Geo::GeoFixedBinarySearchMap
An associative container with performance OlogN and only one allocation.
This class may be used as a replacement for std::map when:
You know how many entries it will have.
You can add all the entries before lookup.
You care about the number of allocations, or memory fragmentation, or something. The sequence of operations is to create a map large enough to hold all entries, then use Key() and Value() to set the Key/Value pairs for each entry, then call Prepare(). Now that the map is ready, you call Lookup() to find the Value for a Key using a binary search. Duplicate key entries (as defined by the TKeyPrepareCompareFunctor) will be removed, leaving only the lowest value (as defined by the TKeyCompareFunctor).
Functions
| Name | Description |
|---|---|
| ~GeoFixedBinarySearchMap() | Destructor. |
| GeoFixedBinarySearchMap(s32) | Construct a BinarySearchMap. |
| Key(s32) | Obtain access to the key at the given index. |
| Lookup(const TKey &) | Return the index of the object in the map, or -1 if it isn't found. |
| operator[](s32) | Obtain the data at the given index, so that it can be read or modified. |
| Prepare() | Prepare the structure for searching. |
| Size() | Returns the number of entries in the map. |
| Value(s32) | Obtain access to the value at the given index. |
Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::~GeoFixedBinarySearchMap
public: ~GeoFixedBinarySearchMap()
Destructor.
Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::GeoFixedBinarySearchMap
public: GeoFixedBinarySearchMap
(
s32 size
)
Construct a BinarySearchMap.
Parameters
| [in] | size | The number of entries that we want to put in the map. |
TKey& Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::Key
public: TKey & Key
(
s32 idx
)
Obtain access to the key at the given index.
s32 Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::Lookup
public: s32 Lookup
(
const TKey & LookupThis
) const
Return the index of the object in the map, or -1 if it isn't found.
const GeoFixedBinarySearchMapData* Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::operator[]
public: const GeoFixedBinarySearchMapData * operator[]
(
s32 idx
) const
Obtain the data at the given index, so that it can be read or modified.
Parameters
| [in] | idx | The position. |
Returns
A pointer to the data at that position.
void Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::Prepare
public: void Prepare()
Prepare the structure for searching.
First sort it by Key and Data, and then remove duplicate keys.
s32 Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::Size
public: s32 Size()
Returns the number of entries in the map.
TValue& Geo::GeoFixedBinarySearchMap< TKey, TValue, TKeyCompareFunctor, TValueCompareFunctor, TKeyPrepareCompareFunctor >::Value
public: TValue & Value
(
s32 idx
) const
Obtain access to the value at the given index.