CRBTree Class

 

For the latest documentation on Visual Studio 2017 RC, see Visual Studio 2017 RC Documentation.

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.

Public Typedefs

NameDescription
CRBTree::KINARGTYPEType used when a key is passed as an input argument.
CRBTree::KOUTARGTYPEType used when a key is returned as an output argument.
CRBTree::VINARGTYPEType used when a value is passed as an input argument.
CRBTree::VOUTARGTYPEType used when a value is passed as an output argument.

Public Classes

NameDescription
CRBTree::CPair ClassA class containing the key and value elements.

Public Constructors

NameDescription
CRBTree::~CRBTreeThe destructor.

Public Methods

NameDescription
CRBTree::FindFirstKeyAfterCall this method to find the position of the element that uses the next available key.
CRBTree::GetAtCall this method to get the element at a given position in the tree.
CRBTree::GetCountCall this method to get the number of elements in the tree.
CRBTree::GetHeadPositionCall this method to get the position value for the element at the head of the tree.
CRBTree::GetKeyAtCall this method to get the key from a given position in the tree.
CRBTree::GetNextCall this method to obtain a pointer to an element stored in the CRBTree object, and advance the position to the next element.
CRBTree::GetNextAssocCall this method to get the key and value of an element stored in the map and advance the position to the next element.
CRBTree::GetNextKeyCall this method to get the key of an element stored in the tree and advance the position to the next element.
CRBTree::GetNextValueCall this method to get the value of an element stored in the tree and advance the position to the next element.
CRBTree::GetPrevCall this method to obtain a pointer to an element stored in the CRBTree object, and then update the position to the previous element.
CRBTree::GetTailPositionCall this method to get the position value for the element at the tail of the tree.
CRBTree::GetValueAtCall this method to retrieve the value stored at a given position in the CRBTree object.
CRBTree::IsEmptyCall this method to test for an empty tree object.
CRBTree::RemoveAllCall this method to remove all elements from the CRBTree object.
CRBTree::RemoveAtCall this method to remove the element at the given position in the CRBTree object.
CRBTree::SetValueAtCall this method to change the value stored at a given position in the CRBTree object.

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.

Header: atlcoll.h

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:

m_keyThe data member storing the key element.
m_valueThe data member storing the value element.

The destructor.

~CRBTree() throw();

Remarks

Frees any allocated resources. Calls CRBTree::RemoveAll to delete all elements.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Type used when a key is passed as an input argument.

typedef KTraits::INARGTYPE KINARGTYPE;

Type used when a key is returned as an output argument.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

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.

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.

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.

Type used when a value is passed as an input argument.

typedef VTraits::INARGTYPE VINARGTYPE;

Type used when a value is passed as an output argument.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Class Overview

Show: