L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC > Class Template Reference

AVL tree based associative container. More...

#include <avl_map>

+ Inheritance diagram for cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >:
+ Collaboration diagram for cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >:

Public Types

typedef COMPARE< KEY_TYPE > Key_compare
 Type of the comparison functor.
 
typedef KEY_TYPE Key_type
 Type of the key values.
 
typedef DATA_TYPE Data_type
 Type of the data values.
 
typedef Base_type::Node Node
 Return type for find.
 
typedef Base_type::Node_allocator Node_allocator
 Type of the allocator.
 
- Public Types inherited from cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >
enum  { E_noent = 2 , E_exist = 17 , E_nomem = 12 , E_inval = 22 }
 Return status constants. More...
 
typedef ITEM_TYPE Item_type
 Type for the items store in the set.
 
typedef GET_KEY Get_key
 Key-getter type to derive the sort key of an internal node.
 
typedef GET_KEY::Key_type Key_type
 Type of the sort key used for the items.
 
typedef Type_traits< Item_type >::Const_type Const_item_type
 Type used for const items within the set.
 
typedef COMPARE Item_compare
 Type for the comparison functor.
 
typedef ALLOC< _Node > Node_allocator
 Type for the node allocator.
 
typedef Avl_set_iter< _Node, Item_type, Fwd > Iterator
 Forward iterator for the set.
 
typedef Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
 Constant forward iterator for the set.
 
typedef Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
 Backward iterator for the set.
 
typedef Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
 Constant backward iterator for the set.
 

Public Member Functions

 Avl_map (Node_allocator const &alloc=Node_allocator())
 Create an empty AVL-tree based map.
 
cxx::Pair< Iterator, int > insert (Key_type const &key, Data_type const &data)
 Insert a <key, data> pair into the map.
 
Data_type const & operator[] (Key_type const &key) const
 Get the data for the given key.
 
Data_typeoperator[] (Key_type const &key)
 Get or insert data for the given key.
 
- Public Member Functions inherited from cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >
 Base_avl_set (Node_allocator const &alloc=Node_allocator())
 Create a AVL-tree based set.
 
 Base_avl_set (Base_avl_set const &o)
 Create a copy of an AVL-tree based set.
 
cxx::Pair< Iterator, int > insert (Item_type const &item)
 Insert an item into the set.
 
int remove (Key_type const &item)
 Remove an item from the set.
 
int erase (Key_type const &item)
 Erase the item with the given key.
 
Node find_node (Key_type const &item) const
 Lookup a node equal to item.
 
Node lower_bound_node (Key_type const &key) const
 Find the first node greater or equal to key.
 
Const_iterator begin () const
 Get the constant forward iterator for the first element in the set.
 
Const_iterator end () const
 Get the end marker for the constant forward iterator.
 
Iterator begin ()
 Get the mutable forward iterator for the first element of the set.
 
Iterator end ()
 Get the end marker for the mutable forward iterator.
 
Const_rev_iterator rbegin () const
 Get the constant backward iterator for the last element in the set.
 
Const_rev_iterator rend () const
 Get the end marker for the constant backward iterator.
 
Rev_iterator rbegin ()
 Get the mutable backward iterator for the last element of the set.
 
Rev_iterator rend ()
 Get the end marker for the mutable backward iterator.
 

Detailed Description

template<typename KEY_TYPE, typename DATA_TYPE, template< typename A > class COMPARE = Lt_functor, template< typename B > class ALLOC = New_allocator>
class cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >

AVL tree based associative container.

Template Parameters
KEY_TYPEType of the key values.
DATA_TYPEType of the data values.
COMPAREType comparison functor for the key values.
ALLOCType of the allocator used for the nodes.

Definition at line 56 of file avl_map.

Constructor & Destructor Documentation

◆ Avl_map()

template<typename KEY_TYPE , typename DATA_TYPE , template< typename A > class COMPARE = Lt_functor, template< typename B > class ALLOC = New_allocator>
cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::Avl_map ( Node_allocator const &  alloc = Node_allocator())
inline

Create an empty AVL-tree based map.

Parameters
allocThe node allocator.

Definition at line 91 of file avl_map.

Member Function Documentation

◆ insert()

template<typename KEY_TYPE , typename DATA_TYPE , template< typename A > class COMPARE = Lt_functor, template< typename B > class ALLOC = New_allocator>
cxx::Pair< Iterator, int > cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::insert ( Key_type const &  key,
Data_type const &  data 
)
inline

Insert a <key, data> pair into the map.

Parameters
keyThe key value.
dataThe data value to insert.
Returns
A pair of iterator (first) and return value (second). second will be 0 if the element was inserted into the set and -#E_exist if the key was already in the set and the set was therefore not updated. In both cases, first contains an iterator that points to the element. second may also be -#E_nomem when memory for the new node could not be allocated. first is then invalid.

Definition at line 110 of file avl_map.

References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::insert().

Referenced by cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::operator[]().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ operator[]() [1/2]

template<typename KEY_TYPE , typename DATA_TYPE , template< typename A > class COMPARE = Lt_functor, template< typename B > class ALLOC = New_allocator>
Data_type & cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::operator[] ( Key_type const &  key)
inline

Get or insert data for the given key.

Parameters
keyThe key value to use for lookup.
Returns
If the item already exists, a reference to the data item. Otherwise a new data item is default-constructed and inserted under the given key before a reference is returned.

Definition at line 134 of file avl_map.

References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::find_node(), and cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::insert().

+ Here is the call graph for this function:

◆ operator[]() [2/2]

template<typename KEY_TYPE , typename DATA_TYPE , template< typename A > class COMPARE = Lt_functor, template< typename B > class ALLOC = New_allocator>
Data_type const & cxx::Avl_map< KEY_TYPE, DATA_TYPE, COMPARE, ALLOC >::operator[] ( Key_type const &  key) const
inline

Get the data for the given key.

Parameters
keyThe key value to use for lookup.
Precondition
A <key, data> pair for the given key value must exist.

Definition at line 122 of file avl_map.

References cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::find_node().

+ Here is the call graph for this function:

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