CRBTree 类

  • 项目

此类提供用于创建和使用 Red-Black 树的方法。

语法

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

参数

K
键元素类型。

V
值元素类型。

KTraits
用于复制或移动键元素的代码。 有关更多详细信息，请参阅 CElementTraits 类。

VTraits
用于复制或移动值元素的代码。

成员

公共 Typedef

名称 描述
CRBTree::KINARGTYPE 作为输入参数传递键时使用的类型。
CRBTree::KOUTARGTYPE 作为输出参数返回键时使用的类型。
CRBTree::VINARGTYPE 作为输入参数传递值时使用的类型。
CRBTree::VOUTARGTYPE 作为输出参数传递值时使用的类型。

公共类

名称 描述
CRBTree::CPair 类 包含键和值元素的类。

公共构造函数

名称 描述
CRBTree::~CRBTree 析构函数。

公共方法

名称 描述
CRBTree::FindFirstKeyAfter 调用此方法可查找使用下一个可用键的元素的位置。
CRBTree::GetAt 调用此方法以获取树中给定位置的元素。
CRBTree::GetCount 调用此方法可获取树中的元素数。
CRBTree::GetHeadPosition 调用此方法可获取树头元素的位置值。
CRBTree::GetKeyAt 调用此方法以从树中的给定位置获取密钥。
CRBTree::GetNext 调用此方法可获取指向存储在 CRBTree 对象中的元素的指针，并将位置推进到下一个元素。
CRBTree::GetNextAssoc 调用此方法获取存储在映射中的元素的键和值，并将位置推进到下一个元素。
CRBTree::GetNextKey 调用此方法获取存储在树中的元素的键，并将位置推进到下一个元素。
CRBTree::GetNextValue 调用此方法以获取存储在树中的元素的值，并将位置推进到下一个元素。
CRBTree::GetPrev 调用此方法获取指向存储在 CRBTree 对象中的元素的指针，然后将位置更新到前一个元素。
CRBTree::GetTailPosition 调用此方法可获取树尾元素的位置值。
CRBTree::GetValueAt 调用此方法可检索存储在 CRBTree 对象中给定位置的值。
CRBTree::IsEmpty 调用此方法可测试空树对象。
CRBTree::RemoveAll 调用此方法可从 CRBTree 对象中删除所有元素。
CRBTree::RemoveAt 调用此方法可删除 CRBTree 对象中给定位置处的元素。
CRBTree::SetValueAt 调用此方法可更改存储在 CRBTree 对象中给定位置的值。

备注

红黑树是一种二叉搜索树，它使用每个节点的额外信息来确保它保持“平衡”，也就是说，树的高度不会不成比例地增大因而影响性能。

此模板类旨在供 CRBMap 和 CRBMultiMap 使用。 构成这些派生类的大部分方法由 CRBTree 提供。

有关各种集合类及其特性和性能特征的更完整讨论，请参阅 ATL 集合类。

要求

标头：atlcoll.h

CRBTree::CPair 类

包含键和值元素的类。

class CPair : public __POSITION

备注

CRBTree::GetAt、CRBTree::GetNext 和 CRBTree::GetPrev 方法使用此类来访问存储在树结构中的键和值元素。

成员如下：

数据成员 说明
m_key 存储键元素的数据成员。
m_value 存储值元素的数据成员。

CRBTree::~CRBTree

析构函数。

~CRBTree() throw();

备注

释放任何已分配的资源。 调用 CRBTree::RemoveAll 可删除所有元素。

CRBTree::FindFirstKeyAfter

调用此方法可查找使用下一个可用键的元素的位置。

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

参数

键
一个键值。

返回值

返回使用下一个可用键的元素的位置值。 如果没有更多元素，则返回 NULL。

备注

这种方法可以很轻松地遍历树，而无需事先计算位置值。

CRBTree::GetAt

调用此方法以获取树中给定位置的元素。

CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;

参数

pos
位置值。

键
用于接收键的变量。

value
用于接收值的变量。

返回值

前两种形式返回一个指向 CPair 的指针。 第三种形式获取给定位置的键和值。

备注

可以通过调用 CRBTree::GetHeadPosition 或 CRBTree::GetTailPosition 等方法预先确定位置值。

在调试版本中，如果 pos 等于 NULL，则会发生断言失败。

CRBTree::GetCount

调用此方法可获取树中的元素数。

size_t GetCount() const throw();

返回值

