A fast implementation of a set associative container, this one using a sorted array of key values to lookup a similar array of value pointers.
Requires that the key type support both operator< and operator<=. This could be removed by a small refactor of the binary search loop.
Requires that the value type be stored on the heap, as this class only stores pointers. Fixing this would require changing the class to work with iterators (to allow a sentinel value such as end() to represent a missing value).
| Name | Description |
|---|---|
| Clear() | Removes all entries from the collection. Remember, this object did not take ownership. |
| Find(const TKey &) | Find a value in the collection with TKey key. |
| FindIndex(const TKey &) | Find the index of a given key. |
| GetKey(s32) | Get the key at index i. |
| GetSize() | Returns the number of entries in the collection. |
| GetValue(s32) | Get the value at index i. |
| GetValue(s32) | Get the value at index i. |
| Insert(const TKey &, TValue *) | Insert an pointer to a TValue item into the container. |
| operator[](s32) | Get the value at index i. |
| operator[](s32) | Get the value at index i. |
| Remove(const TKey &, s32 &) | Remove the entry referenced to by key. |
| Remove(const TKey &) | Remove the entry referenced to by key. |
| RemoveIndex(s32) | Remove the entry referenced by index obtained by FindIndex (note that all indices are of course invalidated). |
public: void Clear()
Removes all entries from the collection. Remember, this object did not take ownership.
public: TValue * Find
(
const TKey & key
) const
Find a value in the collection with TKey key.
O(logN) operation.
NULL on failure.
public: s32 FindIndex
(
const TKey & key
) const
Find the index of a given key.
O(logN) operation.
-1 on failure.
public: TKey GetKey
(
s32 i
) const
Get the key at index i.
public: s32 GetSize() const
Returns the number of entries in the collection.
public: const TValue * GetValue
(
s32 i
) const
Get the value at index i.
public: TValue *& GetValue
(
s32 i
)
Get the value at index i.
public: s32 Insert
(
const TKey & key,
TValue * value
)
Insert an pointer to a TValue item into the container.
O(logN) operation.
-1 on failure.
public: const TValue * operator[]
(
s32 i
) const
Get the value at index i.
public: TValue *& operator[]
(
s32 i
)
Get the value at index i.
public: TValue * Remove
(
const TKey & key,
s32 & removedIndex
)
Remove the entry referenced to by key.
removedIndex will be filled by previous index value (note that all indices are of course invalidated).
NULL if not found in collection, otherwise the value object.
public: TValue * Remove
(
const TKey & key
)
Remove the entry referenced to by key.
NULL if not found in collection, otherwise the value object.
public: TValue * RemoveIndex
(
s32 index
)
Remove the entry referenced by index obtained by FindIndex (note that all indices are of course invalidated).
NULL if not found in collection, otherwise the value object.