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 ()=delete
	packed_trie_map (const entry *entries, size_type entry_size)
	packed_trie_map (const trie_map< key_trait_type, value_type > &other)
const_iterator	begin () const
const_iterator	end () 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

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/3]

template<typename _KeyTrait , typename _ValueT >

mdds::packed_trie_map< _KeyTrait, _ValueT >::packed_trie_map ( )

delete

Not implemented.

packed_trie_map() [2/3]

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.
null_value	null value to return when the find method fails to find a matching entry.

packed_trie_map() [3/3]

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

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.

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.

size()

template<typename _KeyTrait , typename _ValueT >

size_type mdds::packed_trie_map< _KeyTrait, _ValueT >::size

(

)

const

Return the number of entries in the map.

Returns

the number of entries in the map.