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.