F´ 数据结构的基石ArraySetOrMapImpl 外部存储集合实现详解【免费下载链接】fprimeF´ - A flight software and embedded systems framework项目地址: https://gitcode.com/GitHub_Trending/fpr/fprimeArraySetOrMapImpl是 F´F Prime飞行软件框架 Fw/DataStructures 库中一个final类模板它以数组为底层存储实现 set集合与 map映射两种数据结构。本文将以官方文档 ArraySetOrMapImpl.md 为骨架结合仓库源码与单元测试完整讲解其模板参数、内部存储布局、全部公开接口的算法细节以及如何配合ExternalArrayMap、ExternalArraySet在内存受限的嵌入式场景中落地使用。读完本文你将掌握这套“零堆分配、外部提供后备存储”的容器实现原理并能独立完成容量计算、存储绑定与增删查改的编码实践。1. 设计定位为何需要 ArraySetOrMapImpl在 F´ 的Fw/DataStructures中集合类遵循一套统一的概念约定见 sdd.mdsize大小当前存储在数据结构中的元素个数capacity容量数据结构最多可容纳的元素个数。数组类容器如Array的 size 与 capacity 恒等而 map/set 的 size 在 0 与 capacity 之间浮动。ArraySetOrMapImpl正是这一约定下“用数组实现 set/map”的公共实现内核它自身不持有存储而是通过ExternalArray指向调用方提供的外部内存从而做到零堆分配非常适合飞行软件与嵌入式系统的确定性内存需求。从源码结构看它的两个直接使用方分别是ExternalArrayMap以ArraySetOrMapImplK, V作为私有成员m_impl对外暴露 map 接口继承MapBaseK, VExternalArraySet以ArraySetOrMapImplT, Nil作为私有成员m_impl对外暴露 set 接口继承SetBaseT。即“外部存储 数组实现”这一职责被抽离到ArraySetOrMapImpl其上层只需做薄薄的接口转译。2. 模板参数与公共类型2.1. 模板参数ArraySetOrMapImpl定义于 Fw/DataStructures/ArraySetOrMapImpl.hpp声明为template typename KE, typename VN class ArraySetOrMapImpl final { ... };Kind名称用途typenameKEmap 中 key 的类型或 set 中元素的类型typenameVNmap 中 value 的类型当用作 set 时为Nil“一个模板两种语义”的实现技巧在于set 被建模为“值为 Nil 的 map”。VN Nil时容器退化为只关心 key 的集合。2.2. 类型别名 Entryusing Entry SetOrMapImplEntryKE, VN;Entry即SetOrMapImplEntryKE, VN内部持有两个成员m_keyOrElement与m_valueOrNil并静态断言见 SetOrMapImplEntry.hppKE必须可默认构造default constructibleKE必须可赋值assignable toKEVN必须可默认构造VN必须可赋值。这保证了数组可以原地构造条目、并支持按值赋值是数组式容器成立的编译期前提。2.3. 内部迭代器 ConstIteratorConstIterator是ArraySetOrMapImpl的公有内嵌类提供对元素集合的只读遍历并作为SetOrMapImplConstIteratorKE, VN的基类。从源码ArraySetOrMapImpl.hpp可以看到其实现要点持有指向容器的指针m_impl与当前下标m_indeximplKind()返回ImplKind::ARRAY标识这是数组式实现isInRange()判定m_index m_impl-m_sizegetEntry()在越界时通过FW_ASSERT触发断言保证访问安全increment()仅在范围内递增下标compareEqual()对“同时处于越界end状态”的两个迭代器判等支持it end()的惯用遍历写法。3. 内部存储布局成员变量ArraySetOrMapImpl只有两个私有成员见 ArraySetOrMapImpl.hpp名称类型用途默认值m_entriesExternalArrayEntry存放 set/map 条目的数组C 默认初始化m_sizeFwSizeType当前条目个数0类关系如下源自原文档m_entries本身是“带边界检查、使用外部内存的数组”ExternalArray.hpp。它的下标运算符对每个访问执行两条断言FW_ASSERT(this-m_elements ! nullptr); FW_ASSERT(i this-m_size, static_castFwAssertArgType(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 ArraySetOrMapImplKE, 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. 拷贝赋值 operatorArraySetOrMapImplKE, VN operator(const ArraySetOrMapImplKE, VN impl)算法见 ArraySetOrMapImpl.hpp若impl ! this依次执行m_entries impl.m_entries、m_size impl.m_size返回*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初始化status Success::FAILURE对i遍历[0, m_size)若m_entries[i].getKey() keyOrElement则把valueOrNil m_entries[i].getValue()置status SUCCESS并跳出返回status。对 set 语义VN Nil调用方如ExternalArraySet::find传入一个临时Nil对象仅凭返回状态判断元素是否存在。5.5. getCapacity / getSizeFwSizeType 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置status FAILURE遍历[0, m_size)若发现同 key 条目调用e.setValueOrNil(valueOrNil)更新旧值置SUCCESS并跳出若status FAILURE且m_size getCapacity()在m_entries[m_size]处构造新条目Entry(keyOrElement, valueOrNil)m_size置SUCCESS返回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置status FAILURE先缓存size m_size作为固定循环上界循环会在m_size被修改后立即 break避免边界漂移遍历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并跳出返回status。删除不存在的 key 返回FAILURE此时valueOrNil不被修改。5.8. setStorage绑定后备存储两种重载void setStorage(Entry* entries, FwSizeType capacity) // 类型化 void setStorage(ByteArray data, FwSizeType capacity) // 非类型化两者均两步完成见 ArraySetOrMapImpl.hpp调用m_entries.setStorage(...)绑定存储调用clear()把m_size归零。绑定存储即隐含“清空”确保新存储从干净状态开始。非类型化重载要求data按getByteArrayAlignment()对齐、且字节数不少于getByteArraySize(capacity)这两条前置条件同样由ExternalArray::setStorage内的FW_ASSERT强制校验对齐检查reinterpret_castuintptr_t(data.bytes) % alignof(T) 0容量检查使用除法形式size data.size / sizeof(T)以避免size * sizeof(T)溢出见 ExternalArray.hpp。6. 静态工具函数字节存储的量化接口6.1. getByteArrayAlignmentstatic constexpr U8 getByteArrayAlignment()返回ExternalArrayEntry::getByteArrayAlignment()即alignof(Entry)。在使用非类型化字节存储前必须以此值对齐缓冲区典型写法alignas(alignment) U8 bytes[...]。6.2. getByteArraySizestatic constexpr FwSizeType getByteArraySize(FwSizeType capacity)返回ExternalArrayEntry::getByteArraySize(capacity)即capacity * sizeof(Entry)。它给出容纳指定容量所需的最小字节数供静态数组、内存池或序列化缓冲区分配使用。这两个函数都是constexpr可在编译期完成对齐与尺寸计算。7. 组合使用ExternalArrayMap 与 ExternalArraySetArraySetOrMapImpl一般不直接对外使用而是作为下述两个公开容器的实现内核对应文档 ExternalArrayMap.md 与 ExternalArraySet.md。7.1. map键值对容器ExternalArrayMapK, V继承MapBaseK, V私有成员为ArraySetOrMapImplK, V m_impl每个公开方法都是对m_impl的薄转发。类型化存储示例using Map Fw::ExternalArrayMapU16, U32; constexpr FwSizeType capacity 10; Map::Entry entries[capacity]; // 类型化后备存储 Map map(entries, capacity); U32 value 0; auto status map.insert(0, 42); // 插入 (key0, value42) 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::ExternalArrayMapU16, 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元素集合容器ExternalArraySetT继承SetBaseT私有成员为ArraySetOrMapImplT, Nil m_impl。由于VN Nil它的Entry类型为SetOrMapImplEntryT, Nil所有 find/insert/remove 都通过临时Nil占位完成using Set Fw::ExternalArraySetU16; 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指针一致、容量正确非类型化存储构造用alignasgetByteArraySize分配字节数组后构造断言元素指针与字节地址一致拷贝构造与拷贝赋值插入后复制断言副本getSize() 1并验证 find 能取回原值 42。此外STest 规则/场景目录Fw/DataStructures/test/ut/STest/ArraySetOrMapImplTestRules.hpp 等以状态机随机测试方式对 insert/remove/find/迭代器的交互不变量做穷举式验证ArraySetTest、ArrayMapTest、ExternalArraySetTest、ExternalArrayMapTest等测试文件则从上层容器视角交叉覆盖同一内核。若想快速复现这些测试可按 F´ 标准流程在构建目录中启用对应测试目标并运行fprime-util测试命令。9. 复杂度与适用场景总结操作时间复杂度说明insertO(n)先线性查找 key最坏情况 O(n)命中则 O(1) 更新removeO(n)线性查找 O(1) 尾元素顶替findO(n)线性扫描begin/end/clearO(1)常数开销getSize/getCapacityO(1)直接读成员作为顺序数据结构ArraySetOrMapImpl及其上层容器不支持多线程并发直接访问。按 sdd.md 的约定在 F´ 组件中使用时应将其作为 active/queued 组件的成员借助组件队列实现对结构的互斥访问。它最适合以下场景零堆分配需求后备存储完全由调用方提供栈、静态区、内存池、字节缓冲区运行期不触发动态内存容量确定编译期即可通过getByteArrayAlignment()/getByteArraySize(capacity)精确预算内存小规模数据如遥测通道表、命令字典、健康检查成员名单等条目数有限、以确定性为首要目标的场景需要共享内存或通信缓冲区直接承载集合时非类型化setStorage(ByteArray, ...)提供了天然通路。若对查找性能有更高要求可对比同目录下的红黑树实现RedBlackTreeMap/RedBlackTreeSetO(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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考