返回存储在树中的元素数量（每个键/值对是一个元素）。

CRBTree::GetHeadPosition

调用此方法可获取树头元素的位置值。

POSITION GetHeadPosition() const throw();

返回值

返回树头元素的位置值。

注解

GetHeadPosition 返回的值可以与 CRBTree::GetKeyAt 或 CRBTree::GetNext 等方法一起使用，以遍历树并检索值。

CRBTree::GetKeyAt

调用此方法以从树中的给定位置获取密钥。

const K& GetKeyAt(POSITION pos) const throw();

参数

pos
位置值。

返回值

返回存储在树中位置 pos 的键。

备注

如果 pos 不是有效的位置值，则结果是不可预测的。 在调试版本中，如果 pos 等于 NULL，则会发生断言失败。

CRBTree::GetNext

调用此方法可获取指向存储在 CRBTree 对象中的元素的指针，并将位置推进到下一个元素。

const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

返回值

返回指向树中下一个 CPair 值的指针。

备注

在每次调用后都会更新 pos 位置计数器。 如果检索到的元素是树中的最后一个元素，则将 pos 设置为 NULL。

CRBTree::GetNextAssoc

调用此方法获取存储在映射中的元素的键和值，并将位置推进到下一个元素。

void GetNextAssoc(
    POSITION& pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

键
用于指定树的键类型的模板参数。

value
用于指定树的值类型的模板参数。

备注

在每次调用后都会更新 pos 位置计数器。 如果检索到的元素是树中的最后一个元素，则将 pos 设置为 NULL。

CRBTree::GetNextKey

调用此方法获取存储在树中的元素的键，并将位置推进到下一个元素。

const K& GetNextKey(POSITION& pos) const throw();

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

返回值

返回对映射中下一个树的引用。

备注

更新当前位置计数器 pos。如果树中没有更多条目，则位置计数器设置为 NULL。

CRBTree::GetNextValue

调用此方法以获取存储在树中的元素的值，并将位置推进到下一个元素。

const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

返回值

返回对树中下一个值的引用。

备注

更新当前位置计数器 pos。如果树中没有更多条目，则位置计数器设置为 NULL。

CRBTree::GetPrev

调用此方法获取指向存储在 CRBTree 对象中的元素的指针，然后将位置更新到前一个元素。

const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

返回值

返回指向存储在树中的前一个 CPair 值的指针。

备注

更新当前位置计数器 pos。如果树中没有更多条目，则位置计数器设置为 NULL。

CRBTree::GetTailPosition

调用此方法可获取树尾元素的位置值。

POSITION GetTailPosition() const throw();

返回值

返回树尾元素的位置值。

备注

GetTailPosition 返回的值可以与 CRBTree::GetKeyAt 或 CRBTree::GetPrev 等方法一起使用，以遍历树并检索值。

CRBTree::GetValueAt

调用此方法可检索存储在 CRBTree 对象中给定位置的值。

const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

返回值

返回对存储在 CRBTree 对象中给定位置的值的引用。

CRBTree::IsEmpty

调用此方法可测试空树对象。

bool IsEmpty() const throw();

返回值

如果树为空，则返回 TRUE；否则返回 FALSE。

CRBTree::KINARGTYPE

作为输入参数传递键时使用的类型。

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

作为输出参数返回键时使用的类型。

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

调用此方法可从 CRBTree 对象中删除所有元素。

void RemoveAll() throw();

备注

清除 CRBTree 对象，释放用于存储元素的内存。

CRBTree::RemoveAt

调用此方法可删除 CRBTree 对象中给定位置处的元素。

void RemoveAt(POSITION pos) throw();

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

备注

删除存储在指定位置的键/值对。 释放用于存储元素的内存。 pos 引用的 POSITION 变得无效，虽然树中任何其他元素的 POSITION 仍然有效，但它们不一定保持相同的顺序。

CRBTree::SetValueAt

调用此方法可更改存储在 CRBTree 对象中给定位置的值。

void SetValueAt(POSITION pos, VINARGTYPE value);

参数

pos
位置计数器，由先前调用 CRBTree::GetHeadPosition 或 CRBTree::FindFirstKeyAfter 等方法返回。

value
要添加到 CRBTree 的对象值。

备注

更改存储在 CRBTree 对象中给定位置的值元素。

CRBTree::VINARGTYPE

作为输入参数传递值时使用的类型。

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

作为输出参数传递值时使用的类型。

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

另请参阅

类概述