mdds
|
#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_map > | const_iterator |
typedef trie::detail::packed_search_results< packed_trie_map > | search_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_map & | operator= (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 > |
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.
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.
entries | pointer to the array of key-value entries. |
entry_size | size of the key-value entry array. |
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.
other | mdds::trie_map instance to build content from. |
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.
const_iterator mdds::packed_trie_map< KeyTraits, ValueT >::find | ( | const key_type & | key | ) | const |
Find a value associated with a specified key.
key | key to match. |
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.
input | pointer to an array whose value represents the key to match. |
len | length of the matching key value. |
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.
is | input stream to load the state from. |
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.
prefix | prefix to match. |
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.
prefix | pointer to an array whose value represents the prefix to match. |
len | length of the prefix value to match. |
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.
os | output stream to write the state to. |
|
noexcept |
Return the number of entries in the map.