mdds
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Friends | List of all members
mdds::trie_map< KeyT, ValueT, TraitsT > Class Template Reference

#include <trie_map.hpp>

Classes

class  const_node_type
 

Public Types

using traits_type = TraitsT
 
typedef packed_trie_map< KeyT, ValueT, TraitsT > packed_type
 
typedef KeyT key_type
 
typedef key_type::value_type key_unit_type
 
typedef ValueT value_type
 
typedef size_t size_type
 
using const_iterator = trie::detail::const_iterator< trie_map >
 
using iterator = trie::detail::iterator< trie_map >
 
typedef trie::detail::search_results< trie_mapsearch_results
 

Public Member Functions

 trie_map ()
 
 trie_map (const trie_map &other)
 
 trie_map (trie_map &&other)
 
const_iterator begin () const
 
iterator begin ()
 
const_iterator end () const
 
iterator end ()
 
trie_mapoperator= (trie_map other)
 
bool operator== (const trie_map &other) const
 
bool operator!= (const trie_map &other) const
 
void swap (trie_map &other)
 
const_node_type root_node () const
 
void insert (const key_type &key, value_type value)
 
void insert (const key_unit_type *key, size_type len, value_type value)
 
bool erase (const key_unit_type *key, size_type len)
 
const_iterator find (const key_type &key) const
 
const_iterator find (const key_unit_type *input, size_type len) const
 
iterator find (const key_type &key)
 
iterator find (const key_unit_type *input, size_type len)
 
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
 
bool empty () const noexcept
 
void clear ()
 
packed_type pack ()
 

Friends

class packed_trie_map< KeyT, ValueT, TraitsT >
 
class trie::detail::iterator_base< trie_map, true >
 
class trie::detail::iterator_base< trie_map, false >
 
class trie::detail::const_iterator< trie_map >
 
class trie::detail::iterator< trie_map >
 
class trie::detail::search_results< trie_map >
 

Detailed Description

template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits>
class mdds::trie_map< KeyT, ValueT, TraitsT >

Trie map provides storage for multiple key-value pairs where keys are either strings, or otherwise consist of arrays of characters. The keys are stored in an ordered tree structure known as trie, or sometimes referred to as prefix tree.

Constructor & Destructor Documentation

◆ trie_map()

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
mdds::trie_map< KeyT, ValueT, TraitsT >::trie_map ( )

Default constructor.

Member Function Documentation

◆ clear()

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
void mdds::trie_map< KeyT, ValueT, TraitsT >::clear ( )

Empty the container.

◆ erase()

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
bool mdds::trie_map< KeyT, ValueT, TraitsT >::erase ( const key_unit_type *  key,
size_type  len 
)

Erase a key and the value associated with it.

Parameters
keypointer to the first character of a character array that stores key value.
lenlength of the character array storing the key.
Returns
true if a key is erased, false otherwise.

◆ find() [1/4]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
iterator mdds::trie_map< KeyT, ValueT, TraitsT >::find ( const key_type &  key)

Find a value associated with a specified key.

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

◆ find() [2/4]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
const_iterator mdds::trie_map< KeyT, ValueT, TraitsT >::find ( const key_type &  key) const

Find a value associated with a specified key.

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

◆ find() [3/4]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
iterator mdds::trie_map< KeyT, ValueT, TraitsT >::find ( const key_unit_type *  input,
size_type  len 
)

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
mutable iterator that references a value associated with the key, or the end position in case the key is not found.

◆ find() [4/4]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
const_iterator mdds::trie_map< KeyT, ValueT, TraitsT >::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
immutable iterator that references a value associated with the key, or the end position in case the key is not found.

◆ insert() [1/2]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
void mdds::trie_map< KeyT, ValueT, TraitsT >::insert ( const key_type &  key,
value_type  value 
)

Insert a new key-value pair.

Parameters
keykey value.
valuevalue to associate with the key.

◆ insert() [2/2]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
void mdds::trie_map< KeyT, ValueT, TraitsT >::insert ( const key_unit_type *  key,
size_type  len,
value_type  value 
)

Insert a new key-value pair.

Parameters
keypointer to the first character of a character array that stores key value.
lenlength of the character array storing the key.
valuevalue to associate with the key.

◆ pack()

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
packed_type mdds::trie_map< KeyT, ValueT, TraitsT >::pack ( )

Create a compressed and immutable version of the container which provides better search performance and requires much less memory footprint.

Note
Calling this method will move all stored values into the packed variant. You should make a copy of the instance first if you need to preserve the original.
Returns
an instance of mdds::packed_trie_map with the same content, with all the values stored in the original instance moved into the returned instance.
Exceptions
mdds::size_errorWhen the number of entries exceeds maximum allowed number of key-value pairs. See trie::default_traits::pack_value_type for more detailed explanation.

◆ prefix_search() [1/2]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
search_results mdds::trie_map< KeyT, ValueT, TraitsT >::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 that contains all matching key-value pairs. The results are sorted by the key in ascending order.

◆ prefix_search() [2/2]

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
search_results mdds::trie_map< KeyT, ValueT, TraitsT >::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.

◆ root_node()

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
const_node_type mdds::trie_map< KeyT, ValueT, TraitsT >::root_node ( ) const

Obtain a root node of the trie to traverse it node-by-node.

Returns
Root node of the trie.

◆ size()

template<typename KeyT , typename ValueT , typename TraitsT = trie::default_traits>
size_type mdds::trie_map< KeyT, ValueT, TraitsT >::size ( ) const

Return the number of entries in the map.

Returns
the number of entries in the map.