hat-trie
Public Types | Public Member Functions | Static Public Member Functions | Friends | List of all members
tsl::htrie_map< CharT, T, Hash, KeySizeT > Class Template Reference

#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_mapoperator= (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, iteratorequal_range_ks (const CharT *key, size_type key_size)
 
std::pair< const_iterator, const_iteratorequal_range_ks (const CharT *key, size_type key_size) const
 
std::pair< iterator, iteratorequal_range (const CharT *key)
 
std::pair< const_iterator, const_iteratorequal_range (const CharT *key) const
 
std::pair< iterator, iteratorequal_range (const std::basic_string< CharT > &key)
 
std::pair< const_iterator, const_iteratorequal_range (const std::basic_string< CharT > &key) const
 
std::pair< prefix_iterator, prefix_iteratorequal_prefix_range_ks (const CharT *prefix, size_type prefix_size)
 
std::pair< const_prefix_iterator, const_prefix_iteratorequal_prefix_range_ks (const CharT *prefix, size_type prefix_size) const
 
std::pair< prefix_iterator, prefix_iteratorequal_prefix_range (const CharT *prefix)
 
std::pair< const_prefix_iterator, const_prefix_iteratorequal_prefix_range (const CharT *prefix) const
 
std::pair< prefix_iterator, prefix_iteratorequal_prefix_range (const std::basic_string< CharT > &prefix)
 
std::pair< const_prefix_iterator, const_prefix_iteratorequal_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)
 

Detailed Description

template<class CharT, class T, class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
class tsl::htrie_map< CharT, T, Hash, KeySizeT >

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:

Member Typedef Documentation

◆ char_type

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::char_type = typename ht::char_type

◆ const_iterator

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::const_iterator = typename ht::const_iterator

◆ const_prefix_iterator

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::const_prefix_iterator = typename ht::const_prefix_iterator

◆ hasher

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::hasher = typename ht::hasher

◆ iterator

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::iterator = typename ht::iterator

◆ key_size_type

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::key_size_type = typename ht::key_size_type

◆ mapped_type

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::mapped_type = T

◆ prefix_iterator

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::prefix_iterator = typename ht::prefix_iterator

◆ size_type

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
using tsl::htrie_map< CharT, T, Hash, KeySizeT >::size_type = typename ht::size_type

Constructor & Destructor Documentation

◆ htrie_map() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
tsl::htrie_map< CharT, T, Hash, KeySizeT >::htrie_map ( const Hash &  hash = Hash())
inlineexplicit

◆ htrie_map() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
tsl::htrie_map< CharT, T, Hash, KeySizeT >::htrie_map ( size_type  burst_threshold,
const Hash &  hash = Hash() 
)
inlineexplicit

◆ htrie_map() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class InputIt , typename std::enable_if< is_iterator< InputIt >::value >::type * = nullptr>
tsl::htrie_map< CharT, T, Hash, KeySizeT >::htrie_map ( InputIt  first,
InputIt  last,
const Hash &  hash = Hash() 
)
inline

◆ htrie_map() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
tsl::htrie_map< CharT, T, Hash, KeySizeT >::htrie_map ( std::initializer_list< std::pair< const CharT *, T >>  init,
const Hash &  hash = Hash() 
)
inline

Member Function Documentation

◆ at() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::at ( const CharT *  key)
inline

◆ at() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::at ( const CharT *  key) const
inline

◆ at() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::at ( const std::basic_string< CharT > &  key)
inline

◆ at() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::at ( const std::basic_string< CharT > &  key) const
inline

◆ at_ks() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::at_ks ( const CharT *  key,
size_type  key_size 
)
inline

◆ at_ks() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::at_ks ( const CharT *  key,
size_type  key_size 
) const
inline

◆ begin() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::begin ( )
inlinenoexcept

◆ begin() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::begin ( ) const
inlinenoexcept

◆ burst_threshold() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::burst_threshold ( ) const
inline

◆ burst_threshold() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::burst_threshold ( size_type  threshold)
inline

◆ cbegin()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::cbegin ( ) const
inlinenoexcept

