|
hat-trie
|
#include <htrie_map.h>
Public Types | |
| using | char_type = typename ht::char_type |
| using | mapped_type = T |
| using | key_size_type = typename ht::key_size_type |
| using | size_type = typename ht::size_type |
| using | hasher = typename ht::hasher |
| using | iterator = typename ht::iterator |
| using | const_iterator = typename ht::const_iterator |
| using | prefix_iterator = typename ht::prefix_iterator |
| using | const_prefix_iterator = typename ht::const_prefix_iterator |
Public Member Functions | |
| htrie_map (const Hash &hash=Hash()) | |
| htrie_map (size_type burst_threshold, const Hash &hash=Hash()) | |
| template<class InputIt , typename std::enable_if< is_iterator< InputIt >::value >::type * = nullptr> | |
| htrie_map (InputIt first, InputIt last, const Hash &hash=Hash()) | |
| htrie_map (std::initializer_list< std::pair< const CharT *, T >> init, const Hash &hash=Hash()) | |
| htrie_map & | operator= (std::initializer_list< std::pair< const CharT *, T >> ilist) |
| iterator | begin () noexcept |
| const_iterator | begin () const noexcept |
| const_iterator | cbegin () const noexcept |
| iterator | end () noexcept |
| const_iterator | end () const noexcept |
| const_iterator | cend () const noexcept |
| bool | empty () const noexcept |
| size_type | size () const noexcept |
| size_type | max_size () const noexcept |
| size_type | max_key_size () const noexcept |
| void | shrink_to_fit () |
| void | clear () noexcept |
| std::pair< iterator, bool > | insert_ks (const CharT *key, size_type key_size, const T &value) |
| std::pair< iterator, bool > | insert (const CharT *key, const T &value) |
| std::pair< iterator, bool > | insert (const std::basic_string< CharT > &key, const T &value) |
| std::pair< iterator, bool > | insert_ks (const CharT *key, size_type key_size, T &&value) |
| std::pair< iterator, bool > | insert (const CharT *key, T &&value) |
| std::pair< iterator, bool > | insert (const std::basic_string< CharT > &key, T &&value) |
| template<class InputIt , typename std::enable_if< is_iterator< InputIt >::value >::type * = nullptr> | |
| void | insert (InputIt first, InputIt last) |
| void | insert (std::initializer_list< std::pair< const CharT *, T >> ilist) |
| template<class... Args> | |
| std::pair< iterator, bool > | emplace_ks (const CharT *key, size_type key_size, Args &&... args) |
| template<class... Args> | |
| std::pair< iterator, bool > | emplace (const CharT *key, Args &&... args) |
| template<class... Args> | |
| std::pair< iterator, bool > | emplace (const std::basic_string< CharT > &key, Args &&... args) |
| iterator | erase (const_iterator pos) |
| iterator | erase (const_iterator first, const_iterator last) |
| size_type | erase_ks (const CharT *key, size_type key_size) |
| size_type | erase (const CharT *key) |
| size_type | erase (const std::basic_string< CharT > &key) |
| size_type | erase_prefix_ks (const CharT *prefix, size_type prefix_size) |
| size_type | erase_prefix (const CharT *prefix) |
| size_type | erase_prefix (const std::basic_string< CharT > &prefix) |
| void | swap (htrie_map &other) |
| T & | at_ks (const CharT *key, size_type key_size) |
| const T & | at_ks (const CharT *key, size_type key_size) const |
| T & | at (const CharT *key) |
| const T & | at (const CharT *key) const |
| T & | at (const std::basic_string< CharT > &key) |
| const T & | at (const std::basic_string< CharT > &key) const |
| T & | operator[] (const CharT *key) |
| T & | operator[] (const std::basic_string< CharT > &key) |
| size_type | count_ks (const CharT *key, size_type key_size) const |
| size_type | count (const CharT *key) const |
| size_type | count (const std::basic_string< CharT > &key) const |
| iterator | find_ks (const CharT *key, size_type key_size) |
| const_iterator | find_ks (const CharT *key, size_type key_size) const |
| iterator | find (const CharT *key) |
| const_iterator | find (const CharT *key) const |
| iterator | find (const std::basic_string< CharT > &key) |
| const_iterator | find (const std::basic_string< CharT > &key) const |
| std::pair< iterator, iterator > | equal_range_ks (const CharT *key, size_type key_size) |
| std::pair< const_iterator, const_iterator > | equal_range_ks (const CharT *key, size_type key_size) const |
| std::pair< iterator, iterator > | equal_range (const CharT *key) |
| std::pair< const_iterator, const_iterator > | equal_range (const CharT *key) const |
| std::pair< iterator, iterator > | equal_range (const std::basic_string< CharT > &key) |
| std::pair< const_iterator, const_iterator > | equal_range (const std::basic_string< CharT > &key) const |
| std::pair< prefix_iterator, prefix_iterator > | equal_prefix_range_ks (const CharT *prefix, size_type prefix_size) |
| std::pair< const_prefix_iterator, const_prefix_iterator > | equal_prefix_range_ks (const CharT *prefix, size_type prefix_size) const |
| std::pair< prefix_iterator, prefix_iterator > | equal_prefix_range (const CharT *prefix) |
| std::pair< const_prefix_iterator, const_prefix_iterator > | equal_prefix_range (const CharT *prefix) const |
| std::pair< prefix_iterator, prefix_iterator > | equal_prefix_range (const std::basic_string< CharT > &prefix) |
| std::pair< const_prefix_iterator, const_prefix_iterator > | equal_prefix_range (const std::basic_string< CharT > &prefix) const |
| iterator | longest_prefix_ks (const CharT *key, size_type key_size) |
| const_iterator | longest_prefix_ks (const CharT *key, size_type key_size) const |
| iterator | longest_prefix (const CharT *key) |
| const_iterator | longest_prefix (const CharT *key) const |
| iterator | longest_prefix (const std::basic_string< CharT > &key) |
| const_iterator | longest_prefix (const std::basic_string< CharT > &key) const |
| float | max_load_factor () const |
| void | max_load_factor (float ml) |
| size_type | burst_threshold () const |
| void | burst_threshold (size_type threshold) |
| hasher | hash_function () const |
| template<class Serializer > | |
| void | serialize (Serializer &serializer) const |
Static Public Member Functions | |
| template<class Deserializer > | |
| static htrie_map | deserialize (Deserializer &deserializer, bool hash_compatible=false) |
Friends | |
| bool | operator== (const htrie_map &lhs, const htrie_map &rhs) |
| bool | operator!= (const htrie_map &lhs, const htrie_map &rhs) |
| void | swap (htrie_map &lhs, htrie_map &rhs) |
Implementation of a hat-trie map.
The value T must be either nothrow move-constructible/assignable, copy-constuctible or both.
The size of a key string is limited to std::numeric_limits<KeySizeT>::max() - 1. That is 65 535 characters by default, but can be raised with the KeySizeT template parameter. See max_key_size() for an easy access to this limit.
Iterators invalidation:
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::char_type = typename ht::char_type |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::const_iterator = typename ht::const_iterator |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::const_prefix_iterator = typename ht::const_prefix_iterator |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::hasher = typename ht::hasher |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::iterator = typename ht::iterator |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::key_size_type = typename ht::key_size_type |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::mapped_type = T |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::prefix_iterator = typename ht::prefix_iterator |
| using tsl::htrie_map< CharT, T, Hash, KeySizeT >::size_type = typename ht::size_type |
|
inlineexplicit |
|
inlineexplicit |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
|
inline |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
|
inlinestatic |
Deserialize a previouly serialized map through the deserializer parameter.
The deserializer parameter must be a function object that supports the following calls:
template<typename U> U operator()(); where the types std::uint64_t, float and T must be supported for U.void operator()(CharT* value_out, std::size_t value_size);If the deserialized hash map part of the hat-trie is hash compatible with the serialized map, the deserialization process can be sped up by setting hash_compatible to true. To be hash compatible, the Hash (take care of the 32-bits vs 64 bits), and KeySizeT must behave the same than the ones used in the serialized map. Otherwise the behaviour is undefined with hash_compatible sets to true.
The behaviour is undefined if the type CharT and T of the htrie_map are not the same as the types used during serialization.
The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, size of int, ...) of the types it deserializes in the hands of the Deserializer function object if compatibilty is required.
|
inline |
|
inline |
|
inline |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair of iterator, the first being the begin iterator and the second being the end iterator.
|
inline |
Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair of iterator, the first being the begin iterator and the second being the end iterator.
|
inline |
Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair of iterator, the first being the begin iterator and the second being the end iterator.
|
inline |
Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair of iterator, the first being the begin iterator and the second being the end iterator.
|
inline |
Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair of iterator, the first being the begin iterator and the second being the end iterator.
|
inline |
Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair of iterator, the first being the begin iterator and the second being the end iterator.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.
|
inline |
Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.
|
inline |
Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Return the element in the trie which is the longest prefix of key. If no element in the trie is a prefix of key, the end iterator is returned.
Example:
tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
map.longest_prefix("/foo"); // returns {"/foo", 1}
map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
map.longest_prefix("/bar"); // returns end()
map.longest_prefix(""); // returns end()
|
inline |
Return the element in the trie which is the longest prefix of key. If no element in the trie is a prefix of key, the end iterator is returned.
Example:
tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
map.longest_prefix("/foo"); // returns {"/foo", 1}
map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
map.longest_prefix("/bar"); // returns end()
map.longest_prefix(""); // returns end()
|
inline |
Return the element in the trie which is the longest prefix of key. If no element in the trie is a prefix of key, the end iterator is returned.
Example:
tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
map.longest_prefix("/foo"); // returns {"/foo", 1}
map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
map.longest_prefix("/bar"); // returns end()
map.longest_prefix(""); // returns end()
|
inline |
Return the element in the trie which is the longest prefix of key. If no element in the trie is a prefix of key, the end iterator is returned.
Example:
tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
map.longest_prefix("/foo"); // returns {"/foo", 1}
map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
map.longest_prefix("/bar"); // returns end()
map.longest_prefix(""); // returns end()
|
inline |
Return the element in the trie which is the longest prefix of key. If no element in the trie is a prefix of key, the end iterator is returned.
Example:
tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
map.longest_prefix("/foo"); // returns {"/foo", 1}
map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
map.longest_prefix("/bar"); // returns end()
map.longest_prefix(""); // returns end()
|
inline |
Return the element in the trie which is the longest prefix of key. If no element in the trie is a prefix of key, the end iterator is returned.
Example:
tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
map.longest_prefix("/foo"); // returns {"/foo", 1}
map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
map.longest_prefix("/bar"); // returns end()
map.longest_prefix(""); // returns end()
|
inlinenoexcept |
|
inline |
|
inline |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
|
inline |
Serialize the map through the serializer parameter.
The serializer parameter must be a function object that supports the following calls:
void operator()(const U& value); where the types std::uint64_t, float and T must be supported for U.void operator()(const CharT* value, std::size_t value_size);The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, ...) of the types it serializes in the hands of the Serializer function object if compatibilty is required.
|
inline |
Call shrink_to_fit() on each hash node of the hat-trie to reduce its size.
|
inlinenoexcept |
|
inline |
|
friend |
|
friend |
|
friend |
1.8.13