mdds::trie_map< _KeyTrait, _ValueT > Class Template Reference

#include <trie_map.hpp>

Public Types
typedef packed_trie_map< _KeyTrait, _ValueT >	packed_type
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::iterator_base< trie_map >	const_iterator
typedef trie::detail::search_results< trie_map >	search_results

Public Member Functions
	trie_map ()
const_iterator	begin () const
const_iterator	end () const
void	insert (const key_type &key, const value_type &value)
void	insert (const key_unit_type *key, size_type len, const 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
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
void	clear ()
packed_type	pack () const

Friends
class	packed_trie_map< _KeyTrait, _ValueT >
class	trie::detail::iterator_base< trie_map >
class	trie::detail::search_results< trie_map >

Detailed Description

template<typename _KeyTrait, typename _ValueT>
class mdds::trie_map< _KeyTrait, _ValueT >

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 _KeyTrait, typename _ValueT>

mdds::trie_map< _KeyTrait, _ValueT >::trie_map

(

)

Default constructor.

Member Function Documentation

clear()

template<typename _KeyTrait, typename _ValueT>

void mdds::trie_map< _KeyTrait, _ValueT >::clear

(

)

Empty the container.

erase()

template<typename _KeyTrait, typename _ValueT>

bool mdds::trie_map< _KeyTrait, _ValueT >::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/2]

template<typename _KeyTrait, typename _ValueT>

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

insert() [1/2]

template<typename _KeyTrait, typename _ValueT>

void mdds::trie_map< _KeyTrait, _ValueT >::insert	(	const key_type &	key,
		const 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 _KeyTrait, typename _ValueT>

void mdds::trie_map< _KeyTrait, _ValueT >::insert	(	const key_unit_type *	key,
		size_type	len,
		const 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 _KeyTrait, typename _ValueT>

packed_type mdds::trie_map< _KeyTrait, _ValueT >::pack

(

)

const

Create a compressed and immutable version of the container which provides better search performance and requires much less memory footprint.

Returns

an instance of mdds::packed_trie_map with the same content.

prefix_search() [1/2]

template<typename _KeyTrait, typename _ValueT>

search_results mdds::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::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::trie_map< _KeyTrait, _ValueT >::size

(

)

const

Return the number of entries in the map.

Returns

the number of entries in the map.