外部存储的红黑树集合：F´ Fw/DataStructures 中 ExternalRedBlackTreeSet 完整技术指南

外部存储的红黑树集合：F´ Fw/DataStructures 中 ExternalRedBlackTreeSet 完整技术指南

【免费下载链接】fprimeF´ - A flight software and embedded systems framework项目地址: https://gitcode.com/GitHub_Trending/fpr/fprime

ExternalRedBlackTreeSet是 F´（F Prime，飞行软件与嵌入式系统框架）Fw/DataStructures数据结构库中基于红黑树实现、采用外部后备存储的集合（Set）类模板。本文以官方 SDD 文档（Fw/DataStructures/docs/ExternalRedBlackTreeSet.md）为骨架，结合仓库头文件与单元测试，系统讲解它的模板参数、继承体系、五个构造函数、全部成员函数、静态存储布局函数，以及底层RedBlackTreeSetOrMapImpl的红黑树不变量与重平衡原理，帮助你理解如何在零堆分配、容量受限的嵌入式场景中直接使用该容器。

1. 定位：F´ DataStructures 库中的"外部存储"集合

在 F´ 框架中，Fw/DataStructures提供了一组基础数据结构，所有定义位于命名空间Fw下。该库区分两个核心概念（见 sdd.md）：

• size（大小）：数据结构当前存储的元素个数；
• capacity（容量）：数据结构最多可存储的元素个数。

对于定长数组，size 与 capacity 相同；对于集合这类容器，size 介于 0 与 capacity 之间。所有容器都属于顺序数据结构（sequential data structures），不支持多线程直接并发访问；如需多线程使用，官方建议将其作为 active/queued 组件的成员，借助组件队列来串行化访问。

集合（Set）家族在Fw/DataStructures中一共有四个实现类模板：

类图如下：

"外部存储"意味着树节点所用的内存由调用方提供（可以是一段静态分配的缓冲区或字节数组），容器自身不持有、不动态申请内存。这正是嵌入式/飞行软件场景的核心诉求：零堆分配、容量静态可控、运行时可预测。

2. 模板参数与基类

2.1. 模板参数

ExternalRedBlackTreeSet只有一个模板参数（对应文档第 1 节）：

与内部存储版本RedBlackTreeSet<T, C>（容量C作为编译期模板参数，见 RedBlackTreeSet.md）不同，ExternalRedBlackTreeSet<T>的容量是运行时通过构造函数或setStorage传入的，灵活性更高，代价是需要调用方自行管理后备内存。

2.2. 基类

ExternalRedBlackTreeSet<T>公开继承自抽象基类SetBase<T>，而SetBase<T>又继承自SizedContainer（表示具有 capacity 与 size 的通用容器）。SetBase定义了集合的抽象接口（SetBase.hpp）：

virtual ConstIterator begin() const = 0; virtual ConstIterator end() const = 0; virtual Success find(const T& element) const = 0; virtual Success insert(const T& element) = 0; virtual Success remove(const T& element) = 0;

此外，SetBase还提供非虚的copyDataFrom(const SetBase<T>& set)，用于把另一个集合的数据复制到当前集合：先clear()，再取min(set.getSize(), getCapacity())个元素逐一insert，并断言插入成功。

值得注意的继承细节：SetBase的拷贝构造函数与拷贝赋值运算符被声明为= delete（私有），理由是"避免在基类中使用虚的用户自定义运算符"；因此拷贝语义完全由派生类自己定义实现——ExternalRedBlackTreeSet正是这样做的（见第 5 节）。

3. 公开类型与私有成员

3.1. 公开类型（对应文档第 3 节）

其中Nil是一个空类型（Nil.md），仅作为占位符：当SetOrMapImplEntry用作"集合条目"时，其"值"部分没有意义，就用Nil填充。Entry实际承载了元素（keyOrElement）与值/占位（valueOrNil）两部分，见 SetOrMapImplEntry.md。

关于迭代器类型，需要以源码为准做一个澄清：原 SDD 文档第 3 节将ConstIterator描述为MapConstIterator<T>的别名，但 ExternalRedBlackTreeSet.hpp 中实际定义为：

using ConstIterator = SetConstIterator<T>;

这与基类SetBase中的定义一致（SetBase.hpp）。SetConstIterator提供operator==、operator!=、operator++、isInRange()、operator*、operator->等操作，且其operator*返回元素引用、对越界访问会触发断言失败（详见 SetConstIterator.md）。该迭代器基于实现类型（数组、红黑树等）提供不同的构造方式，对使用者屏蔽底层差异。

3.2. 私有成员变量（对应文档第 4 节）

组合关系：

ExternalRedBlackTreeSet本身不存储任何树节点，所有逻辑都委托给成员m_impl。RedBlackTreeSetOrMapImpl<KE, VN>是一个可同时用于 set 与 map 的红黑树实现模板（RedBlackTreeSetOrMapImpl.hpp），其内部由两个外部容器构成：

• Nodes = ExternalArray<Node>：存放树节点数组；
• FreeNodes = ExternalStack<Index>：空闲节点索引栈，用于节点的分配与回收。

当ExternalRedBlackTreeSet以"外部存储"接入时，实际就是为这两个内部容器提供后备内存。

4. 公开构造与析构函数（对应文档第 5 节）

4.1. 零参数构造函数

ExternalRedBlackTreeSet()

所有成员按默认值初始化。此时容器没有绑定任何后备存储，capacity 为 0，size 为 0，不能执行插入操作（insert会因无空闲节点而返回失败）。

示例：

ExternalRedBlackTreeSet<U32> set;

4.2. 提供类型化后备存储的构造函数

原文档给出的签名是ExternalRedBlackTreeSet(Entry* entries, FwSizeType capacity)，但以当前仓库源码为准，实际签名（ExternalRedBlackTreeSet.hpp）为：

ExternalRedBlackTreeSet(Node* nodes, //!< 树节点数组，至少 capacity 个元素 Index* freeNodes, //!< 空闲节点索引数组，至少 capacity 个元素 FwSizeType capacity)

这是因为底层红黑树实现需要两块后备内存：一块存放Node结构（含父子指针、颜色与条目），一块存放Index（即FwSizeType）类型的空闲节点栈。构造函数体调用setStorage(nodes, freeNodes, capacity)完成绑定。

示例：

using Set = ExternalRedBlackTreeSet<U32>; using Impl = Fw::RedBlackTreeSetOrMapImpl<U32, Fw::Nil>; constexpr FwSizeType capacity = 10; Impl::Node nodes[capacity]; Impl::Index freeNodes[capacity]; Set set(nodes, freeNodes, capacity);

这一用法与单元测试Fw/DataStructures/test/ut/ExternalRedBlackTreeSetTest.cpp中TypedStorageConstructor用例完全一致：测试通过友元测试器ExternalRedBlackTreeSetTester取出m_impl，验证nodes与freeNodes两块内存确实被底层m_nodes与m_freeNodes使用。

4.3. 提供非类型化（字节数组）后备存储的构造函数

ExternalRedBlackTreeSet(ByteArray data, FwSizeType capacity)

这是嵌入式场景最常用的方式：把一整块字节缓冲区按一定布局切成"节点区 + 空闲栈区"。前提条件：

• data必须按照getByteArrayAlignment()返回的对齐要求对齐；
• data必须包含至少getByteArraySize(capacity)个字节。

构造函数体内调用setStorage(data, capacity)，底层会把缓冲区切分为对齐的两段（详见第 7 节）。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; constexpr U8 alignment = Set::getByteArrayAlignment(); constexpr FwSizeType byteArraySize = Set::getByteArraySize(capacity); alignas(alignment) U8 bytes[byteArraySize]; ExternalRedBlackTreeSet<U32> set(ByteArray(&bytes[0], sizeof bytes), capacity);

4.4. 拷贝构造函数

ExternalRedBlackTreeSet(const ExternalRedBlackTreeSet<T>& set)

直接执行*this = set。由于后备存储（外部数组指针）随m_impl一起被复制，拷贝后的集合与原集合共享同一块后备存储——两个对象操作的是同一棵树。使用时务必注意这一点，避免"双写"同一缓冲区造成语义混乱。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 3; Set::Entry entries[capacity]; // 使用带后备存储的构造函数 Set m1(entries, capacity); // 插入元素 const auto status = m1.insert(42); ASSERT_EQ(status, Success::SUCCESS); // 调用拷贝构造函数 Set m2(m1); ASSERT_EQ(m2.getSize(), 1);

4.5. 析构函数

~ExternalRedBlackTreeSet() override

定义为= default。析构时不释放外部后备存储——那块内存由调用方负责生命周期管理，这正是"外部存储"设计的题中之义。

5. 公开成员函数详解（对应文档第 6 节）

除静态函数外，ExternalRedBlackTreeSet的所有成员函数都是对m_impl的薄封装，逐一说明如下。

5.1. operator=（拷贝赋值）

ExternalRedBlackTreeSet<T>& operator=(const ExternalRedBlackTreeSet<T>& set)

实现逻辑（与源码一致，ExternalRedBlackTreeSet.hpp）：

1. 若&set != this，则执行m_impl = set.m_impl（连同后备存储指针一起复制）；
2. 返回*this。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 3; Set::Entry entries[capacity]; Set m1(entries, capacity); const auto status = m1.insert(42); ASSERT_EQ(status, Success::SUCCESS); // 默认构造的集合 Set m2; ASSERT_EQ(m2.getSize(), 0); // 拷贝赋值 m2 = m1; ASSERT_EQ(m2.getSize(), 1);

5.2. begin / end

ConstIterator begin() const ConstIterator end() const

分别返回m_impl.begin()与m_impl.end()。红黑树版本的begin()会从根节点出发沿左子树一直下行，找到最左节点（中序遍历的第一个节点）；end()则把迭代器内部节点索引置为哨兵值Node::NONE。

begin 示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set::Entry entries[capacity]; Set set(entries, capacity); const auto status = set.insert(42); ASSERT_EQ(status, Fw::Success::SUCCESS); auto it = set.begin(); ASSERT_EQ(*it, 42);

end 示例（遍历到终点）：

auto iter = set.begin(); ASSERT_NE(iter, set.end()); // 非空集合时 begin 不等于 end iter++; // 自增越过唯一元素 ASSERT_EQ(iter, set.end()); // 此时到达 end

红黑树迭代器的自增逻辑（increment）值得关注：若当前节点有右孩子，则跳到右子树的最左节点；否则沿父指针上溯，直到"经过一个左孩子或到达根"。这是标准的二叉树中序遍历实现（见 RedBlackTreeSetOrMapImpl.hpp 中ConstIterator::increment）。

5.3. clear

void clear() override

调用m_impl.clear()。底层实现把根置为NONE，清空空闲栈，然后把所有节点索引按逆序压回空闲栈（capacity - i - 1）。清空后集合 size 为 0，但 capacity 与后备存储保持不变，可继续复用。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set::Entry entries[capacity]; Set set(entries, capacity); const auto status = set.insert(42); ASSERT_EQ(set.getSize(), 1); set.clear(); ASSERT_EQ(set.getSize(), 0);

5.4. find

Success find(const T& element) const override

实现为：Nil nil = {}; return m_impl.find(element, nil);——用一个局部Nil占位接收"值"输出。底层find沿树进行二叉搜索（比较keyOrElement == entryKey、<、>三分支），命中返回Success::SUCCESS，否则返回FAILURE。由于红黑树保证树高为O(log n)，查找最坏情况下需要O(log n)步。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set::Entry entries[capacity]; Set set(entries, capacity); auto status = set.find(42); ASSERT_EQ(status, Success::FAILURE); // 尚未插入 status = set.insert(42); ASSERT_EQ(status, Success::SUCCESS); status = set.find(42); ASSERT_EQ(status, Success::SUCCESS); // 插入后可找到

5.5. getCapacity / getSize

FwSizeType getCapacity() const override // 返回 m_impl.getCapacity() FwSizeType getSize() const override // 返回 m_impl.getSize()

底层getCapacity()返回节点数组大小（即后备存储容量）；getSize()则计算capacity - freeNodesSize（即"已被占用的节点数"，也就是树中实际元素数），并断言freeNodesSize <= capacity。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set::Entry entries[capacity]; Set set(entries, capacity); ASSERT_EQ(set.getCapacity(), capacity); // 容量等于后备数组大小 auto size = set.getSize(); ASSERT_EQ(size, 0); // 初始为空 const auto status = set.insert(42); ASSERT_EQ(status, Success::SUCCESS); size = set.getSize(); ASSERT_EQ(size, 1); // 插入后 size 为 1

5.6. insert

Success insert(const T& element) override

实现为return m_impl.insert(element, Nil())，即把"值"部分填Nil。底层insert的语义（RedBlackTreeSetOrMapImpl.hpp）：

1. 先findNode(element, node, direction)查找；
2. 若元素已存在，则返回SUCCESS（集合元素唯一，不重复插入）；
3. 若不存在，则从空闲栈pop一个节点，设置元素后调用insertNode将其挂入树中并按红黑树规则重平衡；
4. 若空闲栈为空（容量已满），返回FAILURE。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set::Entry entries[capacity]; Set set(entries, capacity); auto size = set.getSize(); ASSERT_EQ(size, 0); const auto status = set.insert(42); ASSERT_EQ(status, Success::SUCCESS); size = set.getSize(); ASSERT_EQ(size, 1);

5.7. remove

Success remove(const T& element) override

实现为：Nil nil = {}; return m_impl.remove(element, nil);。底层remove先查找节点，命中后把节点从树中摘除、将 freed 节点索引压回空闲栈，返回SUCCESS；元素不存在则返回FAILURE。删除是红黑树最复杂的操作，底层removeNode会对"删除黑色节点导致黑高度失衡"的多种兄弟/侄子形态分别进行旋转与重着色（详见第 8 节）。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set::Entry entries[capacity]; Set set(entries, capacity); const auto status = set.insert(42); ASSERT_EQ(status, Success::SUCCESS); // 元素不存在：删除失败 status = set.remove(0); ASSERT_EQ(status, Success::FAILURE); // 元素存在：删除成功 status = set.remove(42); ASSERT_EQ(status, Success::SUCCESS); ASSERT_EQ(set.getSize(), 0);

提示：原文档示例在remove后直接断言缓存的size变量（删除前后均为旧值），这是文档示例中的笔误；实际使用时应像上文一样在删除后重新调用set.getSize()获取最新大小。单元测试ExternalRedBlackTreeSetTest.cpp中的Remove用例则是在remove之后调用set.getSize()验证。

5.8. setStorage（类型化数据）

void setStorage(Node* nodes, Index* freeNodes, FwSizeType capacity)

直接转发给m_impl.setStorage(nodes, freeNodes, capacity)。底层实现会依次绑定m_nodes（节点数组）与m_freeNodes（空闲栈），然后调用clear()把整棵树初始化为空。调用后集合容量立即生效，可以在任意时刻为同一个集合对象更换或重新绑定后备存储。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; Set set; // 先零参构造 Set::Entry entries[capacity]; set.setStorage(entries, capacity); // 稍后绑定存储

5.9. setStorage（非类型化数据）

void setStorage(ByteArray data, FwSizeType capacity)

把单个字节缓冲区按对齐要求切分为两块后备内存：

1. 调用m_impl.setStorage(data, capacity)；
2. 调用clear()。

底层RedBlackTreeSetOrMapImpl::setStorage(ByteArray, ...)的切分逻辑（RedBlackTreeSetOrMapImpl.hpp）为：

• 节点区大小 =Nodes::getByteArraySize(capacity)；
• 计算"大于等于节点区大小、且对齐到FreeNodes::getByteArrayAlignment()"的偏移freeNodesOffset；
• 用断言保证freeNodesOffset + FreeNodes::getByteArraySize(capacity) <= data.size，即缓冲区足够大；
• 把data.bytes[freeNodesOffset .. freeNodesOffset + freeNodesSize)作为空闲栈的字节存储。

示例：

using Set = ExternalRedBlackTreeSet<U32>; constexpr FwSizeType capacity = 10; constexpr U8 alignment = Set::getByteArrayAlignment(); constexpr FwSizeType byteArraySize = Set::getByteArraySize(capacity); alignas(alignment) U8 bytes[byteArraySize]; Set set; // 先零参构造 set.setStorage(ByteArray(&bytes[0], sizeof bytes), capacity); // 再绑定字节存储

单元测试UntypedStorageConstructor用例还验证了：绑定字节存储后，底层m_nodes的元素指针恰好等于reinterpret_cast<Impl::Node*>(bytes)，证明节点区确实从缓冲区起始位置开始。

6. 公开静态函数（对应文档第 7 节）

这两个静态函数用于预先计算非类型化后备存储的布局，是"外部存储"容器正确用法的关键工具。

6.1. getByteArrayAlignment

static constexpr U8 getByteArrayAlignment()

返回RedBlackTreeSetOrMapImpl<T, Nil>::getByteArrayAlignment()，底层实现为ExternalArray<Entry>::getByteArrayAlignment()。即：字节缓冲区所需的对齐要求等于Entry（树条目类型）的对齐要求。

6.2. getByteArraySize

static constexpr FwSizeType getByteArraySize(FwSizeType capacity)

返回RedBlackTreeSetOrMapImpl<T, Nil>::getByteArraySize(capacity)，底层计算公式为：

Nodes::getByteArraySize(capacity) + FreeNodes::getByteArrayAlignment() + FreeNodes::getByteArraySize(capacity)

即"节点区字节数 + 空闲栈对齐字节数 + 空闲栈字节数"。由于两者都是constexpr，你可以在编译期就得到缓冲区大小并用alignas静态数组声明内存（如第 4.3 节示例所示），完全避免堆分配。

7. 源码级纵深：底层红黑树如何工作

ExternalRedBlackTreeSet的本质是一个"外壳"，真正承载算法的是RedBlackTreeSetOrMapImpl<T, Nil>。理解它的实现，才算真正掌握这个容器（RedBlackTreeSetOrMapImpl.hpp）。

7.1. 节点结构

Node包含四个字段：m_parent、m_left、m_right（均为Index，即FwSizeType，用常量NONE = std::numeric_limits<Index>::max()表示"无节点"）、m_color（Color::BLACK或Color::RED），以及条目m_entry。所有节点存放在ExternalArray<Node>中，通过索引互相链接，不使用指针——这使整棵树可以被放到任意对齐的字节缓冲区中，序列化/搬移都很方便。

7.2. 红黑树不变量

注释中明确了红黑树的两个合法性条件：

1. 红孩子不变量（red child invariant）：不存在"红节点有红孩子"的情况；
2. 黑高度不变量（black height invariant）：对叶扩展树 T'（把每个缺失的孩子替换为黑色叶节点）而言，从任一节点到叶节点的每条路径经过的黑色节点数相同。

满足这两条不变量后，树是平衡的，find操作为O(log n)。

7.3. 插入与重平衡

insertNode先把新节点染红，再向上检查：

• 父为黑：无违例，结束；
• 父为红且祖父存在：根据叔父（uncle）颜色分两条路径——
  • 叔父为黑：通过旋转（rotateSubtree）＋换色修复，源码注释中用K1..K4的键序（K1 < K2 < K3 < K4）图示了"之字形（zig-zag）"与"直线形（zig-zig）"两种旋转形态；
  • 叔父为红：把父、叔、祖父换色，将"红孩子违例"向上推到祖父，循环继续。

7.4. 删除与重平衡

removeNode结合removeBlackLeafNode处理最棘手的"删除黑叶节点导致黑高度失衡"问题。重平衡循环根据**兄弟（sibling）、近侄（closeNephew）、远侄（distantNephew）**的颜色组合，执行多次旋转与重着色，源码中附有大量 ASCII 树形图逐阶段说明黑高度的变化。这些实现细节从单元测试Fw/DataStructures/test/ut/RedBlackTreeSetOrMapImplTest.cpp（及test/ut/STest/下基于 STest 规则/场景的测试）得到系统性验证。

7.5. 查找与定位

findNode维护parent/child/direction三个游标沿树下行：命中返回SUCCESS；未命中时，node返回"应插入位置的父节点"，direction返回应插入的方向（左/右）。insert与remove都复用它，保证插入/删除定位与查找使用同一套比较逻辑（==、<、>）。

8. 外部存储 vs 内部存储：如何选择

Fw/DataStructures同时提供红黑树集合的两个版本：

从源码结构看（RedBlackTreeSet.md 第 4 节），内部存储版本RedBlackTreeSet<T, C>的组合方式是：成员m_extSet（一个ExternalRedBlackTreeSet<T>）＋ 成员m_entries（Entry[C]数组），构造函数用ExternalRedBlackTreeSet<T>(m_entries, C)初始化。也就是说，内部存储版本只是外部存储版本的一个便捷封装——ExternalRedBlackTreeSet才是红黑树集合的真正核心实现。

因此实际选型建议：

• 需要把集合放进全局静态内存、共享内存或特定对齐的 DMA 缓冲区，或希望"容器对象与数据内存分离"（例如容器作为组件成员、数据内存单独静态分配）时，用ExternalRedBlackTreeSet；
• 希望最简用法、把容量固化在类型里（编译期可检查、可优化）时，用RedBlackTreeSet<T, C>；
• 元素数量规模很小且对查找性能不敏感时，可以退而选择数组实现ArraySet/ExternalArraySet，它们占用更少内存且遍历更缓存友好。

9. 测试与验证

仓库为ExternalRedBlackTreeSet提供了完整的单元测试，位于Fw/DataStructures/test/ut/ExternalRedBlackTreeSetTest.cpp，覆盖：

• ZeroArgConstructor：零参构造后getCapacity() == 0、getSize() == 0；
• TypedStorageConstructor：节点数组与空闲栈数组被底层正确引用；
• UntypedStorageConstructor：字节缓冲区被切分为节点区与空闲栈区且对齐正确；
• CopyConstructor、CopyAssignment：拷贝后 size 正确；
• Insert、Remove、Find、Clear等操作语义；
• 此外，通过 STest 规则/场景框架（test/ut/STest/目录）对底层RedBlackTreeSetOrMapImpl进行随机化压力测试，验证红黑树不变量在大量随机插入/删除后始终成立。

单元测试中还用到友元测试器（friend class ExternalRedBlackTreeSetTester），得以直接访问私有成员m_impl断言内部状态——这是 F´ 测试基础设施（STest）配合友元类进行白盒验证的典型模式。

10. 小结

ExternalRedBlackTreeSet<T>是 F´ 框架为嵌入式飞行软件准备的"零堆分配、容量外部可控"的红黑树集合：

• 接口层：继承SetBase<T>，提供insert/remove/find/clear/begin/end/getSize/getCapacity等标准集合操作，元素唯一，最坏O(log n)查找；
• 存储层：所有树节点放入调用方提供的后备内存（类型化双数组或对齐字节缓冲区），并通过getByteArrayAlignment/getByteArraySize在编译期计算布局；
• 算法层：底层RedBlackTreeSetOrMapImpl以索引链接 + 红黑节点着色实现完整插入/删除重平衡，配套 STest 随机测试保障不变量。

无论是作为RedBlackTreeSet<T, C>的内部引擎，还是直接用于需要精确控制内存布局的组件场景，它都是 F´ 数据容器家族中平衡"性能、确定性、内存可控"三要素的代表实现。相关参考：组件文档目录、头文件实现、底层实现、单元测试。

【免费下载链接】fprimeF´ - A flight software and embedded systems framework项目地址: https://gitcode.com/GitHub_Trending/fpr/fprime