mdds
Classes | Public Types | Public Member Functions | Friends | List of all members
mdds::trie_map< _KeyTrait, _ValueT > Class Template Reference

#include <trie_map.hpp>

Public Types

typedef packed_trie_map< _KeyTrait, _ValueT > packed_type
 
typedef _KeyTrait key_trait_type
 
typedef key_trait_type::string_type string_type
 
typedef key_trait_type::buffer_type buffer_type
 
typedef key_trait_type::char_type char_type
 
typedef _ValueT value_type
 
typedef size_t size_type
 
typedef std::pair< string_type, value_type > key_value_type
 

Public Member Functions

 trie_map ()=delete
 
 trie_map (value_type null_value)
 
void insert (const char_type *key, size_type len, const value_type &value)
 
bool erase (const char_type *key, size_type len)
 
value_type find (const char_type *input, size_type len) const
 
std::vector< key_value_type > prefix_search (const char_type *prefix, size_type len) const
 
size_type size () const
 
void clear ()
 
packed_type pack () const
 

Friends

class packed_trie_map< _KeyTrait, _ValueT >
 

Detailed Description

template<typename _KeyTrait, typename _ValueT>
class mdds::trie_map< _KeyTrait, _ValueT >

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

template<typename _KeyTrait, typename _ValueT>
mdds::trie_map< _KeyTrait, _ValueT >::trie_map ( )
delete

Not implemented.

template<typename _KeyTrait, typename _ValueT>
mdds::trie_map< _KeyTrait, _ValueT >::trie_map ( value_type  null_value)

Constructor.

Parameters
null_valuenull value to return when the find method fails to find a matching entry.

Member Function Documentation

template<typename _KeyTrait, typename _ValueT>
void mdds::trie_map< _KeyTrait, _ValueT >::clear ( )

Empty the container.

template<typename _KeyTrait, typename _ValueT>
bool mdds::trie_map< _KeyTrait, _ValueT >::erase ( const char_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.
template<typename _KeyTrait, typename _ValueT>
value_type mdds::trie_map< _KeyTrait, _ValueT >::find ( const char_type *  input,
size_type  len 
) const

Find a value associated with a specified string key.

Parameters
inputpointer to a C-style string whose value represents the key to match.
lenlength of the matching string value.
Returns
value associated with the key, or the null value in case the key is not found.
template<typename _KeyTrait, typename _ValueT>
void mdds::trie_map< _KeyTrait, _ValueT >::insert ( const char_type *  key,
size_type  len,
const 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.
template<typename _KeyTrait, typename _ValueT>
packed_type mdds::trie_map< _KeyTrait, _ValueT >::pack ( ) const

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

Returns
an instance of mdds::packed_trie_map with the same content.
template<typename _KeyTrait, typename _ValueT>
std::vector<key_value_type> mdds::trie_map< _KeyTrait, _ValueT >::prefix_search ( const char_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 a C-style string whose value represents the prefix to match.
lenlength of the prefix value to match.
Returns
list of all matching key-value pairs sorted by the key in ascending order.
template<typename _KeyTrait, typename _ValueT>
size_type mdds::trie_map< _KeyTrait, _ValueT >::size ( ) const

Return the number of entries in the map.

Returns
the number of entries in the map.