Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Protected Types
Saf::Collection::TreeMap< KeyType, ValType, CompType > Class Template Reference

Ordered associative container. More...

#include <TreeMap.h>

Inheritance diagram for Saf::Collection::TreeMap< KeyType, ValType, CompType >:
Saf::Algo::Struct::RedBlackTree< KeyType, Pair< const KeyType, ValType >, Algo::Selector::FirstMember< Pair< const KeyType, ValType > >, CompType >

List of all members.

Public Types

typedef BaseType::ConstIterator ConstIterator
typedef BaseType::Iterator Iterator

Public Member Functions

 TreeMap ()
 Constructor.
 TreeMap (const MyType &m)
 Copy constructor.
ValType & At (const KeyType &key)
 Get a reference to the value corresponding to a given key.
const ValType & At (const KeyType &key) const
 Get a reference to the value corresponding to a given key.
MyTypeoperator= (const MyType &m)
 Assignment operator.
ValType & operator[] (const KeyType &key)
 Operator returning the reference to the value corresponding to a given key.
MyTypeSwap (MyType &m)
 Swap the content of two tree maps.
Iterator Update (const KeyType &key, const ValType &val)
 Update the value corresponding to a given key.

Protected Types

typedef
Algo::Struct::RedBlackTree
< KeyType, RecType,
Algo::Selector::FirstMember
< RecType >, CompType > 
BaseType
typedef TreeMap< KeyType,
ValType, CompType > 
MyType
typedef Pair< const KeyType,
ValType > 
RecType

Detailed Description

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
class Saf::Collection::TreeMap< KeyType, ValType, CompType >

Ordered associative container.

This class implements an associative container where keys map to values. Internally, the data is stored in a sorted order in a red/black tree enabling insert, erase and look-up of the values in guaranteed logarithmic time.

Iterator category: Bidirectional.

Template Parameters:
KeyTypeKey data type. Each key can appear only once in the map.
ValTypeData type of the mapped values.
CompTypeA binary comparison predicate inducing a strict weak ordering on KeyType values.
See also:
Algo::Struct::RedBlackTree, Collection::HashMap.

Member Typedef Documentation

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
typedef Algo::Struct::RedBlackTree<KeyType,RecType,Algo::Selector::FirstMember<RecType>,CompType> Saf::Collection::TreeMap< KeyType, ValType, CompType >::BaseType [protected]
template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
typedef BaseType::ConstIterator Saf::Collection::TreeMap< KeyType, ValType, CompType >::ConstIterator
template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
typedef BaseType::Iterator Saf::Collection::TreeMap< KeyType, ValType, CompType >::Iterator
template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
typedef TreeMap<KeyType,ValType,CompType> Saf::Collection::TreeMap< KeyType, ValType, CompType >::MyType [protected]
template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
typedef Pair<const KeyType,ValType> Saf::Collection::TreeMap< KeyType, ValType, CompType >::RecType [protected]

Constructor & Destructor Documentation

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
Saf::Collection::TreeMap< KeyType, ValType, CompType >::TreeMap ( ) [inline]

Constructor.

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
Saf::Collection::TreeMap< KeyType, ValType, CompType >::TreeMap ( const MyType m) [inline]

Copy constructor.


Member Function Documentation

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
ValType& Saf::Collection::TreeMap< KeyType, ValType, CompType >::At ( const KeyType &  key) [inline]

Get a reference to the value corresponding to a given key.

If the key does not exist in the TreeMap then an IndexOutOfRangeException is thrown.

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
const ValType& Saf::Collection::TreeMap< KeyType, ValType, CompType >::At ( const KeyType &  key) const [inline]

Get a reference to the value corresponding to a given key.

If the key does not exist in the TreeMap then an IndexOutOfRangeException is thrown.

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
MyType& Saf::Collection::TreeMap< KeyType, ValType, CompType >::operator= ( const MyType m) [inline]

Assignment operator.

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
ValType& Saf::Collection::TreeMap< KeyType, ValType, CompType >::operator[] ( const KeyType &  key) [inline]

Operator returning the reference to the value corresponding to a given key.

If the key does not exist in the TreeMap then it is created and the corresponding value is initialized using a default constructor.

template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
MyType& Saf::Collection::TreeMap< KeyType, ValType, CompType >::Swap ( MyType m) [inline]

Swap the content of two tree maps.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class KeyType, class ValType, class CompType = Algo::Predicate::Less<KeyType>>
Iterator Saf::Collection::TreeMap< KeyType, ValType, CompType >::Update ( const KeyType &  key,
const ValType &  val 
) [inline]

Update the value corresponding to a given key.

If the key exists in the TreeMap then its corresponding value is updated. Otherwise a new pair is inserted into the TreeMap.

Remarks:
In general, should be a little bit faster than using map[key] = val.

The documentation for this class was generated from the following file: