#include <red_black_tree.h>

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

[legend]

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

[legend]

Public Types
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 value_type *	pointer

typedef const value_type *	const_pointer

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< iterator >	reverse_iterator

typedef eastl::reverse_iterator< const_iterator >	const_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_type >	base_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=EASTL_RBTREE_DEFAULT_ALLOCATOR)

	rbtree (const this_type &x)

	rbtree (this_type &&x)

	rbtree (this_type &&x, const allocator_type &allocator)

template<typename InputIterator >
	rbtree (InputIterator first, InputIterator last, const Compare &compare, const allocator_type &allocator=EASTL_RBTREE_DEFAULT_ALLOCATOR)

const allocator_type &	get_allocator () const EA_NOEXCEPT

allocator_type &	get_allocator () EA_NOEXCEPT

void	set_allocator (const allocator_type &allocator)

const key_compare &	key_comp () const

key_compare &	key_comp ()

this_type &	operator= (const this_type &x)

this_type &	operator= (std::initializer_list< value_type > ilist)

this_type &	operator= (this_type &&x)

void	swap (this_type &x)

iterator	begin () EA_NOEXCEPT

const_iterator	begin () const EA_NOEXCEPT

const_iterator	cbegin () const EA_NOEXCEPT

iterator	end () EA_NOEXCEPT

const_iterator	end () const EA_NOEXCEPT

const_iterator	cend () const EA_NOEXCEPT

reverse_iterator	rbegin () EA_NOEXCEPT

const_reverse_iterator	rbegin () const EA_NOEXCEPT

const_reverse_iterator	crbegin () const EA_NOEXCEPT

reverse_iterator	rend () EA_NOEXCEPT

const_reverse_iterator	rend () const EA_NOEXCEPT

const_reverse_iterator	crend () const EA_NOEXCEPT

bool	empty () const EA_NOEXCEPT

size_type	size () const EA_NOEXCEPT

template<class... Args>
insert_return_type	emplace (Args &&... args)

template<class... Args>
iterator	emplace_hint (const_iterator position, Args &&... args)

template<class... Args>
eastl::pair< iterator, bool >	try_emplace (const key_type &k, Args &&... args)

template<class... Args>
eastl::pair< iterator, bool >	try_emplace (key_type &&k, Args &&... args)

template<class... Args>
iterator	try_emplace (const_iterator position, const key_type &k, Args &&... args)

template<class... Args>
iterator	try_emplace (const_iterator position, key_type &&k, Args &&... args)

template<class P , class = typename eastl::enable_if<eastl::is_constructible<value_type, P&&>::value>::type>
insert_return_type	insert (P &&otherValue)

iterator	insert (const_iterator hint, value_type &&value)

insert_return_type	insert (const value_type &value)

iterator	insert (const_iterator position, const value_type &value)

void	insert (std::initializer_list< value_type > ilist)

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)

template<class M >
pair< iterator, bool >	insert_or_assign (const key_type &k, M &&obj)

template<class M >
pair< iterator, bool >	insert_or_assign (key_type &&k, M &&obj)

template<class M >
iterator	insert_or_assign (const_iterator hint, const key_type &k, M &&obj)

template<class M >
iterator	insert_or_assign (const_iterator hint, key_type &&k, M &&obj)

iterator	erase (const_iterator position)

iterator	erase (const_iterator first, const_iterator last)

reverse_iterator	erase (const_reverse_iterator position)

reverse_iterator	erase (const_reverse_iterator first, const_reverse_iterator last)

void	erase (const key_type first, const key_type last)

void	clear ()

void	reset_lose_memory ()

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)

template<class... Args>
eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool >	try_emplace (const key_type &key, Args &&... args)

template<class... Args>
eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool >	try_emplace (key_type &&key, Args &&... args)

template<class M >
eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool >	insert_or_assign (const key_type &k, M &&obj)

template<class M >
eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool >	insert_or_assign (key_type &&k, M &&obj)

template<class... Args>
eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool >	DoInsertValue (true_type, Args &&... args)

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

Protected Member Functions
node_type *	DoAllocateNode ()

void	DoFreeNode (node_type *pNode)

node_type *	DoCreateNodeFromKey (const key_type &key)

template<class... Args>
node_type *	DoCreateNode (Args &&... args)

node_type *	DoCreateNode (const value_type &value)

node_type *	DoCreateNode (value_type &&value)

node_type *	DoCreateNode (const node_type pNodeSource, node_type pNodeParent)

node_type *	DoCopySubtree (const node_type pNodeSource, node_type pNodeDest)

void	DoNukeSubtree (node_type *pNode)

template<class... Args>
eastl::pair< iterator, bool >	DoInsertValue (true_type, Args &&... args)

template<class... Args>
iterator	DoInsertValue (false_type, Args &&... args)

eastl::pair< iterator, bool >	DoInsertValue (true_type, value_type &&value)

iterator	DoInsertValue (false_type, value_type &&value)

template<class... Args>
iterator	DoInsertValueImpl (node_type *pNodeParent, bool bForceToLeft, const key_type &key, Args &&... args)

iterator	DoInsertValueImpl (node_type pNodeParent, bool bForceToLeft, const key_type &key, node_type pNodeNew)

eastl::pair< iterator, bool >	DoInsertKey (true_type, const key_type &key)

iterator	DoInsertKey (false_type, const key_type &key)

template<class... Args>
iterator	DoInsertValueHint (true_type, const_iterator position, Args &&... args)

template<class... Args>
iterator	DoInsertValueHint (false_type, const_iterator position, Args &&... args)

iterator	DoInsertValueHint (true_type, const_iterator position, value_type &&value)

iterator	DoInsertValueHint (false_type, const_iterator position, value_type &&value)

iterator	DoInsertKey (true_type, const_iterator position, const key_type &key)

iterator	DoInsertKey (false_type, const_iterator position, const key_type &key)

iterator	DoInsertKeyImpl (node_type *pNodeParent, bool bForceToLeft, const key_type &key)

node_type *	DoGetKeyInsertionPositionUniqueKeys (bool &canInsert, const key_type &key)

node_type *	DoGetKeyInsertionPositionNonuniqueKeys (const key_type &key)

node_type *	DoGetKeyInsertionPositionUniqueKeysHint (const_iterator position, bool &bForceToLeft, const key_type &key)

node_type *	DoGetKeyInsertionPositionNonuniqueKeysHint (const_iterator position, bool &bForceToLeft, const key_type &key)

Protected Member Functions inherited from eastl::rb_base_compare_ebo< Compare, bool >
	rb_base_compare_ebo (const Compare &compare)

Compare &	get_compare ()

const Compare &	get_compare () const

template<typename T >
bool	compare (const T &lhs, const T &rhs)

template<typename T >
bool	compare (const T &lhs, const T &rhs) const

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.

Member Function Documentation

◆ 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*>());

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

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

third_party/EASTL/include/EASTL/internal/red_black_tree.h

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

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 >

Member Function Documentation

◆ find_as()

◆ insert()

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 >