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 >:

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.
MyType &	operator= (const MyType &m)
	Assignment operator.
ValType &	operator[] (const KeyType &key)
	Operator returning the reference to the value corresponding to a given key.
MyType &	Swap (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:

KeyType	Key data type. Each key can appear only once in the map.
ValType	Data type of the mapped values.
CompType	A 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]

Reimplemented from Saf::Algo::Struct::RedBlackTree< KeyType, Pair< const KeyType, ValType >, Algo::Selector::FirstMember< Pair< const KeyType, ValType > >, CompType >.

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

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:

• Saf/Collection/TreeMap.h