structured_multimap Class Template Reference

List of all members.

---

Detailed Description

template<class KeyT, class DataT, class CompT = std::less<typename KeyT::value_type>, class AllocT = std::allocator<std::pair<const KeyT, DataT> >>
class containers::structured_multimap< KeyT, DataT, CompT, AllocT >

Structured Multimap is a Sorted Associative Container that stores objects of type pair<Key, Data>.

Structured Multimap is a Structured Container, meaning that its key type is required to be a Forward Container, and that the map uses a comparator to establish a strict weak ordering among key::value_type elements (rather than on whole keys). This allows searches in the set involving parts of keys, ie with shared prefix or with shared middle parts.

Structured Multimap is a Pair Associative Container, meaning that its value type is pair<const Key, T>. It is also a Multiple Associative Container, meaning that more than one elements can be stored under the same key.

A std::multimap is normally backed by a binary tree. A structured multimap is instead backed by a ternary_tree, which manages structured ordering of keys. For string-like keys, a ternary tree is typically as fast as an unordered_multimap, and several times faster than most std::multimap implementations.

Public Types
enum	constants { wildcard_char = ternary_tree::wildcard_char }
	Default for partial_match_search ('?'). More...
typedef KeyT	key_type
typedef DataT	mapped_type
typedef std::pair< const KeyT, DataT >	value_type
typedef KeyT::value_type	char_type
typedef CompT	char_compare
typedef AllocT	allocator_type
typedef AllocT::difference_type	difference_type
typedef AllocT::size_type	size_type
typedef AllocT::pointer	pointer
typedef AllocT::const_pointer	const_pointer
typedef AllocT::reference	reference
typedef AllocT::const_reference	const_reference
typedef ternary_tree::key_compare	key_compare
typedef iterators::iterator_wrapper < multimap_iterator, iterators::nonconst_traits < value_type > >	iterator
typedef iterators::iterator_wrapper < multimap_iterator, iterators::const_traits < value_type > >	const_iterator
typedef std::reverse_iterator < iterator >	reverse_iterator
typedef std::reverse_iterator < const_iterator >	const_reverse_iterator
typedef search_results_list < ternary_tree, iterator >	search_results_list
	Results from partial_match_search and hamming_search.
Public Member Functions
Construct, copy, destroy
	structured_multimap ()
	structured_multimap (const char_compare &comp)
	structured_multimap (const char_compare &comp, const allocator_type &alloc)
template<class InputIterator>
	structured_multimap (InputIterator first, InputIterator last, const char_compare &comp=char_compare(), const allocator_type &alloc=allocator_type())
	structured_multimap (const structured_multimap &other)
	~structured_multimap ()
structured_multimap &	operator= (const structured_multimap &other)
allocator_type	get_allocator () const
Iterators
Includes C++0x methods cbegin, cend, crbegin, crend to make it easier to access const iterators.
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
reverse_iterator	rbegin ()
const_reverse_iterator	rbegin () const
reverse_iterator	rend ()
const_reverse_iterator	rend () const
const_iterator	cbegin () const
const_iterator	cend () const
const_reverse_iterator	crbegin () const
const_reverse_iterator	crend () const
Capacity
bool	empty () const
size_type	size () const
size_type	max_size () const
Modifiers
iterator	insert (const value_type &val)
iterator	insert (iterator where, const value_type &val)
template<class InputIterator>
void	insert (InputIterator first, InputIterator last)
iterator	erase (iterator pos)
size_type	erase (const key_type &key)
iterator	erase (iterator first, iterator last)
void	swap (structured_multimap &other)
void	clear ()
Container comparison.
bool	operator== (const structured_multimap &rhs) const
bool	operator< (const structured_multimap &rhs) const
Observers
char_compare	char_comp () const
	Returns a copy of the key element comparator object.
key_compare	key_comp () const
	Returns a copy of the key_compare class; this is defined in terms of a lexicographical_compare using the char_compare object.
value_compare	value_comp () const
Map operations
iterator	find (const key_type &key)
const_iterator	find (const key_type &key) const
size_type	count (const key_type &key) const
iterator	lower_bound (const key_type &key)
iterator	upper_bound (const key_type &key)
const_iterator	lower_bound (const key_type &key) const
const_iterator	upper_bound (const key_type &key) const
std::pair< iterator, iterator >	equal_range (const key_type &key)
std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
Structured search operations [deprecated]
The interface for structure searches remains to be defined. See ternary_tree Structured Search section
std::pair< iterator, iterator >	prefix_range (const key_type &key)
	See ternary_tree::prefix_range.
