Sierra Toolkit Version of the Day
eastl::rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys > Class Template Reference

#include <red_black_tree_eastl.h>

Inheritance diagram for eastl::rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys >:
Collaboration diagram for eastl::rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys >:

List of all members.

Public Types

enum  {
  kKeyAlignment = EASTL_ALIGN_OF(key_type),
  kKeyAlignmentOffset = 0,
  kValueAlignment = EASTL_ALIGN_OF(value_type),
  kValueAlignmentOffset = 0
typedef ptrdiff_t difference_type
typedef eastl_size_t size_type
typedef Key key_type
typedef Value value_type
typedef rbtree_node< value_type > node_type
typedef value_type & reference
typedef const value_type & const_reference
typedef type_select
< bMutableIterators,
rbtree_iterator< value_type,
value_type *, value_type & >
, rbtree_iterator< value_type,
const value_type *, const
value_type & > >::type 
typedef rbtree_iterator
< value_type, const value_type
*, const value_type & > 
< iterator
< const_iterator
typedef Allocator allocator_type
typedef Compare key_compare
typedef type_select
< bUniqueKeys, eastl::pair
< iterator, bool >, iterator >
typedef rbtree< Key, Value,
Compare, Allocator, ExtractKey,
bMutableIterators, bUniqueKeys > 
typedef rb_base< Key, Value,
Compare, ExtractKey,
bUniqueKeys, this_type
typedef integral_constant
< bool, bUniqueKeys > 
typedef base_type::extract_key extract_key

Public Member Functions

 rbtree (const allocator_type &allocator)
 rbtree (const Compare &compare, const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX" rbtree"))
 rbtree (const this_type &x)
template<typename InputIterator >
 rbtree (InputIterator first, InputIterator last, const Compare &compare, const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX" rbtree"))
allocator_type & get_allocator ()
void set_allocator (const allocator_type &allocator)
const key_compare & key_comp () const
key_compare & key_comp ()
this_typeoperator= (const this_type &x)
void swap (this_type &x)
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
bool empty () const
size_type size () const
insert_return_type insert (const value_type &value)
iterator insert (iterator position, const value_type &value)
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
iterator erase (iterator position)
iterator erase (iterator first, iterator last)
reverse_iterator erase (reverse_iterator position)
reverse_iterator erase (reverse_iterator first, reverse_iterator last)
void erase (const key_type *first, const key_type *last)
void clear ()
void reset ()
iterator find (const key_type &key)
const_iterator find (const key_type &key) const
template<typename U , typename Compare2 >
iterator find_as (const U &u, Compare2 compare2)
template<typename U , typename Compare2 >
const_iterator find_as (const U &u, Compare2 compare2) const
iterator lower_bound (const key_type &key)
const_iterator lower_bound (const key_type &key) const
iterator upper_bound (const key_type &key)
const_iterator upper_bound (const key_type &key) const
bool validate () const
int validate_iterator (const_iterator i) const
template<typename InputIterator >
 rbtree (InputIterator first, InputIterator last, const C &compare, const allocator_type &allocator)

Public Attributes

rbtree_node_base mAnchor
size_type mnSize
 This node acts as end() and its mpLeft points to begin(), and mpRight points to rbegin() (the last node on the right).
allocator_type mAllocator
 Stores the count of nodes in the tree (not counting the anchor node).

Protected Member Functions

node_typeDoAllocateNode ()
void DoFreeNode (node_type *pNode)
node_typeDoCreateNodeFromKey (const key_type &key)
node_typeDoCreateNode (const value_type &value)
node_typeDoCreateNode (const node_type *pNodeSource, node_type *pNodeParent)
node_typeDoCopySubtree (const node_type *pNodeSource, node_type *pNodeDest)
void DoNukeSubtree (node_type *pNode)
eastl::pair< iterator, bool > DoInsertValue (const value_type &value, true_type)
iterator DoInsertValue (const value_type &value, false_type)
eastl::pair< iterator, bool > DoInsertKey (const key_type &key, true_type)
iterator DoInsertKey (const key_type &key, false_type)
iterator DoInsertValue (iterator position, const value_type &value, true_type)
iterator DoInsertValue (iterator position, const value_type &value, false_type)
iterator DoInsertKey (iterator position, const key_type &key, true_type)
iterator DoInsertKey (iterator position, const key_type &key, false_type)
iterator DoInsertValueImpl (node_type *pNodeParent, const value_type &value, bool bForceToLeft)
iterator DoInsertKeyImpl (node_type *pNodeParent, const key_type &key, bool bForceToLeft)

Detailed Description

template<typename Key, typename Value, typename Compare, typename Allocator, typename ExtractKey, bool bMutableIterators, bool bUniqueKeys>
class eastl::rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys >


rbtree is the red-black tree basis for the map, multimap, set, and multiset containers. Just about all the work of those containers is done here, and they are merely a shell which sets template policies that govern the code generation for this rbtree.

This rbtree implementation is pretty much the same as all other modern rbtree implementations, as the topic is well known and researched. We may choose to implement a "relaxed balancing" option at some point in the future if it is deemed worthwhile. Most rbtree implementations don't do this.

The primary rbtree member variable is mAnchor, which is a node_type and acts as the end node. However, like any other node, it has mpNodeLeft, mpNodeRight, and mpNodeParent members. We do the conventional trick of assigning begin() (left-most rbtree node) to mpNodeLeft, assigning 'end() - 1' (a.k.a. rbegin()) to mpNodeRight, and assigning the tree root node to mpNodeParent.

Compare (functor): This is a comparison class which defaults to 'less'. It is a common STL thing which takes two arguments and returns true if the first is less than the second.

ExtractKey (functor): This is a class which gets the key from a stored node. With map and set, the node is a pair, whereas with set and multiset the node is just the value. ExtractKey will be either eastl::use_first (map and multimap) or eastl::use_self (set and multiset).

bMutableIterators (bool): true if rbtree::iterator is a mutable iterator, false if iterator and const_iterator are both const iterators. It will be true for map and multimap and false for set and multiset.

bUniqueKeys (bool): true if the keys are to be unique, and false if there can be multiple instances of a given key. It will be true for set and map and false for multiset and multimap.

To consider: Add an option for relaxed tree balancing. This could result in performance improvements but would require a more complicated implementation.

find_as In order to support the ability to have a tree of strings but be able to do efficiently lookups via char pointers (i.e. so they aren't converted to string objects), we provide the find_as function. This function allows you to do a find with a key of a type other than the tree's key type. See the find_as function for more documentation on this.

Definition at line 345 of file red_black_tree_eastl.h.

Member Function Documentation

template<typename K , typename V , typename C , typename A , typename E , bool bM, bool bU>
rbtree< K, V, C, A, E, bM, bU >::insert_return_type eastl::rbtree< K, V, C, A, E, bM, bU >::insert ( const value_type &  value) [inline]

map::insert and set::insert return a pair, while multimap::insert and multiset::insert return an iterator.

Definition at line 902 of file red_black_tree_eastl.h.

template<typename K , typename V , typename C , typename A , typename E , bool bM, bool bU>
template<typename U , typename Compare2 >
rbtree< K, V, C, A, E, bM, bU >::iterator eastl::rbtree< K, V, C, A, E, bM, bU >::find_as ( const U &  u,
Compare2  compare2 

Implements a find whereby the user supplies a comparison of a different type than the tree's value_type. A useful case of this is one whereby you have a container of string objects but want to do searches via passing in char pointers. The problem is that without this kind of find, you need to do the expensive operation of converting the char pointer to a string so it can be used as the argument to the find function.

Example usage (note that the compare uses string as first type and char* as second): set<string> strings; strings.find_as("hello", less_2<string, const char*>());

Definition at line 1468 of file red_black_tree_eastl.h.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines