CRBTree Class
This class provides methods for creating and utilizing a Red-Black tree.
Syntax
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
CRBTree::CPair Class
A class containing the key and value elements.
class CPair : public __POSITION
Remarks
This class is used by the methods CRBTree::GetAt, CRBTree::GetNext, and CRBTree::GetPrev to access the key and value elements stored in the tree structure.
The members are as follows:
| Data member | Description |
|---|---|
m_key |
The data member storing the key element. |
m_value |
The data member storing the value element. |
CRBTree::~CRBTree
The destructor.
~CRBTree() throw();
Remarks
Frees any allocated resources. Calls CRBTree::RemoveAll to delete all elements.
CRBTree::FindFirstKeyAfter
Call this method to find the position of the element that uses the next available key.
POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();
Parameters
key
A key value.
Return Value
Returns the position value of the element that uses the next available key. If there are no more elements, NULL is returned.
Remarks
This method makes it easy to traverse the tree without having to calculate position values beforehand.
CRBTree::GetAt
Call this method to get the element at a given position in the tree.
CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
Parameters
pos
The position value.
key
The variable that receives the key.
value
The variable that receives the value.
Return Value
The first two forms return a pointer to a CPair. The third form obtains a key and a value for the given position.
Remarks
The position value can be previously determined with a call to a method such as CRBTree::GetHeadPosition or CRBTree::GetTailPosition.
In debug builds, an assertion failure will occur if pos is equal to NULL.
CRBTree::GetCount
Call this method to get the number of elements in the tree.
size_t GetCount() const throw();
Return Value
Returns the number of elements (each key/value pair is one element) stored in the tree.
CRBTree::GetHeadPosition
Call this method to get the position value for the element at the head of the tree.
POSITION GetHeadPosition() const throw();
Return Value
Returns the position value for the element at the head of the tree.
Remarks
The value returned by GetHeadPosition can be used with methods such as CRBTree::GetKeyAt or CRBTree::GetNext to traverse the tree and retrieve values.
CRBTree::GetKeyAt
Call this method to get the key from a given position in the tree.
const K& GetKeyAt(POSITION pos) const throw();
Parameters
pos
The position value.
Return Value
Returns the key stored at position pos in the tree.
Remarks
If pos is not a valid position value, results are unpredictable. In debug builds, an assertion failure will occur if pos is equal to NULL.
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.
const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
Return Value
Returns a pointer to the next CPair value in the tree.
Remarks
The pos position counter is updated after each call. If the retrieved element is the last in the tree, pos is set to NULL.
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.
void GetNextAssoc(
POSITION& pos,
KOUTARGTYPE key,
VOUTARGTYPE value) const;
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
key
Template parameter specifying the type of the tree's key.
value
Template parameter specifying the type of the tree's value.
Remarks
The pos position counter is updated after each call. If the retrieved element is the last in the tree, pos is set to NULL.
CRBTree::GetNextKey
Call this method to get the key of an element stored in the tree and advance the position to the next element.
const K& GetNextKey(POSITION& pos) const throw();
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
Return Value
Returns a reference to the next key in the tree.
Remarks
Updates the current position counter, pos. If there are no more entries in the tree, the position counter is set to NULL.
CRBTree::GetNextValue
Call this method to get the value of an element stored in the tree and advance the position to the next element.
const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
Return Value
Returns a reference to the next value in the tree.
Remarks
Updates the current position counter, pos. If there are no more entries in the tree, the position counter is set to NULL.
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.
const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
Return Value
Returns a pointer to the previous CPair value stored in the tree.
Remarks
Updates the current position counter, pos. If there are no more entries in the tree, the position counter is set to NULL.
CRBTree::GetTailPosition
Call this method to get the position value for the element at the tail of the tree.
POSITION GetTailPosition() const throw();
Return Value
Returns the position value for the element at the tail of the tree.
Remarks
The value returned by GetTailPosition can be used with methods such as CRBTree::GetKeyAt or CRBTree::GetPrev to traverse the tree and retrieve values.
CRBTree::GetValueAt
Call this method to retrieve the value stored at a given position in the CRBTree object.
const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
Return Value
Returns a reference to the value stored at the given position in the CRBTree object.
CRBTree::IsEmpty
Call this method to test for an empty tree object.
bool IsEmpty() const throw();
Return Value
Returns TRUE if the tree is empty, FALSE otherwise.
CRBTree::KINARGTYPE
Type used when a key is passed as an input argument.
typedef KTraits::INARGTYPE KINARGTYPE;
CRBTree::KOUTARGTYPE
Type used when a key is returned as an output argument.
typedef KTraits::OUTARGTYPE KOUTARGTYPE;
CRBTree::RemoveAll
Call this method to remove all elements from the CRBTree object.
void RemoveAll() throw();
Remarks
Clears out the CRBTree object, freeing the memory used to store the elements.
CRBTree::RemoveAt
Call this method to remove the element at the given position in the CRBTree object.
void RemoveAt(POSITION pos) throw();
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
Remarks
Removes the key/value pair stored at the specified position. The memory used to store the element is freed. The POSITION referenced by pos becomes invalid, and while the POSITION of any other elements in the tree remains valid, they do not necessarily retain the same order.
CRBTree::SetValueAt
Call this method to change the value stored at a given position in the CRBTree object.
void SetValueAt(POSITION pos, VINARGTYPE value);
Parameters
pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.
value
The value to add to the CRBTree object.
Remarks
Changes the value element stored at the given position in the CRBTree object.
CRBTree::VINARGTYPE
Type used when a value is passed as an input argument.
typedef VTraits::INARGTYPE VINARGTYPE;
CRBTree::VOUTARGTYPE
Type used when a value is passed as an output argument.
typedef VTraits::OUTARGTYPE VOUTARGTYPE;
See also
Feedback
Coming soon: Throughout 2024 we will be phasing out GitHub Issues as the feedback mechanism for content and replacing it with a new feedback system. For more information see: https://aka.ms/ContentUserFeedback.
Submit and view feedback for