A bidirectional map (bimap), specialized to map n unique string keys to unique indexes with values of 0 through (n-1) and vice versa. The ordering & values of keys are set at creation and frozen.
More...
#include <FrozenKeyIdxBiMap.h>
|
| | FrozenKeyIdxBiMap () |
| |
| | FrozenKeyIdxBiMap (const std::vector< std::string > &keys) noexcept |
| |
| std::optional< int > | find (const char *key) const noexcept |
| |
|
std::optional< int > | find (std::string_view key) const noexcept |
| |
| std::string | inverse_find (int index) const |
| |
| std::size_t | size () const noexcept |
| |
A bidirectional map (bimap), specialized to map n unique string keys to unique indexes with values of 0 through (n-1) and vice versa. The ordering & values of keys are set at creation and frozen.
- Why Frozen?
- The contents are "frozen" for 3 primary reasons:
- It drastically simplifies the implementation (we don't have to worry about deletion – which can be quite messy)
- Linear-probing generally provides better data locality than other hash collision resolution techniques, but generally has other drawbacks. Freezing the contents lets us mitigate many drawbacks (mostly related to the deletion operation)
- It let's us make copy operations cheaper. Since we know the map won't change, we can just use reference counting.
- I would be stunned if
std::map<std::string, uint16_t> or std::map<const char*, uint16_t> is faster than the internal hash table since std::map is usually implemented as a tree.
◆ FrozenKeyIdxBiMap() [1/2]
| utils::FrozenKeyIdxBiMap::FrozenKeyIdxBiMap |
( |
| ) |
|
|
inline |
◆ FrozenKeyIdxBiMap() [2/2]
| utils::FrozenKeyIdxBiMap::FrozenKeyIdxBiMap |
( |
const std::vector< std::string > & |
keys | ) |
|
|
explicitnoexcept |
Main Constructor
- Parameters
-
| keys | Sequence of 1 or more unique strings. |
◆ find()
| std::optional< int > utils::FrozenKeyIdxBiMap::find |
( |
const char * |
key | ) |
const |
|
noexcept |
Lookup the value associated with the specified key
This returns an empty optional if the key isn't known.
◆ inverse_find()
| std::string utils::FrozenKeyIdxBiMap::inverse_find |
( |
int |
index | ) |
const |
|
inline |
Return the key associated with the specified value
For some context, if this function returns a string s for some index i, then a call to FrozenKeyIdxBiMap::find that passes s will return i
- Warning
- Invalid indices (i.e.
index < 0 OR index >= length) produce undefined behavior
◆ size()
| std::size_t utils::FrozenKeyIdxBiMap::size |
( |
| ) |
const |
|
inlinenoexcept |
return the number of keys in the map
The documentation for this class was generated from the following files:
