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

#include <trie_map.hpp>

Classes

struct  entry
 

Public Types

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

 packed_trie_map ()=delete
 
 packed_trie_map (const entry *entries, size_type entry_size, value_type null_value)
 
 packed_trie_map (const trie_map< key_trait_type, value_type > &other)
 
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
 

Detailed Description

template<typename _KeyTrait, typename _ValueT>
class mdds::packed_trie_map< _KeyTrait, _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

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

Not implemented.

template<typename _KeyTrait , typename _ValueT >
mdds::packed_trie_map< _KeyTrait, _ValueT >::packed_trie_map ( const entry entries,
size_type  entry_size,
value_type  null_value 
)

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.
null_valuenull value to return when the find method fails to find a matching entry.
template<typename _KeyTrait , typename _ValueT >
mdds::packed_trie_map< _KeyTrait, _ValueT >::packed_trie_map ( const trie_map< key_trait_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

template<typename _KeyTrait , typename _ValueT >
value_type mdds::packed_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 >
std::vector<key_value_type> mdds::packed_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::packed_trie_map< _KeyTrait, _ValueT >::size ( ) const

Return the number of entries in the map.

Returns
the number of entries in the map.