F´ 数据结构的基石：ArraySetOrMapImpl 外部存储集合实现详解

F´ 数据结构的基石：ArraySetOrMapImpl 外部存储集合实现详解

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

ArraySetOrMapImpl是 F´（F Prime）飞行软件框架 Fw/DataStructures 库中一个final类模板，它以数组为底层存储实现 set（集合）与 map（映射）两种数据结构。本文将以官方文档 ArraySetOrMapImpl.md 为骨架，结合仓库源码与单元测试，完整讲解其模板参数、内部存储布局、全部公开接口的算法细节，以及如何配合ExternalArrayMap、ExternalArraySet在内存受限的嵌入式场景中落地使用。读完本文，你将掌握这套“零堆分配、外部提供后备存储”的容器实现原理，并能独立完成容量计算、存储绑定与增删查改的编码实践。

1. 设计定位：为何需要 ArraySetOrMapImpl

在 F´ 的Fw/DataStructures中，集合类遵循一套统一的概念约定（见 sdd.md）：

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

数组类容器（如Array）的 size 与 capacity 恒等；而 map/set 的 size 在 0 与 capacity 之间浮动。ArraySetOrMapImpl正是这一约定下“用数组实现 set/map”的公共实现内核：它自身不持有存储，而是通过ExternalArray指向调用方提供的外部内存，从而做到零堆分配，非常适合飞行软件与嵌入式系统的确定性内存需求。

从源码结构看，它的两个直接使用方分别是：

• ExternalArrayMap：以ArraySetOrMapImpl<K, V>作为私有成员m_impl，对外暴露 map 接口（继承MapBase<K, V>）；
• ExternalArraySet：以ArraySetOrMapImpl<T, Nil>作为私有成员m_impl，对外暴露 set 接口（继承SetBase<T>）。

即“外部存储 + 数组实现”这一职责被抽离到ArraySetOrMapImpl，其上层只需做薄薄的接口转译。

2. 模板参数与公共类型

2.1. 模板参数

ArraySetOrMapImpl定义于 Fw/DataStructures/ArraySetOrMapImpl.hpp，声明为：

template <typename KE, typename VN> class ArraySetOrMapImpl final { ... };

“一个模板两种语义”的实现技巧在于：set 被建模为“值为 Nil 的 map”。VN = Nil时，容器退化为只关心 key 的集合。

2.2. 类型别名 Entry

using Entry = SetOrMapImplEntry<KE, VN>;

Entry即SetOrMapImplEntry<KE, VN>，内部持有两个成员m_keyOrElement与m_valueOrNil，并静态断言（见 SetOrMapImplEntry.hpp）：

• KE必须可默认构造（default constructible）；
• KE必须可赋值（assignable toKE&）；
• VN必须可默认构造；
• VN必须可赋值。

这保证了数组可以原地构造条目、并支持按值赋值，是数组式容器成立的编译期前提。

2.3. 内部迭代器 ConstIterator

ConstIterator是ArraySetOrMapImpl的公有内嵌类，提供对元素集合的只读遍历，并作为SetOrMapImplConstIterator<KE, VN>的基类。从源码（ArraySetOrMapImpl.hpp）可以看到其实现要点：

• 持有指向容器的指针m_impl与当前下标m_index；
• implKind()返回ImplKind::ARRAY，标识这是数组式实现；
• isInRange()判定m_index < m_impl->m_size；
• getEntry()在越界时通过FW_ASSERT触发断言，保证访问安全；
• increment()仅在范围内递增下标；
• compareEqual()对“同时处于越界（end）状态”的两个迭代器判等，支持it == end()的惯用遍历写法。

3. 内部存储布局：成员变量

ArraySetOrMapImpl只有两个私有成员（见 ArraySetOrMapImpl.hpp）：

类关系如下（源自原文档）：

m_entries本身是“带边界检查、使用外部内存的数组”（ExternalArray.hpp）。它的下标运算符对每个访问执行两条断言：

FW_ASSERT(this->m_elements != nullptr); FW_ASSERT(i < this->m_size, static_cast<FwAssertArgType>(i));

即：存储未绑定（空指针）或下标越界都会立即触发 F´ 断言系统（Assert.hpp），把数组式容器的安全隐患暴露在开发期。

4. 构造与析构

ArraySetOrMapImpl共提供 5 个构造/析构入口。

4.1. 零参数构造函数

ArraySetOrMapImpl() = default;

所有成员保持默认值：m_entries为空存储、m_size = 0。此时容器处于“未绑定存储”状态，getCapacity()返回 0，不能执行插入操作。

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

ArraySetOrMapImpl(Entry* entries, FwSizeType capacity)

要求entries指向至少capacity个Entry元素的连续内存。实现为直接调用setStorage(entries, capacity)，见 ArraySetOrMapImpl.hpp。

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

ArraySetOrMapImpl(ByteArray data, FwSizeType capacity)

data必须按getByteArrayAlignment()对齐，且至少包含getByteArraySize(capacity)字节。实现为调用setStorage(data, capacity)，内部通过reinterpret_cast把字节数组转换为Entry数组，并用 placement new 原地构造每个条目（见 ExternalArray.hpp）。这是把容器放进共享内存池、通信缓冲区或飞行配置文件的关键能力。

4.4. 拷贝构造函数

ArraySetOrMapImpl(const ArraySetOrMapImpl<KE, VN>& map)

直接执行*this = map，即复用拷贝赋值运算符完成成员复制。注意拷贝是浅拷贝存储指针、深拷贝 size的语义：m_entries的operator=会调用setStorage(a.m_elements, a.m_size)（见 ExternalArray.hpp），因此拷贝后两个容器共享同一块后备存储，但各自的m_size独立复制。

4.5. 析构函数

~ArraySetOrMapImpl() = default;

由于存储是外部提供的，析构不做释放；ExternalArray析构时若由它通过未类型化路径构造过元素（m_destroyElementsOnRelease == true），会调用每个元素的析构函数（见 ExternalArray.hpp）。

5. 核心成员函数：增删查改全解

5.1. 拷贝赋值 operator=

ArraySetOrMapImpl<KE, VN>& operator=(const ArraySetOrMapImpl<KE, VN>& impl)

算法（见 ArraySetOrMapImpl.hpp）：

1. 若&impl != this：依次执行m_entries = impl.m_entries、m_size = impl.m_size；
2. 返回*this。

自赋值防护（&impl != this判断）避免了对同一存储的重绑定问题。

5.2. begin / end：迭代遍历

ConstIterator begin() const; // 返回 ConstIterator(*this) ConstIterator end() const; // 先取 begin()，再调用 setToEnd()

begin()直接以当前容器构造迭代器；end()通过setToEnd()把迭代器下标推到m_size，从而支持标准的半开区间遍历：

