Loading...
Searching...
No Matches
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_map > | search_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_map & | operator= (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

  key | pointer to the first character of a character array that stores key value.
  len | length 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

  key | key 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

  key | key 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

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

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

  key | key value.
  value | value 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

  key | pointer to the first character of a character array that stores key value.
  len | length of the character array storing the key.
  value | value 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_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.

## 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

  prefix | prefix 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

  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::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.