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::key_type	key_type
typedef key_trait_type::key_buffer_type	key_buffer_type
typedef key_trait_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_trait_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 _Func = trie::value_serializer<value_type>>
void	save_state (std::ostream &os) const
template<typename _Func = 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 >

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

packed_trie_map() [1/2]

template<typename _KeyTrait , typename _ValueT >

mdds::packed_trie_map< _KeyTrait, _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.

Parameters

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

packed_trie_map() [2/2]

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

other

mdds::trie_map instance to build content from.

Member Function Documentation

dump_structure()

template<typename _KeyTrait , typename _ValueT >

void mdds::packed_trie_map< _KeyTrait, _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.

find() [1/2]

template<typename _KeyTrait , typename _ValueT >

const_iterator mdds::packed_trie_map< _KeyTrait, _ValueT >::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 _KeyTrait , typename _ValueT >

const_iterator mdds::packed_trie_map< _KeyTrait, _ValueT >::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 _KeyTrait , typename _ValueT >

template<typename _Func = trie::value_serializer<value_type>>

void mdds::packed_trie_map< _KeyTrait, _ValueT >::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 _KeyTrait , typename _ValueT >

search_results mdds::packed_trie_map< _KeyTrait, _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.

Parameters

prefix

prefix to match.

Returns

results object containing all matching key-value pairs.

prefix_search() [2/2]

template<typename _KeyTrait , typename _ValueT >

search_results mdds::packed_trie_map< _KeyTrait, _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.

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.

save_state()

template<typename _KeyTrait , typename _ValueT >

template<typename _Func = trie::value_serializer<value_type>>

void mdds::packed_trie_map< _KeyTrait, _ValueT >::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 _KeyTrait , typename _ValueT >

size_type mdds::packed_trie_map< _KeyTrait, _ValueT >::size ( ) const

noexcept

Return the number of entries in the map.

Returns

the number of entries in the map.