CRBTree Class

Article
04/24/2015

This class provides methods for creating and utilizing a Red-Black tree.

template< 
   typename K, 
   typename V, 
   class KTraits = CElementTraits< K >, 
   class VTraits = CElementTraits< V > 
> class CRBTree

Parameters

K
The key element type.
V
The value element type.
KTraits
The code used to copy or move key elements. See CElementTraits Class for more details.
VTraits
The code used to copy or move value elements.

Members

Public Typedefs

Name	Description
CRBTree::KINARGTYPE	Type used when a key is passed as an input argument.
CRBTree::KOUTARGTYPE	Type used when a key is returned as an output argument.
CRBTree::VINARGTYPE	Type used when a value is passed as an input argument.
CRBTree::VOUTARGTYPE	Type used when a value is passed as an output argument.

Public Classes

Name	Description
CRBTree::CPair Class	A class containing the key and value elements.

Public Constructors

Name	Description
CRBTree::~CRBTree	The destructor.

Public Methods

Name	Description
CRBTree::FindFirstKeyAfter	Call this method to find the position of the element that uses the next available key.
CRBTree::GetAt	Call this method to get the element at a given position in the tree.
CRBTree::GetCount	Call this method to get the number of elements in the tree.
CRBTree::GetHeadPosition	Call this method to get the position value for the element at the head of the tree.
CRBTree::GetKeyAt	Call this method to get the key from a given position in the tree.
CRBTree::GetNext	Call this method to obtain a pointer to an element stored in the CRBTree object, and advance the position to the next element.
CRBTree::GetNextAssoc	Call this method to get the key and value of an element stored in the map and advance the position to the next element.
CRBTree::GetNextKey	Call this method to get the key of an element stored in the tree and advance the position to the next element.
CRBTree::GetNextValue	Call this method to get the value of an element stored in the tree and advance the position to the next element.
CRBTree::GetPrev	Call this method to obtain a pointer to an element stored in the CRBTree object, and then update the position to the previous element.
CRBTree::GetTailPosition	Call this method to get the position value for the element at the tail of the tree.
CRBTree::GetValueAt	Call this method to retrieve the value stored at a given position in the CRBTree object.
CRBTree::IsEmpty	Call this method to test for an empty tree object.
CRBTree::RemoveAll	Call this method to remove all elements from the CRBTree object.
CRBTree::RemoveAt	Call this method to remove the element at the given position in the CRBTree object.
CRBTree::SetValueAt	Call this method to change the value stored at a given position in the CRBTree object.

Remarks

A Red-Black tree is a binary search tree that uses an extra bit of information per node to ensure that it remains "balanced," that is, the tree height doesn't grow disproportionately large and affect performance.

This template class is designed to be used by CRBMap and CRBMultiMap. The bulk of the methods that make up these derived classes are provided by CRBTree.

For a more complete discussion of the various collection classes and their features and performance characteristics, see ATL Collection Classes.

Requirements

Header: atlcoll.h