AZStd::rbtree< Traits > Class Template Reference

#include <rbtree.h>

Public Types
typedef Traits	traits_type
typedef Traits::key_type	key_type
typedef Traits::key_equal	key_equal
typedef Traits::allocator_type	allocator_type
typedef allocator_type::size_type	size_type
typedef allocator_type::difference_type	difference_type
typedef Traits::value_type	value_type
typedef value_type *	pointer
typedef const value_type *	const_pointer
typedef value_type &	reference
typedef const value_type &	const_reference
typedef AZStd::bidirectional_iterator_tag	iterator_category
typedef Internal::rbtree_node< value_type >	node_type
typedef node_type *	node_ptr_type
typedef const node_type *	const_node_ptr_type
typedef rbtree_const_iterator< typename Traits::value_type >	const_iterator_impl
typedef rbtree_iterator< typename Traits::value_type >	iterator_impl
typedef iterator_impl	iterator
typedef const_iterator_impl	const_iterator
typedef AZStd::reverse_iterator< iterator >	reverse_iterator
typedef AZStd::reverse_iterator< const_iterator >	const_reverse_iterator
typedef rbtree_node_destructor< allocator_type, node_type >	node_deleter

Public Member Functions
	rbtree (const key_equal &keyEq)
	rbtree (const allocator_type &allocator)
AZ_FORCE_INLINE	rbtree (const key_equal &keyEq, const allocator_type &allocator)
	rbtree (const this_type &rhs)
	rbtree (const this_type &rhs, const allocator_type &allocator)
this_type &	operator= (const this_type &rhs)
AZ_FORCE_INLINE key_equal	key_comp () const
AZ_FORCE_INLINE iterator	begin ()
AZ_FORCE_INLINE const_iterator	begin () const
AZ_FORCE_INLINE iterator	end ()
AZ_FORCE_INLINE const_iterator	end () const
AZ_FORCE_INLINE reverse_iterator	rbegin ()
AZ_FORCE_INLINE const_reverse_iterator	rbegin () const
AZ_FORCE_INLINE reverse_iterator	rend ()
AZ_FORCE_INLINE const_reverse_iterator	rend () const
AZ_FORCE_INLINE bool	empty () const
AZ_FORCE_INLINE size_type	size () const
AZ_FORCE_INLINE size_type	max_size () const
	rbtree (this_type &&rhs)
	rbtree (this_type &&rhs, const allocator_type &allocator)