for (auto it = impl.begin(); it != impl.end(); ++it) { // it.getEntry() 访问当前条目 }

迭代器getEntry()内部用FW_ASSERT(isInRange(), m_index, m_size)双重保证越界即断言。

5.3. clear：清空

void clear() { this->m_size = 0; }

只重置计数，不清空或销毁存储中的条目对象——数组式容器的“清空”是 O(1) 逻辑操作，后续插入会覆盖旧值。

5.4. find：按 key 查找

Success find(const KE& keyOrElement, VN& valueOrNil) const

算法（见 ArraySetOrMapImpl.hpp）：

1. 初始化status = Success::FAILURE；
2. 对i遍历[0, m_size)：若m_entries[i].getKey() == keyOrElement，则把valueOrNil = m_entries[i].getValue()，置status = SUCCESS并跳出；
3. 返回status。

对 set 语义（VN = Nil），调用方（如ExternalArraySet::find）传入一个临时Nil对象，仅凭返回状态判断元素是否存在。

5.5. getCapacity / getSize

FwSizeType getCapacity() const { return this->m_entries.getSize(); } FwSizeType getSize() const { return this->m_size; }

• getCapacity()委托给ExternalArray::getSize()，返回后备存储能容纳的最大条目数；
• getSize()返回当前条目数。

两者满足0 <= getSize() <= getCapacity()的不变式。

5.6. insert：插入（键存在则更新值）

Success insert(const KE& keyOrElement, const VN& valueOrNil)

算法（见 ArraySetOrMapImpl.hpp）：

1. 置status = FAILURE；
2. 遍历[0, m_size)：若发现同 key 条目，调用e.setValueOrNil(valueOrNil)更新旧值，置SUCCESS并跳出；
3. 若status == FAILURE且m_size < getCapacity()：在m_entries[m_size]处构造新条目Entry(keyOrElement, valueOrNil)，m_size++，置SUCCESS；
4. 返回status。

可见 insert 是“键在则更新值，键不在则追加，容量满则失败”的 upsert 语义。当用作 set 时（VN = Nil），重复插入同元素因第 2 步命中而静默成功，天然满足集合的去重约束。

说明：原文档 ArraySetOrMapImpl.md 的 insert 描述中包含维护“下一条目链接”的步骤；从当前源码看（ArraySetOrMapImpl.hpp），该链接维护已不再执行，append +m_size++即完成插入，逻辑更简洁，以源码为准。

5.7. remove：删除（尾元素顶替）

Success remove(const KE& keyOrElement, VN& valueOrNil)

算法（见 ArraySetOrMapImpl.hpp）：

1. 置status = FAILURE；先缓存size = m_size作为固定循环上界（循环会在m_size被修改后立即 break，避免边界漂移）；
2. 遍历i：若m_entries[i].getKey() == keyOrElement：
   • 回填valueOrNil = m_entries[i].getValue()（删除前把值交给调用方）；
   • 若i < m_size - 1，执行m_entries[i] = m_entries[m_size - 1]，即用最后一个条目顶替被删位置（swap-with-last 技巧，O(1) 移动、不打乱内部顺序以外的约束）；
   • m_size--，置SUCCESS并跳出；
3. 返回status。

删除不存在的 key 返回FAILURE，此时valueOrNil不被修改。

5.8. setStorage：绑定后备存储（两种重载）

void setStorage(Entry* entries, FwSizeType capacity) // 类型化 void setStorage(ByteArray data, FwSizeType capacity) // 非类型化

两者均两步完成（见 ArraySetOrMapImpl.hpp）：

1. 调用m_entries.setStorage(...)绑定存储；
2. 调用clear()把m_size归零。

绑定存储即隐含“清空”，确保新存储从干净状态开始。非类型化重载要求data按getByteArrayAlignment()对齐、且字节数不少于getByteArraySize(capacity)，这两条前置条件同样由ExternalArray::setStorage内的FW_ASSERT强制校验（对齐检查：reinterpret_cast<uintptr_t>(data.bytes) % alignof(T) == 0；容量检查使用除法形式size <= data.size / sizeof(T)以避免size * sizeof(T)溢出，见 ExternalArray.hpp）。

6. 静态工具函数：字节存储的量化接口

6.1. getByteArrayAlignment

static constexpr U8 getByteArrayAlignment()

返回ExternalArray<Entry>::getByteArrayAlignment()，即alignof(Entry)。在使用非类型化字节存储前，必须以此值对齐缓冲区（典型写法alignas(alignment) U8 bytes[...]）。

6.2. getByteArraySize

static constexpr FwSizeType getByteArraySize(FwSizeType capacity)

返回ExternalArray<Entry>::getByteArraySize(capacity)，即capacity * sizeof(Entry)。它给出容纳指定容量所需的最小字节数，供静态数组、内存池或序列化缓冲区分配使用。这两个函数都是constexpr，可在编译期完成对齐与尺寸计算。

7. 组合使用：ExternalArrayMap 与 ExternalArraySet

ArraySetOrMapImpl一般不直接对外使用，而是作为下述两个公开容器的实现内核（对应文档 ExternalArrayMap.md 与 ExternalArraySet.md）。

7.1. map：键值对容器

ExternalArrayMap<K, V>继承MapBase<K, V>，私有成员为ArraySetOrMapImpl<K, V> m_impl，每个公开方法都是对m_impl的薄转发。类型化存储示例：

using Map = Fw::ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; // 类型化后备存储 Map map(entries, capacity); U32 value = 0; auto status = map.insert(0, 42); // 插入 (key=0, value=42) ASSERT_EQ(status, Fw::Success::SUCCESS); status = map.find(0, value); // 查找 ASSERT_EQ(status, Fw::Success::SUCCESS); ASSERT_EQ(value, 42); status = map.remove(0, value); // 删除并取回旧值 ASSERT_EQ(status, Fw::Success::SUCCESS);

非类型化（字节池）存储示例：

using Map = Fw::ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; constexpr U8 alignment = Map::getByteArrayAlignment(); constexpr FwSizeType byteArraySize = Map::getByteArraySize(capacity); alignas(alignment) U8 bytes[byteArraySize]; // 对齐的字节缓冲区 Map map; map.setStorage(Fw::ByteArray(&bytes[0], sizeof bytes), capacity);

7.2. set：元素集合容器

ExternalArraySet<T>继承SetBase<T>，私有成员为ArraySetOrMapImpl<T, Nil> m_impl。由于VN = Nil，它的Entry类型为SetOrMapImplEntry<T, Nil>，所有 find/insert/remove 都通过临时Nil占位完成：

using Set = Fw::ExternalArraySet<U16>; constexpr FwSizeType capacity = 5; Set::Entry entries[capacity]; Set set(entries, capacity); auto status = set.insert(7); ASSERT_EQ(status, Fw::Success::SUCCESS); status = set.insert(7); // 重复插入：命中已有元素，依旧 SUCCESS ASSERT_EQ(status, Fw::Success::SUCCESS); ASSERT_EQ(set.getSize(), 1); // 集合去重 status = set.find(7); // 成员判定 ASSERT_EQ(status, Fw::Success::SUCCESS); status = set.remove(7); ASSERT_EQ(status, Fw::Success::SUCCESS);

8. 测试验证与正确性保障

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

• 零参数构造：断言getCapacity() == 0且getSize() == 0（未绑定存储）；
• 类型化存储构造：断言getElements()与传入的entries指针一致、容量正确；
• 非类型化存储构造：用alignas+getByteArraySize分配字节数组后构造，断言元素指针与字节地址一致；
• 拷贝构造与拷贝赋值：插入后复制，断言副本getSize() == 1，并验证 find 能取回原值 42。

此外，STest 规则/场景目录（Fw/DataStructures/test/ut/STest/ArraySetOrMapImplTestRules.hpp 等）以状态机随机测试方式对 insert/remove/find/迭代器的交互不变量做穷举式验证；ArraySetTest、ArrayMapTest、ExternalArraySetTest、ExternalArrayMapTest等测试文件则从上层容器视角交叉覆盖同一内核。若想快速复现这些测试，可按 F´ 标准流程在构建目录中启用对应测试目标并运行fprime-util测试命令。

9. 复杂度与适用场景总结

作为顺序数据结构，ArraySetOrMapImpl及其上层容器不支持多线程并发直接访问。按 sdd.md 的约定，在 F´ 组件中使用时应将其作为 active/queued 组件的成员，借助组件队列实现对结构的互斥访问。

它最适合以下场景：

• 零堆分配需求：后备存储完全由调用方提供（栈、静态区、内存池、字节缓冲区），运行期不触发动态内存；
• 容量确定：编译期即可通过getByteArrayAlignment()/getByteArraySize(capacity)精确预算内存；
• 小规模数据：如遥测通道表、命令字典、健康检查成员名单等条目数有限、以确定性为首要目标的场景；
• 需要共享内存或通信缓冲区直接承载集合时，非类型化setStorage(ByteArray, ...)提供了天然通路。

若对查找性能有更高要求，可对比同目录下的红黑树实现RedBlackTreeMap/RedBlackTreeSet（O(log n) 查找，实现复杂度和内存占用更高），按“数组式简单确定 vs 树形对数查找”的取舍选择。

10. 参考文件索引

• 官方文档：ArraySetOrMapImpl.md、ExternalArray.md、SetOrMapImplEntry.md、ExternalArrayMap.md、ExternalArraySet.md、sdd.md
• 核心源码：ArraySetOrMapImpl.hpp、ExternalArray.hpp、SetOrMapImplEntry.hpp、ExternalArrayMap.hpp、ExternalArraySet.hpp
• 单元测试：ArraySetOrMapImplTest.cpp、ArraySetOrMapImplTestRules.cpp、ArraySetOrMapImplTestScenarios.cpp

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