Stores unique signed integer values in a contiguous array. More...
#include <hashset.h>
Collaboration diagram for Ponca::HashSet< N, T, _HashFunctor, OFFSET >:Public Member Functions | |
| void | clear () |
| Empty the array. | |
| std::pair< typename Self::iterator, bool > | insert (const T &_value) |
| Tries to insert a value in the HashSet. | |
| bool | contains (T _value) const |
| Tries to find a value in the HashSet. | |
| Self::const_iterator | cbegin () const |
| The beginning of the internal array. | |
| Self::const_iterator | cend () const |
| The end of the internal array. | |
| Self::iterator | begin () |
| The beginning of the internal array. | |
| Self::iterator | end () |
| The end of the internal array. | |
Protected Member Functions | |
| bool | search (T _value, T &_searchedIdx) const |
| Search for a value in the HashSet. | |
Detailed Description
class Ponca::HashSet< N, T, _HashFunctor, OFFSET >
Stores unique signed integer values in a contiguous array.
A simple HashMap implementation that mimics a set of indices, by only stores the keys in a Set-like structure (Hence the name HashSet). The internal logic of this HashMap is similar to a std::unordered_map, but is compatible with CUDA.
- Note
- This HashSet type doesn't allow for removal of a single element from the set. It was implemented this way to provide the simplest search and insert method possible
- Warning
- The stored values must never be equal to -1, because it will be mistaken as being empty in the HashSet, and will break the search logic. If you must store -1, change the OFFSET value to something else, by following this simple rule : illegal_value = -OFFSET (e.g. set OFFSET to 2 to allow to store -1, but make -2 illegal to store).
For the search, the best case complexity is O(1), and the worst case complexity is O(n). The complexity is entirely dependent on the hashing function, and the given values : If our hashing function produce sparser result for our set of indices, it will reduce the complexity of the searches for both the HashSet::insert and HashSet::contains method.
- See also
- HashDefaultFunctor::hash for the default hashing function
- BitSet For alternative data structure with compatible API
- Template Parameters
-
N The maximum size of the HashSet T The value type stored in the HashSet (Default to int) _HashFunctor For the hashing function (Default to HashDefaultFunctor) OFFSET Offsets the value stored in m_data, to avoid mistaking it with 0 the is empty flag
Constructor & Destructor Documentation
◆ HashSet()
Member Function Documentation
◆ begin()
The beginning of the internal array.
Definition at line 24 of file hashset.hpp.
◆ cbegin()
|
inline |
The beginning of the internal array.
Definition at line 12 of file hashset.hpp.
◆ cend()
|
inline |
The end of the internal array.
Definition at line 18 of file hashset.hpp.
◆ clear()
| void Ponca::HashSet< N, T, HF, OFFSET >::clear | ( | ) |
Empty the array.
Iterates over every element and sets their values to 0
Definition at line 37 of file hashset.hpp.
◆ contains()
| bool Ponca::HashSet< N, T, HF, OFFSET >::contains | ( | T | _value | ) | const |
Tries to find a value in the HashSet.
- Parameters
-
_value The value to search for
Definition at line 91 of file hashset.hpp.
◆ end()
The end of the internal array.
Definition at line 30 of file hashset.hpp.
◆ insert()
| std::pair< typename HashSet< N, T, HF, OFFSET >::iterator, bool > Ponca::HashSet< N, T, HF, OFFSET >::insert | ( | const T & | _value | ) |
Tries to insert a value in the HashSet.
- Note
- The hashing function doesn't guarantee that we always get different results, sometimes two different values can happen to have the same storage address in our data array. When the hashing function provokes a collision with another value, the HashSet will store the other value in the next available array address. The search will have to keep looking for the value if it isn't stored at the hashing result, which is why the search isn't always of a O(1) complexity.
- Throws an error if value was inserted in an already full HashSet
- Parameters
-
_value The value to be inserted in the HashSet
- Returns
- An std::pair of
Definition at line 70 of file hashset.hpp.
◆ search()
|
inlineprotected |
Search for a value in the HashSet.
Use the hashing function to check if a value is inside the internal array.
- The value isn't considered inside if the value at the address corresponds to the EMPTY flag, (will stop the search and return false as a result)
- If there is already an element at address, but which doesn't correspond to the value, we keep looking at the next address for our value until we either find it, or until we searched everywhere.
Use a reference to either output the id of the last element that was searched in the m_data array or will output -1 if the array is completely full.
- Parameters
-
_value The value to be inserted in the HashSet _searchedIdx Reference to the last searched index or -1 if the array is full.
Definition at line 43 of file hashset.hpp.