std::pair< const_iterator, const_iterator >	prefix_range (const key_type &key) const
template<class CharIter>
iterator	longest_match (CharIter &first, CharIter last)
	See ternary_tree::longest_match.
template<class CharIter>
const_iterator	longest_match (CharIter &first, const CharIter last) const
search_results_list	create_search_results () const
	Required for partial_match_search and hamming_search calls.
template<class OutputIter>
OutputIter	partial_match_search (const key_type &key, OutputIter results, char_type wildcard=wildcard_char) const
	See ternary_tree::partial_match_search.
template<class OutputIter>
OutputIter	hamming_search (const key_type &key, OutputIter results, size_type dist) const
	See ternary_tree::hamming_search.
template<class OutputIter>
OutputIter	levenshtein_search (const key_type &key, OutputIter results, size_type dist) const
	See ternary_tree::levenshtein_search.
template<class OutputIter>
OutputIter	combinatorial_search (const key_type &key, OutputIter results, size_type wildcards=0) const
	See ternary_tree::combinatorial_search (not part of Structured container interface).
Related Functions
(Note that these are not member functions.)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator== (const structured_multimap< KeyT, DataT, CompT, AllocT > &x, const structured_multimap< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator!= (const structured_multimap< KeyT, DataT, CompT, AllocT > &x, const structured_multimap< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator< (const structured_multimap< KeyT, DataT, CompT, AllocT > &x, const structured_multimap< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator> (const structured_multimap< KeyT, DataT, CompT, AllocT > &x, const structured_multimap< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator<= (const structured_multimap< KeyT, DataT, CompT, AllocT > &x, const structured_multimap< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator>= (const structured_multimap< KeyT, DataT, CompT, AllocT > &x, const structured_multimap< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator== (typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &a, typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &b)
template<class KeyT, class DataT, class CompT, class AllocT>
bool	operator!= (typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &a, typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &b)
Classes
class	value_compare
	Value comparator, applying the key_compare to the key part of value_type. More...

---

Member Typedef Documentation

typedef KeyT key_type

typedef DataT mapped_type

typedef std::pair<const KeyT, DataT> value_type

typedef KeyT::value_type char_type

typedef CompT char_compare

typedef AllocT allocator_type

typedef AllocT::difference_type difference_type

typedef AllocT::size_type size_type

typedef AllocT::pointer pointer

typedef AllocT::const_pointer const_pointer

typedef AllocT::reference reference

typedef AllocT::const_reference const_reference

typedef ternary_tree::key_compare key_compare

typedef iterators::iterator_wrapper< multimap_iterator , iterators::nonconst_traits<value_type> > iterator

typedef iterators::iterator_wrapper< multimap_iterator , iterators::const_traits<value_type> > const_iterator

typedef std::reverse_iterator<iterator> reverse_iterator

typedef std::reverse_iterator<const_iterator> const_reverse_iterator

typedef search_results_list<ternary_tree, iterator> search_results_list

Results from partial_match_search and hamming_search.

---

Member Enumeration Documentation

enum constants

Default for partial_match_search ('?').

Enumerator:

wildcard_char

---

Constructor & Destructor Documentation

structured_multimap

(

)

[inline]

structured_multimap

(

const char_compare &

comp

)

[inline, explicit]

structured_multimap	(	const char_compare &	comp,
		const allocator_type &	alloc
	)			[inline]

structured_multimap	(	InputIterator	first,
		InputIterator	last,
		const char_compare &	comp = char_compare(),
		const allocator_type &	alloc = allocator_type()
	)			[inline]

structured_multimap

(

const structured_multimap< KeyT, DataT, CompT, AllocT > &

other

)

[inline]

~structured_multimap

(

)

[inline]

---

Member Function Documentation

structured_multimap& operator=

(

const structured_multimap< KeyT, DataT, CompT, AllocT > &

other

)

[inline]

allocator_type get_allocator

(

)

const [inline]

iterator begin

(

)

[inline]

const_iterator begin

(

)

const [inline]

iterator end

(

)

[inline]

const_iterator end

(

)

const [inline]

reverse_iterator rbegin

(

)

[inline]

const_reverse_iterator rbegin

(

)

const [inline]

reverse_iterator rend

(

)

[inline]

const_reverse_iterator rend

(

)

const [inline]

const_iterator cbegin

(

)

const [inline]

const_iterator cend

(

)

const [inline]

const_reverse_iterator crbegin

(

)

const [inline]

const_reverse_iterator crend

(

)

const [inline]

bool empty

(

)

const [inline]

size_type size

(

)

const [inline]

size_type max_size

(

)

const [inline]

iterator insert

(

const value_type &

val

)

[inline]

iterator insert	(	iterator	where,
		const value_type &	val
	)			[inline]

void insert	(	InputIterator	first,
		InputIterator	last
	)			[inline]

iterator erase

(

iterator

pos

)

[inline]

size_type erase

(

const key_type &

key

)

[inline]

iterator erase	(	iterator	first,
		iterator	last
	)			[inline]

void swap

(

structured_multimap< KeyT, DataT, CompT, AllocT > &

other

)

[inline]

void clear

(

)

[inline]

bool operator==

(

const structured_multimap< KeyT, DataT, CompT, AllocT > &

rhs

)

const [inline]

bool operator<

(

const structured_multimap< KeyT, DataT, CompT, AllocT > &

rhs

)

const [inline]

char_compare char_comp

(

)

const [inline]

Returns a copy of the key element comparator object.

key_compare key_comp

(

)

const [inline]

Returns a copy of the key_compare class; this is defined in terms of a lexicographical_compare using the char_compare object.

value_compare value_comp

(

)

const [inline]

iterator find

(

const key_type &

key

)

[inline]

const_iterator find

(

const key_type &

key

)

const [inline]

size_type count

(

const key_type &

key

)

const [inline]

iterator lower_bound

(

const key_type &

key

)

[inline]

iterator upper_bound

(

const key_type &

key

)

[inline]

const_iterator lower_bound

(

const key_type &

key

)

const [inline]

const_iterator upper_bound

(

const key_type &

key

)

const [inline]

std::pair<iterator, iterator> equal_range

(

const key_type &

key

)

[inline]

std::pair<const_iterator, const_iterator> equal_range

(

const key_type &

key

)

const [inline]

std::pair<iterator, iterator> prefix_range

(

const key_type &

key

)

[inline]

See ternary_tree::prefix_range.

std::pair<const_iterator, const_iterator> prefix_range

(

const key_type &

key

)

const [inline]

iterator longest_match	(	CharIter &	first,
		CharIter	last
	)			[inline]

See ternary_tree::longest_match.

const_iterator longest_match	(	CharIter &	first,
		const CharIter	last
	)			const [inline]

search_results_list create_search_results

(

)

const [inline]

Required for partial_match_search and hamming_search calls.

OutputIter partial_match_search	(	const key_type &	key,
		OutputIter	results,
		char_type	wildcard = wildcard_char
	)			const [inline]

See ternary_tree::partial_match_search.

OutputIter hamming_search	(	const key_type &	key,
		OutputIter	results,
		size_type	dist
	)			const [inline]

See ternary_tree::hamming_search.

OutputIter levenshtein_search	(	const key_type &	key,
		OutputIter	results,
		size_type	dist
	)			const [inline]

See ternary_tree::levenshtein_search.

OutputIter combinatorial_search	(	const key_type &	key,
		OutputIter	results,
		size_type	wildcards = 0
	)			const [inline]

See ternary_tree::combinatorial_search (not part of Structured container interface).

---

Friends And Related Function Documentation

bool operator==	(	const structured_multimap< KeyT, DataT, CompT, AllocT > &	x,
		const structured_multimap< KeyT, DataT, CompT, AllocT > &	y
	)			[related]

bool operator!=	(	const structured_multimap< KeyT, DataT, CompT, AllocT > &	x,
		const structured_multimap< KeyT, DataT, CompT, AllocT > &	y
	)			[related]

bool operator<	(	const structured_multimap< KeyT, DataT, CompT, AllocT > &	x,
		const structured_multimap< KeyT, DataT, CompT, AllocT > &	y
	)			[related]

bool operator>	(	const structured_multimap< KeyT, DataT, CompT, AllocT > &	x,
		const structured_multimap< KeyT, DataT, CompT, AllocT > &	y
	)			[related]

bool operator<=	(	const structured_multimap< KeyT, DataT, CompT, AllocT > &	x,
		const structured_multimap< KeyT, DataT, CompT, AllocT > &	y
	)			[related]

bool operator>=	(	const structured_multimap< KeyT, DataT, CompT, AllocT > &	x,
		const structured_multimap< KeyT, DataT, CompT, AllocT > &	y
	)			[related]

bool operator==	(	typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &	a,
		typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &	b
	)			[related]

bool operator!=	(	typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &	a,
		typename structured_multimap< KeyT, DataT, CompT, AllocT >::const_iterator &	b
	)			[related]