this_type &	operator= (this_type &&rhs)
AZStd::pair< iterator, bool >	insert_unique (value_type &&value)
iterator	insert_unique (const_iterator insertPos, value_type &&value)
iterator	insert_equal (value_type &&value)
template<class ... InputArguments>
AZStd::pair< iterator, bool >	emplace_unique (InputArguments &&... arguments)
template<class ... InputArguments>
iterator	emplace_unique (const_iterator insertPos, InputArguments &&... arguments)
template<class ... InputArguments>
iterator	emplace_equal (InputArguments &&... arguments)
template<class ... InputArguments>
iterator	emplace_equal (const_iterator insertPos, InputArguments &&... arguments)
void	swap (this_type &rhs)
AZStd::pair< iterator, bool >	insert_unique (const value_type &value)
iterator	insert_equal (const value_type &value)
iterator	insert_unique (const_iterator insertPos, const value_type &value)
iterator	insert_equal (const iterator insertPos, const value_type &value)
template<class Iterator >
AZ_FORCE_INLINE void	insert_equal (Iterator first, Iterator last)
template<class Iterator >
AZ_FORCE_INLINE void	insert_unique (Iterator first, Iterator last)
template<typename ComparableToKey , typename... Args>
AZStd::pair< iterator, bool >	try_emplace_unique (ComparableToKey &&key, Args &&... arguments)
template<typename ComparableToKey , typename... Args>
iterator	try_emplace_unique (const_iterator hint, ComparableToKey &&key, Args &&... arguments)
template<typename ComparableToKey , typename MappedType >
AZStd::pair< iterator, bool >	insert_or_assign_unique (ComparableToKey &&key, MappedType &&value)
template<typename ComparableToKey , typename MappedType >
iterator	insert_or_assign_unique (const_iterator hint, ComparableToKey &&key, MappedType &&value)
template<class InsertReturnType , class NodeHandle >
InsertReturnType	node_handle_insert_unique (NodeHandle &&nodeHandle)
template<class NodeHandle >
auto	node_handle_insert_unique (const_iterator hint, NodeHandle &&nodeHandle) -> iterator
template<class NodeHandle >
auto	node_handle_insert_equal (NodeHandle &&nodeHandle) -> iterator
template<class NodeHandle >
auto	node_handle_insert_equal (const_iterator hint, NodeHandle &&nodeHandle) -> iterator
template<class NodeHandle >
NodeHandle	node_handle_extract (const key_type &key)
template<class NodeHandle >
NodeHandle	node_handle_extract (const_iterator it)
iterator	erase (const_iterator erasePos)
size_type	erase (const key_type &key)
bool	erase_unique (const key_type &key)
iterator	erase (const_iterator first, const_iterator last)
AZ_FORCE_INLINE void	erase (const key_type *first, const key_type *last)
AZ_FORCE_INLINE void	clear ()
template<class ComparableToKey >
auto	find (const ComparableToKey &key) -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, iterator >
template<class ComparableToKey >
auto	find (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, const_iterator >
template<class ComparableToKey >
auto	contains (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, bool >
template<class ComparableToKey >
auto	lower_bound (const ComparableToKey &key) -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, iterator >
template<class ComparableToKey >
auto	lower_bound (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, const_iterator >
template<class ComparableToKey >
auto	upper_bound (const ComparableToKey &key) -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, iterator >
template<class ComparableToKey >
auto	upper_bound (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, const_iterator >
template<class ComparableToKey >
auto	count (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, size_type >
template<class ComparableToKey >
auto	equal_range (const ComparableToKey &key) -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, AZStd::pair< iterator, iterator > >
template<class ComparableToKey >
auto	equal_range (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, AZStd::pair< const_iterator, const_iterator > >
template<class ComparableToKey >
auto	equal_range_unique (const ComparableToKey &key) -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, AZStd::pair< iterator, iterator > >
template<class ComparableToKey >
auto	equal_range_unique (const ComparableToKey &key) const -> enable_if_t< Internal::is_transparent< key_equal, ComparableToKey >::value||AZStd::is_convertible_v< ComparableToKey, key_type >, AZStd::pair< const_iterator, const_iterator > >
template<typename ComparableToKey , typename... Args>
auto	try_emplace_unique (ComparableToKey &&key, Args &&... arguments) -> AZStd::pair< iterator, bool >
template<typename ComparableToKey , typename... Args>
auto	try_emplace_unique (const_iterator hint, ComparableToKey &&key, Args &&... arguments) -> iterator
template<typename ComparableToKey , typename MappedType >
auto	insert_or_assign_unique (ComparableToKey &&key, MappedType &&value) -> AZStd::pair< iterator, bool >
template<typename ComparableToKey , typename MappedType >
auto	insert_or_assign_unique (const_iterator hint, ComparableToKey &&key, MappedType &&value) -> iterator
Extensions
allocator_type &	get_allocator ()
const allocator_type &	get_allocator () const
void	set_allocator (const allocator_type &allocator)
	Set the vector allocator. If different than then current all elements will be reallocated.
bool	validate () const
int	validate_iterator (const const_iterator &iter) const
	Validates an iter iterator. Returns a combination of iterator_status_flag.
int	validate_iterator (const iterator &iter) const
void	leak_and_reset ()

Protected Types
typedef Internal::rbtree_node_base *	base_node_ptr_type
typedef const Internal::rbtree_node_base *	const_base_node_ptr_type

Detailed Description

template<class Traits>
class AZStd::rbtree< Traits >

Generic red-black tree. Based on the STLport implementation. In addition to all AZStd extensions and requirements, we use compressed node which saves about ~25% of the tree overhead. This is the base container used for AZStd::set,AZStd::multiset,AZStd::map and AZStd::multimap.

RedBlackTreeTest for examples.

Traits should have the following members typedef xxx key_type; typedef xxx key_equal; typedef xxx value_type; typedef xxx allocator_type; enum { has_multi_elements = true or false, is_dynamic = true or false, // true if we have fixed container. If we do so we will need to se fixed_num_buckets and fixed_num_elements. }

static inline const key_type& key_from_value(const value_type& value);

Member Function Documentation

leak_and_reset()

template<class Traits >

void AZStd::rbtree< Traits >::leak_and_reset ( )

inline

Resets the container without deallocating any memory or calling any destructor. This function should be used when we need very quick tear down. Generally it's used for temporary vectors and we can just nuke them that way. In addition the provided Allocators, has leak and reset flag which will enable automatically this behavior. So this function should be used in special cases AZStdExamples.

Note

This function is added to the vector for consistency. In the vector case we have only one allocation, and if the allocator allows memory leaks it can just leave deallocate function empty, which performance wise will be the same. For more complex containers this will make big difference.

node_handle_extract() [1/2]

template<class Traits >

template<class NodeHandle >

NodeHandle AZStd::rbtree< Traits >::node_handle_extract ( const key_type &  key )

inline

Searches for an element which matches the value of key and extracts it from the hash_table

Returns

A NodeHandle which can be used to insert the an element between unique and non-unique containers of the same type i.e a NodeHandle from an unordered_map can be used to insert a node into an unordered_multimap, but not a std::map

node_handle_extract() [2/2]

template<class Traits >

template<class NodeHandle >

NodeHandle AZStd::rbtree< Traits >::node_handle_extract ( const_iterator  it )

inline

Finds an element within the hash_table that is represented by the supplied iterator and extracts it

Returns

A NodeHandle which can be used to insert the an element between unique and non-unique containers of the same type

node_handle_insert_equal()

template<class Traits >

template<class NodeHandle >

auto AZStd::rbtree< Traits >::node_handle_insert_equal ( NodeHandle &&  nodeHandle ) -> iterator

inline

Returns an iterator pointing to the inserted element. If the nodeHandle is empty the end() iterator is returned

node_handle_insert_unique()

template<class Traits >

template<class InsertReturnType , class NodeHandle >

InsertReturnType AZStd::rbtree< Traits >::node_handle_insert_unique ( NodeHandle &&  nodeHandle )

inline

Returns an insert_return_type with the members initialized as follows: if nodeHandle is empty, inserted is false, position is end(), and node is empty. Otherwise if the insertion took place, inserted is true, position points to the inserted element, and node is empty. If the insertion failed, inserted is false, node has the previous value of nodeHandle, and position points to an element with a key equivalent to nodeHandle.key().

---

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

• Code/Framework/AzCore/AzCore/std/containers/node_handle.h
• Code/Framework/AzCore/AzCore/std/containers/rbtree.h