◆ cend()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::cend ( ) const
inlinenoexcept

◆ clear()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::clear ( )
inlinenoexcept

◆ count() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::count ( const CharT *  key) const
inline

◆ count() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::count ( const std::basic_string< CharT > &  key) const
inline

◆ count_ks()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::count_ks ( const CharT *  key,
size_type  key_size 
) const
inline

◆ deserialize()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class Deserializer >
static htrie_map tsl::htrie_map< CharT, T, Hash, KeySizeT >::deserialize ( Deserializer &  deserializer,
bool  hash_compatible = false 
)
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.

◆ emplace() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class... Args>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::emplace ( const CharT *  key,
Args &&...  args 
)
inline

◆ emplace() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class... Args>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::emplace ( const std::basic_string< CharT > &  key,
Args &&...  args 
)
inline

◆ emplace_ks()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class... Args>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::emplace_ks ( const CharT *  key,
size_type  key_size,
Args &&...  args 
)
inline

◆ empty()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
bool tsl::htrie_map< CharT, T, Hash, KeySizeT >::empty ( ) const
inlinenoexcept

◆ end() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::end ( )
inlinenoexcept

◆ end() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::end ( ) const
inlinenoexcept

◆ equal_prefix_range() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<prefix_iterator, prefix_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_prefix_range ( const CharT *  prefix)
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.

◆ equal_prefix_range() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<const_prefix_iterator, const_prefix_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_prefix_range ( const CharT *  prefix) const
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.

◆ equal_prefix_range() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<prefix_iterator, prefix_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_prefix_range ( const std::basic_string< CharT > &  prefix)
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.

◆ equal_prefix_range() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<const_prefix_iterator, const_prefix_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_prefix_range ( const std::basic_string< CharT > &  prefix) const
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.

◆ equal_prefix_range_ks() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<prefix_iterator, prefix_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_prefix_range_ks ( const CharT *  prefix,
size_type  prefix_size 
)
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.

◆ equal_prefix_range_ks() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<const_prefix_iterator, const_prefix_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_prefix_range_ks ( const CharT *  prefix,
size_type  prefix_size 
) const
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.

◆ equal_range() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_range ( const CharT *  key)
inline

◆ equal_range() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<const_iterator, const_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_range ( const CharT *  key) const
inline

◆ equal_range() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_range ( const std::basic_string< CharT > &  key)
inline

◆ equal_range() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<const_iterator, const_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_range ( const std::basic_string< CharT > &  key) const
inline

◆ equal_range_ks() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_range_ks ( const CharT *  key,
size_type  key_size 
)
inline

◆ equal_range_ks() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<const_iterator, const_iterator> tsl::htrie_map< CharT, T, Hash, KeySizeT >::equal_range_ks ( const CharT *  key,
size_type  key_size 
) const
inline

◆ erase() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase ( const_iterator  pos)
inline

◆ erase() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase ( const_iterator  first,
const_iterator  last 
)
inline

◆ erase() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase ( const CharT *  key)
inline

◆ erase() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase ( const std::basic_string< CharT > &  key)
inline

◆ erase_ks()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase_ks ( const CharT *  key,
size_type  key_size 
)
inline

◆ erase_prefix() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase_prefix ( const CharT *  prefix)
inline

Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.

◆ erase_prefix() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase_prefix ( const std::basic_string< CharT > &  prefix)
inline

Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.

◆ erase_prefix_ks()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::erase_prefix_ks ( const CharT *  prefix,
size_type  prefix_size 
)
inline

Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.

◆ find() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::find ( const CharT *  key)
inline

◆ find() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::find ( const CharT *  key) const
inline

◆ find() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::find ( const std::basic_string< CharT > &  key)
inline

◆ find() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::find ( const std::basic_string< CharT > &  key) const
inline

◆ find_ks() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::find_ks ( const CharT *  key,
size_type  key_size 
)
inline

◆ find_ks() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::find_ks ( const CharT *  key,
size_type  key_size 
) const
inline

◆ hash_function()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
hasher tsl::htrie_map< CharT, T, Hash, KeySizeT >::hash_function ( ) const
inline

