Loading...
Searching...
No Matches
mdds::packed_trie_map< KeyT, ValueT, TraitsT > Class Template Reference

`#include <trie_map.hpp>`

## Classes

struct | entry
class | const_node_type

## Public Types

using | traits_type = TraitsT
typedef KeyT | key_type
typedef key_type::value_type | key_unit_type
typedef ValueT | value_type
typedef size_t | size_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< KeyT, ValueT, TraitsT > &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)
const_node_type | root_node () const
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)
std::string | dump_structure (trie::dump_structure_type type) const

## Friends

class | trie::detail::packed_iterator_base< packed_trie_map >
class | trie::detail::packed_search_results< packed_trie_map >
class | trie_map< KeyT, ValueT, TraitsT >
struct | trie::detail::dump_packed_buffer< packed_trie_map, packed_type >

## Detailed Description

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

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 KeyT, typename ValueT, typename TraitsT = trie::default_traits>

mdds::packed_trie_map< KeyT, ValueT, TraitsT >::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

  entries | pointer to the array of key-value entries.
  entry_size | size of the key-value entry array.

Exceptions

  mdds::size_error | When the number of entries exceeds maximum allowed number of key-value pairs. See trie::default_traits::pack_value_type for more detailed explanation.

## packed_trie_map() [2/2]

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

mdds::packed_trie_map< KeyT, ValueT, TraitsT >::packed_trie_map | ( | const trie_map< KeyT, ValueT, TraitsT > & | other | ) |

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

Parameters

  other | mdds::trie_map instance to build content from.

Exceptions

  mdds::size_error | When the number of entries exceeds maximum allowed number of key-value pairs. See trie::default_traits::pack_value_type for more detailed explanation.

## Member Function Documentation

## dump_structure()

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

std::string mdds::packed_trie_map< KeyT, ValueT, TraitsT >::dump_structure | ( | trie::dump_structure_type | type | ) | const

Dump the structure of the trie content in a specified human-readable textural format.

Parameters

  type | Output format type.

## find() [1/2]

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

const_iterator mdds::packed_trie_map< KeyT, ValueT, TraitsT >::find | ( | const key_type & | key | ) | const

Find a value associated with a specified key.

Parameters

  key | key 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 KeyT, typename ValueT, typename TraitsT = trie::default_traits>

const_iterator mdds::packed_trie_map< KeyT, ValueT, TraitsT >::find | ( | const key_unit_type * | input,
|  | size_type | len ) const

Find a value associated with a specified key.

Parameters

  input | pointer to an array whose value represents the key to match.
  len | length 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 KeyT, typename ValueT, typename TraitsT = trie::default_traits>
template<typename FuncT = trie::value_serializer<value_type>>

void mdds::packed_trie_map< KeyT, ValueT, TraitsT >::load_state | ( | std::istream & | is | ) |

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

Parameters

  is | input stream to load the state from.

## prefix_search() [1/2]

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

search_results mdds::packed_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

  prefix | prefix to match.

Returns
  results object containing all matching key-value pairs.

## prefix_search() [2/2]

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

search_results mdds::packed_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

  prefix | pointer to an array whose value represents the prefix to match.
  len | length 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::packed_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.

## save_state()

template<typename KeyT, typename ValueT, typename TraitsT = trie::default_traits>
template<typename FuncT = trie::value_serializer<value_type>>

void mdds::packed_trie_map< KeyT, ValueT, TraitsT >::save_state | ( | std::ostream & | os | ) | const

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

Parameters

  os | output stream to write the state to.

## size()

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

size_type mdds::packed_trie_map< KeyT, ValueT, TraitsT >::size | ( |  | ) | const

noexcept

Return the number of entries in the map.

Returns
  the number of entries in the map.