Overview     Usage     Performance Notes     Links tst 0.68 - 23 Jan 2009

structured_map 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_map< KeyT, DataT, CompT, AllocT >

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

Structured Map 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 Map is a Pair Associative Container, meaning that its value type is pair<const Key, T>. It is also a Unique Associative Container, meaning that no two elements are the same.

A std::map is normally backed by a binary tree. A structured map 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_map, and several times faster than most std::map 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
< tst_iterator_base,
iterators::nonconst_traits
< value_type > > 
iterator
typedef
iterators::iterator_wrapper
< tst_iterator_base,
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_map ()
 structured_map (const char_compare &comp)
 structured_map (const char_compare &comp, const allocator_type &alloc)
template<class InputIterator>
 structured_map (InputIterator first, InputIterator last, const char_compare &comp=char_compare(), const allocator_type &alloc=allocator_type())
 structured_map (const structured_map &other)
 ~structured_map ()
structured_mapoperator= (const structured_map &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
Element access
mapped_typeoperator[] (const key_type &key)
Modifiers
std::pair< iterator, bool > 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_map &other)
void clear ()
Container comparison.
bool operator== (const structured_map &rhs) const
bool operator< (const structured_map &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, iteratorequal_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, iteratorprefix_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, const CharIter last)
 See ternary_tree::longest_match.
template<class CharIter>
const_iterator longest_match (CharIter &first, 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_map< KeyT, DataT, CompT, AllocT > &x, const structured_map< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator!= (const structured_map< KeyT, DataT, CompT, AllocT > &x, const structured_map< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator< (const structured_map< KeyT, DataT, CompT, AllocT > &x, const structured_map< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator> (const structured_map< KeyT, DataT, CompT, AllocT > &x, const structured_map< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator<= (const structured_map< KeyT, DataT, CompT, AllocT > &x, const structured_map< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator>= (const structured_map< KeyT, DataT, CompT, AllocT > &x, const structured_map< KeyT, DataT, CompT, AllocT > &y)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator== (typename structured_map< KeyT, DataT, CompT, AllocT >::const_iterator &a, typename structured_map< KeyT, DataT, CompT, AllocT >::const_iterator &b)
template<class KeyT, class DataT, class CompT, class AllocT>
bool operator!= (typename structured_map< KeyT, DataT, CompT, AllocT >::const_iterator &a, typename structured_map< 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 std::reverse_iterator<iterator> reverse_iterator

typedef std::reverse_iterator<const_iterator> const_reverse_iterator

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_map (  )  [inline]

structured_map ( const char_compare comp  )  [inline, explicit]

structured_map ( const char_compare comp,
const allocator_type alloc 
) [inline]

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

structured_map ( const structured_map< KeyT, DataT, CompT, AllocT > &  other  )  [inline]

~structured_map (  )  [inline]


Member Function Documentation

structured_map& operator= ( const structured_map< 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]

mapped_type& operator[] ( const key_type key  )  [inline]

std::pair<iterator, bool> 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_map< KeyT, DataT, CompT, AllocT > &  other  )  [inline]

void clear (  )  [inline]

bool operator== ( const structured_map< KeyT, DataT, CompT, AllocT > &  rhs  )  const [inline]

bool operator< ( const structured_map< 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]

std::pair<const_iterator, const_iterator> prefix_range ( const key_type key  )  const [inline]

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

const_iterator longest_match ( CharIter &  first,
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]

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

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

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_map< KeyT, DataT, CompT, AllocT > &  x,
const structured_map< KeyT, DataT, CompT, AllocT > &  y 
) [related]

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

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

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

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

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

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

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


ternary_tree 0.68 -- by rasmus ekman -- Page generated with Doxygen 1.5.6 on 23 Jan 2009