◆ insert() [1/6]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert ( const CharT *  key,
const T &  value 
)
inline

◆ insert() [2/6]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert ( const std::basic_string< CharT > &  key,
const T &  value 
)
inline

◆ insert() [3/6]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert ( const CharT *  key,
T &&  value 
)
inline

◆ insert() [4/6]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert ( const std::basic_string< CharT > &  key,
T &&  value 
)
inline

◆ insert() [5/6]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class InputIt , typename std::enable_if< is_iterator< InputIt >::value >::type * = nullptr>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert ( InputIt  first,
InputIt  last 
)
inline

◆ insert() [6/6]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert ( std::initializer_list< std::pair< const CharT *, T >>  ilist)
inline

◆ insert_ks() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert_ks ( const CharT *  key,
size_type  key_size,
const T &  value 
)
inline

◆ insert_ks() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
std::pair<iterator, bool> tsl::htrie_map< CharT, T, Hash, KeySizeT >::insert_ks ( const CharT *  key,
size_type  key_size,
T &&  value 
)
inline

◆ longest_prefix() [1/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::longest_prefix ( const CharT *  key)
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() 

◆ longest_prefix() [2/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::longest_prefix ( const CharT *  key) const
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() 

◆ longest_prefix() [3/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::longest_prefix ( const std::basic_string< CharT > &  key)
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() 

◆ longest_prefix() [4/4]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::longest_prefix ( const std::basic_string< CharT > &  key) const
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() 

◆ longest_prefix_ks() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::longest_prefix_ks ( const CharT *  key,
size_type  key_size 
)
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() 

◆ longest_prefix_ks() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
const_iterator tsl::htrie_map< CharT, T, Hash, KeySizeT >::longest_prefix_ks ( const CharT *  key,
size_type  key_size 
) const
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() 

◆ max_key_size()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::max_key_size ( ) const
inlinenoexcept

◆ max_load_factor() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
float tsl::htrie_map< CharT, T, Hash, KeySizeT >::max_load_factor ( ) const
inline

◆ max_load_factor() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::max_load_factor ( float  ml)
inline

◆ max_size()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::max_size ( ) const
inlinenoexcept

◆ operator=()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
htrie_map& tsl::htrie_map< CharT, T, Hash, KeySizeT >::operator= ( std::initializer_list< std::pair< const CharT *, T >>  ilist)
inline

◆ operator[]() [1/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::operator[] ( const CharT *  key)
inline

◆ operator[]() [2/2]

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
T& tsl::htrie_map< CharT, T, Hash, KeySizeT >::operator[] ( const std::basic_string< CharT > &  key)
inline

◆ serialize()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
template<class Serializer >
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::serialize ( Serializer &  serializer) const
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.

◆ shrink_to_fit()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::shrink_to_fit ( )
inline

Call shrink_to_fit() on each hash node of the hat-trie to reduce its size.

◆ size()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
size_type tsl::htrie_map< CharT, T, Hash, KeySizeT >::size ( ) const
inlinenoexcept

◆ swap()

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void tsl::htrie_map< CharT, T, Hash, KeySizeT >::swap ( htrie_map< CharT, T, Hash, KeySizeT > &  other)
inline

Friends And Related Function Documentation

◆ operator!=

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
bool operator!= ( const htrie_map< CharT, T, Hash, KeySizeT > &  lhs,
const htrie_map< CharT, T, Hash, KeySizeT > &  rhs 
)
friend

◆ operator==

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
bool operator== ( const htrie_map< CharT, T, Hash, KeySizeT > &  lhs,
const htrie_map< CharT, T, Hash, KeySizeT > &  rhs 
)
friend

◆ swap

template<class CharT , class T , class Hash = tsl::ah::str_hash<CharT>, class KeySizeT = std::uint16_t>
void swap ( htrie_map< CharT, T, Hash, KeySizeT > &  lhs,
htrie_map< CharT, T, Hash, KeySizeT > &  rhs 
)
friend

The documentation for this class was generated from the following file: