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

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 iterator
 
typedef rbtree_iterator< value_type, const value_type *, const value_type & > const_iterator
 
typedef eastl::reverse_iterator< iteratorreverse_iterator
 
typedef eastl::reverse_iterator< const_iteratorconst_reverse_iterator
 
typedef Allocator allocator_type
 
typedef Compare key_compare
 
typedef type_select< bUniqueKeys, eastl::pair< iterator, bool >, iterator >::type insert_return_type
 
typedef rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys > this_type
 
typedef rb_base< Key, Value, Compare, ExtractKey, bUniqueKeys, this_typebase_type
 
typedef integral_constant< bool, bUniqueKeys > has_unique_keys_type
 
typedef base_type::extract_key extract_key
 
- Public Types inherited from eastl::rb_base< Key, Value, Compare, ExtractKey, bUniqueKeys, rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys > >
typedef ExtractKey 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 Member Functions inherited from eastl::rb_base< Key, Value, Compare, ExtractKey, bUniqueKeys, rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys > >
 rb_base (const Compare &compare)
 

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).
 
Compare mCompare
 
- Public Attributes inherited from eastl::rb_base< Key, Value, Compare, ExtractKey, bUniqueKeys, rbtree< Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys > >
Compare mCompare
 

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

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

◆ insert()

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.

◆ find_as()

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: