mdds
Classes | Public Types | Public Member Functions | Friends | List of all members
mdds::packed_trie_map< KeyTraits, ValueT > Class Template Reference

#include <trie_map.hpp>

Classes

struct  entry
 

Public Types

typedef KeyTraits key_traits_type
 
typedef key_traits_type::key_type key_type
 
typedef key_traits_type::key_buffer_type key_buffer_type
 
typedef key_traits_type::key_unit_type key_unit_type
 
typedef ValueT value_type
 
typedef size_t size_type
 
typedef std::pair< key_type, value_type > key_value_type
 
typedef trie::detail::packed_iterator_base< packed_trie_mapconst_iterator
 
typedef trie::detail::packed_search_results< packed_trie_mapsearch_results
 

Public Member Functions

 packed_trie_map (const entry *entries, size_type entry_size)
 
 packed_trie_map (const trie_map< key_traits_type, value_type > &other)
 
 packed_trie_map (const packed_trie_map &other)
 
 packed_trie_map (packed_trie_map &&other)
 
packed_trie_mapoperator= (packed_trie_map other)
 
bool operator== (const packed_trie_map &other) const
 
bool operator!= (const packed_trie_map &other) const
 
const_iterator begin () const
 
const_iterator end () const
 
const_iterator cbegin () const
 
const_iterator cend () const
 
const_iterator find (const key_type &key) const
 
const_iterator find (const key_unit_type *input, size_type len) const
 
search_results prefix_search (const key_type &prefix) const
 
search_results prefix_search (const key_unit_type *prefix, size_type len) const
 
size_type size () const noexcept
 
bool empty () const noexcept
 
void swap (packed_trie_map &other)
 
template<typename FuncT = trie::value_serializer<value_type>>
void save_state (std::ostream &os) const
 
template<typename FuncT = trie::value_serializer<value_type>>
void load_state (std::istream &is)
 
void dump_structure () const
 

Friends

class trie::detail::packed_iterator_base< packed_trie_map >
 
class trie::detail::packed_search_results< packed_trie_map >
 

Detailed Description

template<typename KeyTraits, typename ValueT>
class mdds::packed_trie_map< KeyTraits, ValueT >

An immutable trie container that packs its content into a contiguous array to achieve both space efficiency and lookup performance. The user of this data structure must provide a pre-constructed list of key-value entries that are sorted by the key in ascending order, or construct from an instance of mdds::trie_map.

Note that, since this container is immutable, the content of the container cannot be modified once constructed.

Constructor & Destructor Documentation

◆ packed_trie_map() [1/2]

template<typename KeyTraits , typename ValueT >
mdds::packed_trie_map< KeyTraits, ValueT >::packed_trie_map ( const entry entries,
size_type  entry_size 
)

Constructor that initializes the content from a static list of key-value entries. The caller must ensure that the key-value entries are sorted in ascending order, else the behavior is undefined.

Parameters
entriespointer to the array of key-value entries.
entry_sizesize of the key-value entry array.

◆ packed_trie_map() [2/2]

template<typename KeyTraits , typename ValueT >
mdds::packed_trie_map< KeyTraits, ValueT >::packed_trie_map ( const trie_map< key_traits_type, value_type > &  other)

Constructor to allow construction of an instance from the content of a mdds::trie_map instance.

Parameters
othermdds::trie_map instance to build content from.

Member Function Documentation

◆ dump_structure()

template<typename KeyTraits , typename ValueT >
void mdds::packed_trie_map< KeyTraits, ValueT >::dump_structure ( ) const

Dump the structure of the trie content for debugging. You must define MDDS_TRIE_MAP_DEBUG in order for this method to generate output.

◆ find() [1/2]

template<typename KeyTraits , typename ValueT >
const_iterator mdds::packed_trie_map< KeyTraits, ValueT >::find ( const key_type &  key) const

Find a value associated with a specified key.

Parameters
keykey to match.
Returns
iterator that references a value associated with the key, or the end position in case the key is not found.

◆ find() [2/2]

template<typename KeyTraits , typename ValueT >
const_iterator mdds::packed_trie_map< KeyTraits, ValueT >::find ( const key_unit_type *  input,
size_type  len 
) const

Find a value associated with a specified key.

Parameters
inputpointer to an array whose value represents the key to match.
lenlength of the matching key value.
Returns
iterator that references a value associated with the key, or the end position in case the key is not found.

◆ load_state()

template<typename KeyTraits , typename ValueT >
template<typename FuncT = trie::value_serializer<value_type>>
void mdds::packed_trie_map< KeyTraits, ValueT >::load_state ( std::istream &  is)

Restore the state of the instance of this class from an external buffer.

Parameters
isinput stream to load the state from.

◆ prefix_search() [1/2]

template<typename KeyTraits , typename ValueT >
search_results mdds::packed_trie_map< KeyTraits, ValueT >::prefix_search ( const key_type &  prefix) const

Retrieve all key-value pairs whose keys start with specified prefix. You can also retrieve all key-value pairs by passing a null prefix and a length of zero.

Parameters
prefixprefix to match.
Returns
results object containing all matching key-value pairs.

◆ prefix_search() [2/2]

template<typename KeyTraits , typename ValueT >
search_results mdds::packed_trie_map< KeyTraits, ValueT >::prefix_search ( const key_unit_type *  prefix,
size_type  len 
) const

Retrieve all key-value pairs whose keys start with specified prefix. You can also retrieve all key-value pairs by passing a null prefix and a length of zero.

Parameters
prefixpointer to an array whose value represents the prefix to match.
lenlength of the prefix value to match.
Returns
results object that contains all matching key-value pairs. The results are sorted by the key in ascending order.

◆ save_state()

template<typename KeyTraits , typename ValueT >
template<typename FuncT = trie::value_serializer<value_type>>
void mdds::packed_trie_map< KeyTraits, ValueT >::save_state ( std::ostream &  os) const

Save the state of the instance of this class to an external buffer.

Parameters
osoutput stream to write the state to.

◆ size()

template<typename KeyTraits , typename ValueT >
size_type mdds::packed_trie_map< KeyTraits, ValueT >::size ( ) const
noexcept

Return the number of entries in the map.

Returns
the number of entries in the map.