 |
XII Release 0.1.0
|
|
XII Release 0.1.0
|
Implementation of a hashset. More...
#include <HashSet.h>
Classes | |
| class | ConstIterator |
| Const iterator. More... | |
Public Member Functions | |
| bool | operator== (const xiiHashSetBase< KeyType, Hasher > &rhs) const |
| Compares this table to another table. | |
| void | Reserve (xiiUInt32 uiCapacity) |
| Expands the hashset by over-allocating the internal storage so that the load factor is lower or equal to 60% when inserting the given number of entries. | |
| void | Compact () |
| Tries to compact the hashset to avoid wasting memory. | |
| xiiUInt32 | GetCount () const |
| Returns the number of active entries in the table. | |
| bool | IsEmpty () const |
| Returns true, if the hashset does not contain any elements. | |
| void | Clear () |
| Clears the table. | |
| template<typename CompatibleKeyType> | |
| bool | Insert (CompatibleKeyType &&key) |
| Inserts the key. Returns whether the key was already existing. | |
| template<typename CompatibleKeyType> | |
| bool | Remove (const CompatibleKeyType &key) |
| Removes the entry with the given key. Returns if an entry was removed. | |
| ConstIterator | Remove (const ConstIterator &pos) |
| Erases the key at the given Iterator. Returns an iterator to the element after the given iterator. | |
| template<typename CompatibleKeyType> | |
| bool | Contains (const CompatibleKeyType &key) const |
| Returns if an entry with given key exists in the table. | |
| bool | ContainsSet (const xiiHashSetBase< KeyType, Hasher > &operand) const |
| Checks whether all keys of the given set are in the container. | |
| void | Union (const xiiHashSetBase< KeyType, Hasher > &operand) |
| Makes this set the union of itself and the operand. | |
| void | Difference (const xiiHashSetBase< KeyType, Hasher > &operand) |
| Makes this set the difference of itself and the operand, i.e. subtracts operand. | |
| void | Intersection (const xiiHashSetBase< KeyType, Hasher > &operand) |
| Makes this set the intersection of itself and the operand. | |
| ConstIterator | GetIterator () const |
| Returns a constant Iterator to the very first element. | |
| ConstIterator | GetEndIterator () const |
| Returns a constant Iterator to the first element that is not part of the hashset. Needed to implement range based for loop support. | |
| xiiAllocatorBase * | GetAllocator () const |
| Returns the allocator that is used by this instance. | |
| xiiUInt64 | GetHeapMemoryUsage () const |
| Returns the amount of bytes that are currently allocated on the heap. | |
| void | Swap (xiiHashSetBase< KeyType, Hasher > &other) |
| Swaps this map with the other one. | |
| template<typename CompatibleKeyType> | |
| ConstIterator | Find (const CompatibleKeyType &key) const |
| Searches for key, returns a ConstIterator to it or an invalid iterator, if no such key is found. O(1) operation. | |
| template<typename CompatibleKeyType> | |
| XII_FORCE_INLINE bool | Contains (const CompatibleKeyType &key) const |
| template<typename CompatibleKeyType> | |
| XII_FORCE_INLINE xiiHashSetBase< K, H >::ConstIterator | Find (const CompatibleKeyType &key) const |
| template<typename CompatibleKeyType> | |
| XII_FORCE_INLINE xiiUInt32 | FindEntry (const CompatibleKeyType &key) const |
Protected Member Functions | |
| xiiHashSetBase (xiiAllocatorBase *pAllocator) | |
| Creates an empty hashset. Does not allocate any data yet. | |
| xiiHashSetBase (const xiiHashSetBase< KeyType, Hasher > &rhs, xiiAllocatorBase *pAllocator) | |
| Creates a copy of the given hashset. | |
| xiiHashSetBase (xiiHashSetBase< KeyType, Hasher > &&rhs, xiiAllocatorBase *pAllocator) | |
| Moves data from an existing hashtable into this one. | |
| ~xiiHashSetBase () | |
| Destructor. | |
| void | operator= (const xiiHashSetBase< KeyType, Hasher > &rhs) |
| Copies the data from another hashset into this one. | |
| void | operator= (xiiHashSetBase< KeyType, Hasher > &&rhs) |
| Moves data from an existing hashset into this one. | |
Implementation of a hashset.
The hashset stores values by using the hash as an index into the table. This implementation uses linear-probing to resolve hash collisions which means all values are stored in a linear array. All insertion/erasure/lookup functions take O(1) time if the table does not need to be expanded, which happens when the load gets greater than 60%. The hash function can be customized by providing a Hasher helper class like xiiHashHelper.
| void xiiHashSetBase< K, H >::Compact | ( | ) |
Tries to compact the hashset to avoid wasting memory.
The resulting capacity is at least 'GetCount' (no elements get removed). Will deallocate all data, if the hashset is empty.
1.13.2