企业官网建设流程全解析

F´ 框架 ExternalArrayMap 深度解析：外部存储的数组型映射容器

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

ExternalArrayMap是 F´（F Prime）飞行软件与嵌入式系统框架中Fw/DataStructures库提供的一个final类模板，它实现了一个存储内存由调用方外部提供的数组型键值映射（Map）。本文以 ExternalArrayMap.md 为骨架，结合 ExternalArrayMap.hpp、ArraySetOrMapImpl.hpp 与单元测试源码，完整讲解其模板参数、构造函数、存储管理方式、全部公共接口语义、底层实现原理与测试验证，帮助你在无堆分配的嵌入式场景中正确选用和驾驭该容器。

1. 设计定位：为什么需要“外部存储”的 Map

在 F´ 的 Fw/DataStructures 基础数据结构库 中，映射（Map）是一种将键关联到值、并提供insert、remove、find操作的数据结构。该库提供了四种 Map 模板，它们的差异集中在元素存储内存由谁提供以及底层组织方式上：

ExternalArrayMap的“外部存储（external storage）”含义是：存放条目的数组内存不归类所有，而是由使用者传入。典型做法是声明一个栈上的Entry数组（或对齐的字节数组）并通过构造函数或setStorage交给 Map。这带来了两个关键收益：

• 零堆分配：无需new/malloc，构造、插入、删除全在静态或栈内存中完成，行为可预测，适合飞行软件、航天器、嵌入式实时系统的确定性要求；
• 内存布局可控：存储可以在初始化时一次性规划，也可以放置于共享内存或固定内存池中。

与内部存储的ArrayMap相比，ExternalArrayMap自身不携带容量内存，因此对象体积更小（仅一个实现对象），更利于把“数据结构”和“存储内存”解耦管理。

需要特别说明的是：根据 sdd.md 的定义，Fw/DataStructures中的全部数据结构均为顺序数据结构（sequential data structures），不支持多线程直接并发访问。若要在线程间共享ExternalArrayMap，必须以 Active/Queued 组件的队列等方式外加并发控制。

2. 模板参数与类层次

2.1. 模板参数

ExternalArrayMap位于命名空间Fw，定义于 Fw/DataStructures/ExternalArrayMap.hpp，其类声明为：

template <typename K, typename V> class ExternalArrayMap final : public MapBase<K, V>

注意final关键字：该类模板不可被继承。另外键与值类型需要满足一定的可构造/可赋值要求，详见下文第 8 节对Entry类型 static_assert 的分析。

2.2. 基类与类层次

ExternalArrayMap<K, V>公开继承自抽象基类MapBase<K, V>（源码见 MapBase.hpp），而MapBase<K, V>又公开继承自SizedContainer。SizedContainer定义了“容量（capacity）与大小（size）”这一对核心概念：容量是数据结构最多可容纳的元素数，大小是当前实际存储的元素数；对 Map 而言，大小 S 始终位于 0 到容量 C 之间。完整的继承关系为：

在MapBase中，拷贝构造与赋值运算符被声明为private且= delete（这是所有 Map 派生类的共同约束），因此拷贝语义只能由具体实现类自行提供——ExternalArrayMap正是这样做的（见第 5、6 节）。

2.3. 公共类型

ExternalArrayMap定义了两个公共类型别名：

其中Entry是构造存储时数组的元素类型，也是本文大量示例中使用的Map::Entry entries[capacity]的由来。

3. 私有成员变量

ExternalArrayMap仅有一个私有成员，整个类的状态全部委托给它：

从源码看，m_impl的声明为ArraySetOrMapImpl<K, V> m_impl = {};（ExternalArrayMap.hpp 第 165 行）。ExternalArrayMap本身不实现任何算法，而是将所有操作直接转发给m_impl，自己仅承担“面向用户的 Map 语义层”职责。这意味着对ExternalArrayMap所有操作的语义分析，最终都要落到 ArraySetOrMapImpl.hpp 的实现上（见第 8 节）。

4. 构造函数与析构函数

4.1. 零参数构造函数

ExternalArrayMap()

每个成员变量以其默认值初始化。此时 Map尚未绑定任何存储，容量为 0，不可插入元素，必须先调用setStorage（见第 6.10、6.11 节）。

ExternalArrayMap<U16, U32> map;

测试 ExternalArrayMapTest.cpp 中的ZeroArgConstructor用例验证：零参数构造后getCapacity()与getSize()均为 0。

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

ExternalArrayMap(Entry* entries, FwSizeType capacity)

• entries必须指向一个至少包含capacity个Entry元素的原始数组；
• 内部调用setStorage(entries, capacity)。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity);

从 ExternalArrayMap.hpp 第 46-51 行可以看出，该构造函数的实现是：先调用基类MapBase<K, V>()，再执行this->setStorage(entries, capacity)。

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

ExternalArrayMap(ByteArray data, FwSizeType capacity)

• data必须按照getByteArrayAlignment()的返回值进行内存对齐；
• data至少包含getByteArraySize(capacity)字节；
• 内部调用setStorage(data, capacity)。

using Map = 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(ByteArray(&bytes[0], sizeof bytes), capacity);

非类型化存储允许你把 Map 的存储放进任意对齐的字节缓冲区（例如共享内存段、内存池中的某个槽位），ByteArray是对一段内存区域的轻量封装。测试中的UntypedStorageConstructor用例通过ImplTester验证：implTester.getEntries().getElements()与reinterpret_cast<Entry*>(bytes)指向同一地址，即字节缓冲区被正确 reinterpret 为Entry数组。

4.4. 拷贝构造函数

ExternalArrayMap(const ExternalArrayMap<K, V>& map)

语义为*this = map，即完整复制m_impl。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 3; Map::Entry entries[capacity]; // 调用提供后备存储的构造函数 Map m1(entries, capacity); // 插入一个条目 const U16 key = 0; const U32 value = 42; const auto status = m1.insert(key, value); ASSERT_EQ(status, Success::SUCCESS); // 调用拷贝构造函数 Map m2(m1); ASSERT_EQ(m2.getSize(), 1);

关键语义：ExternalArrayMap的拷贝构造/拷贝赋值复制的只是“实现对象”（指针 + 大小计数），并不会复制存储内存本身。因此源对象与目标对象在复制后会共享同一块后备存储。测试CopyConstructor用MapTester（ExternalArrayMap声明的友元测试类，见 ExternalArrayMapTest.cpp 第 15-24 行）直接检查了implTester2.getEntries().getElements() == entries，确认复制后目标对象仍指向原先传入的entries数组。

4.5. 析构函数

~ExternalArrayMap() override

定义为= default。由于存储是外部的，析构时不会释放任何元素内存，只销毁内部的实现对象本身。

5. 成员函数：赋值与迭代

5.1. operator=（拷贝赋值）

ExternalArrayMap<K, V>& operator=(const ExternalArrayMap<K, V>& map)

语义步骤：

1. 若&map != this（自赋值保护），则执行m_impl = map.m_impl；
2. 返回*this。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 3; Map::Entry entries[capacity]; // 调用提供后备存储的构造函数 Map m1(entries, capacity); // 插入一个条目 U16 key = 0; U32 value = 42; const auto status = m1.insert(key, value); ASSERT_EQ(status, Success::SUCCESS); // 调用零参数构造函数 ExternalArrayMap m2; ASSERT_EQ(m2.getSize(), 0); // 调用拷贝赋值运算符 m2 = m1; ASSERT_EQ(m2.getSize(), 1); value = 0; status = m2.find(key, value); ASSERT_EQ(status, Success::SUCCESS); ASSERT_EQ(value, 42);

与拷贝构造一致，m_impl = map.m_impl复制的ArraySetOrMapImpl内部持有的是ExternalArray<Entry>（一个指针 + 容量），所以赋值后m2的存储仍来自m1的存储指针。测试CopyAssignmentOperator验证了赋值后m2.getSize() == 1且可通过find取回值 42。ArraySetOrMapImpl::operator=同样带有自赋值判断（ArraySetOrMapImpl.hpp 第 151-157 行）。

5.2. begin

ConstIterator begin() const

返回指向 Map 中第一个条目的常量迭代器，实现为ConstIterator(this->m_impl.begin())。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; // 调用提供后备存储的构造函数 Map map(entries, capacity); // 插入一个条目 const auto status = map.insert(0, 1); ASSERT_EQ(status, Fw::Success::SUCCESS); // 获取 Map 的常量迭代器 auto it = map.begin(); // 通过迭代器访问底层的 const 条目 const auto key = it->getKey(); const auto value = it->getValue(); ASSERT_EQ(key, 0); ASSERT_EQ(value, 1);

5.3. end

ConstIterator end() const

返回迭代器的“结尾”值，实现为ConstIterator(this->m_impl.end())。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; // 调用提供后备存储的构造函数 Map map(entries, capacity); // 插入一个条目 auto status = map.insert(0, 1); ASSERT_EQ(status, Fw::Success::SUCCESS); // 获取迭代器 auto iter = map.begin(); // 检查 iter 不在结尾 ASSERT_NE(iter, map.end()); // 递增 iter iter++; // 检查 iter 到达结尾 ASSERT_EQ(iter, map.end());

关于迭代器语义需注意（详见 MapConstIterator.md）：

• 迭代顺序未指定，不要依赖插入顺序；
• isInRange()返回false时访问条目属于运行时错误，会触发断言失败；
• 不建议在更新 Map 之后继续使用迭代器解引用（operator*/operator->）。

5.4. clear

void clear() override

清空 Map 中所有条目，实现为m_impl.clear()。在底层，ArraySetOrMapImpl::clear()只是简单地把大小计数m_size置 0（ArraySetOrMapImpl.hpp 第 163 行）——既不清零元素内容，也不释放存储，因此 O(1)。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity); const auto status = map.insert(0, 3); ASSERT_EQ(map.getSize(), 1); map.clear(); ASSERT_EQ(map.getSize(), 0);

6. 成员函数：查找、容量与增删

6.1. find

Success find(const K& key, V& value) override

若存在键为key的条目，则将value设为该条目的值并返回Success::SUCCESS；否则返回Success::FAILURE。实现直接转发m_impl.find(key, value)。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity); U32 value = 0; auto status = map.find(0, value); ASSERT_EQ(status, Success::FAILURE); status = map.insert(0, 1); ASSERT_EQ(status, Success::SUCCESS); status = map.find(0, value); ASSERT_EQ(status, Success::SUCCESS); ASSERT_EQ(value, 1);

6.2. getCapacity

FwSizeType getCapacity() const override

返回 Map 的容量（最大条目数），即m_impl.getCapacity()；底层实现是返回存储数组m_entries的大小。容量在绑定存储时确定，之后不再变化。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity); ASSERT_EQ(map.getCapacity(), capacity);

6.3. getSize

FwSizeType getSize() const override

返回 Map 当前条目数，即m_impl.getSize()。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity); auto size = map.getSize(); ASSERT_EQ(size, 0); const auto status = map.insert(0, 3); ASSERT_EQ(status, Success::SUCCESS); size = map.getSize(); ASSERT_EQ(size, 1);

6.4. insert

Success insert(const K& key, const V& value) override

• 若 Map 中已存在键key的条目，则更新其值并返回SUCCESS；
• 否则若 Map 未满，则追加新条目(key, value)并返回SUCCESS；
• 否则返回FAILURE。

实现转发m_impl.insert(key, value)。底层细节见第 8 节。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity); auto size = map.getSize(); ASSERT_EQ(size, 0); const auto status = map.insert(0, 1); ASSERT_EQ(status, Success::SUCCESS); size = map.getSize(); ASSERT_EQ(size, 1);

6.5. remove

Success remove(const K& key, V& value) override

• 若存在键为key的条目，则把该条目的值存入value，从 Map 中移除该条目并返回SUCCESS；
• 否则返回FAILURE。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map::Entry entries[capacity]; Map map(entries, capacity); auto size = map.getSize(); ASSERT_EQ(size, 0); auto status = map.insert(0, 1); ASSERT_EQ(status, Success::SUCCESS); size = map.getSize(); ASSERT_EQ(size, 1); // 键不存在 U32 value = 0; status = map.remove(10, value); ASSERT_EQ(status, Success::FAILURE); ASSERT_EQ(size, 1); // 键存在 status = map.remove(0, value); ASSERT_EQ(status, Success::SUCCESS); ASSERT_EQ(size, 0); ASSERT_EQ(value, 1);

注意示例中的一个小细节：remove(10, value)失败后ASSERT_EQ(size, 1)断言的是此前保存的局部变量size（仍是 1），而不是map.getSize()；map.getSize()在移除成功后才真正变为 0。这并不影响语义，实际以map.getSize()为准。

6.6. setStorage（类型化数据）

void setStorage(Entry* entries, FwSizeType capacity)

entries必须指向一个至少包含capacity个Entry元素的原始数组。实现为m_impl.setStorage(entries, capacity)，即先绑定存储、随后清空 Map。

using Map = ExternalArrayMap<U16, U32>; constexpr FwSizeType capacity = 10; Map map; Map::Entry entries[capacity]; map.setStorage(entries, capacity);

该函数与类型化构造函数配合使用，适合“先零参数构造、后延迟绑定存储”的对象生命周期管理方式。

6.7. setStorage（非类型化数据）

void setStorage(ByteArray data, FwSizeType capacity)

data必须按getByteArrayAlignment()对齐，且至少包含getByteArraySize(capacity)字节。语义步骤：

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

using Map = 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(ByteArray(&bytes[0], sizeof bytes), capacity);

无论哪种setStorage重载，底层 ArraySetOrMapImpl.hpp 第 243-258 行的实现都是：先把字节数组 reinterpret 为ExternalArray<Entry>存储并绑定容量，再调用clear()将m_size置 0。因此对已使用过的 Map 重新绑定存储等价于一次彻底重置。

7. 公共静态函数：存储规划工具

7.1. getByteArrayAlignment

static constexpr U8 getByteArrayAlignment()

返回非类型化存储所需的字节对齐值，实现为ArraySetOrMapImpl<K, V>::getByteArrayAlignment()，最终来源于ExternalArray<Entry>::getByteArrayAlignment()。使用alignas时可直接引用该值。

7.2. getByteArraySize

static constexpr FwSizeType getByteArraySize(FwSizeType capacity)

返回指定容量下非类型化存储所需的字节总数，实现为ArraySetOrMapImpl<K, V>::getByteArraySize(capacity)。这两个函数均为constexpr，可在编译期用于声明定长数组（如第 4.3 节的U8 bytes[byteArraySize]），这正是嵌入式场景下“编译期规划内存”的关键手段。

8. 底层实现原理：ArraySetOrMapImpl 源码分析

ExternalArrayMap的全部算法逻辑位于 ArraySetOrMapImpl.hpp，理解它才能真正掌握行为边界。

8.1. 内部状态

ArraySetOrMapImpl<KE, VN>只有两个成员（第 283-286 行）：

// 存储条目的外部数组 ExternalArray<Entry> m_entries = {}; // 当前条目数 FwSizeType m_size = 0;

m_entries是ExternalArray<Entry>，持有元素指针与容量；m_size为逻辑大小。因此getCapacity()返回m_entries.getSize()，getSize()返回m_size。

8.2. Entry 类型约束：编译期 static_assert

Entry的实际类型SetOrMapImplEntry<K, V>在类定义处施加了四条编译期约束：

static_assert(std::is_default_constructible<KE>::value, "key must be default constructible"); static_assert(std::is_assignable<KE&, KE>::value, "key or element must be assignable"); static_assert(std::is_default_constructible<VN>::value, "value must be default constructible"); static_assert(std::is_assignable<VN&, VN>::value, "value must be assignable");

即键与值类型都必须是默认可构造且可赋值的。这是数组型实现能够用连续内存存放、覆盖写入条目的前提；不满足约束的类型会在编译期直接报错。

8.3. insert 的“更新优先、追加其次”语义

ArraySetOrMapImpl.hpp 第 199-217 行的insert实现分为两步：

1. 线性扫描已有m_size个条目，若发现相同键，则e.setValueOrNil(valueOrNil)原地更新值并返回SUCCESS；
2. 否则若m_size < getCapacity()，把新条目写入m_entries[m_size]，m_size++，返回SUCCESS；
3. 两者都不满足时返回FAILURE。

由此可见：insert具有“upsert”语义（键存在即更新，不存在即追加），且数组未满时插入总是成功，只有满员且键不存在时才失败。

8.4. remove 的“尾元素填补”策略

ArraySetOrMapImpl.hpp 第 221-239 行的remove实现值得注意：

const FwSizeType size = this->m_size; for (FwSizeType i = 0; i < size; i++) { if (this->m_entries[i].getKey() == keyOrElement) { valueOrNil = this->m_entries[i].getValue(); if (i < this->m_size - 1) { this->m_entries[i] = this->m_entries[this->m_size - 1]; // 用最后一个元素填补 } this->m_size--; status = Success::SUCCESS; break; } }

删除时，若被删条目不是最后一个，则用最后一个条目覆盖被删位置，再令m_size--。这是一种 O(1) 的 swap-remove 策略，代价是破坏了元素的插入顺序——因此迭代顺序不仅未指定，且在删除后更可能发生变化。这正是 MapConstIterator.md 强调“迭代顺序未指定”的深层原因。

8.5. find 的线性扫描

find同样在 ArraySetOrMapImpl.hpp 第 174-187 行以线性扫描实现：遍历m_entries[0..m_size)，用e.getKey() == keyOrElement判定命中。由于是数组实现，find/insert/remove 的时间复杂度均为 O(n)，适合条目数量较少、追求确定性与无堆分配的场景；若条目量大且对查找性能敏感，应考虑同库中的红黑树实现（RedBlackTreeMap / ExternalRedBlackTreeMap）。

8.6. 迭代器实现要点

ArraySetOrMapImpl内置了嵌套的ConstIterator（ArraySetOrMapImpl.hpp 第 36-112 行），其核心是保存m_impl指针与当前下标m_index：

• isInRange()判定m_index < m_impl->m_size；
• getEntry()在越界时通过FW_ASSERT触发断言失败；
• end()通过setToEnd()把m_index置为m_size；
• 两个迭代器的相等比较在“实现相同且下标相等”或“双方都越界”时成立。

ExternalArrayMap::ConstIterator则是对该迭代器的进一步封装（MapConstIterator<K, V>），在 API 层面向上抛出了统一的 Map 迭代接口。

9. 测试验证：ExternalArrayMapTest 全览

ExternalArrayMap的单元测试位于 Fw/DataStructures/test/ut/ExternalArrayMapTest.cpp，测试采用 F´ 的 STest 场景/规则测试框架，并与std::map作为模型对照。测试中的键类型为U16、值类型为U32、容量为 1024（见 MapTestState.hpp）。

其中CopyDataFrom用例直接调用了基类 MapBase.hpp 第 62-73 行提供的copyDataFrom(const MapBase<K, V>& map)：它先clear()自身，再取min(map.getSize(), this->getCapacity())为复制条数，用迭代器逐条insert，若插入失败则断言。注意其复制目标容量不足时会被截断，这正是测试覆盖size1 > capacity2分支的原因。

10. 典型使用场景与注意事项

10.1. 适用场景

• 无堆分配约束的嵌入式/飞行软件子系统，需要在初始化期或栈上规划全部内存；
• 条目数量小且可预知上限（例如遥测参数映射、命令 ID 到处理器的查表、有限状态机的状态属性表）；
• 希望 Map 对象本身体积最小、把存储独立到共享内存或内存池的场景。

10.2. 使用注意事项清单

1. 存储绑定是使用前提：零参数构造后容量为 0，插入必然失败；务必先调用带存储的构造函数或setStorage。
2. 容量在绑定时刻固定：getCapacity()反映存储数组大小，运行期不可扩容；条目数受m_size上限约束。
3. 拷贝共享存储：ExternalArrayMap的拷贝构造/赋值复制的是实现对象（指针 + 大小），复制后多个 Map 对象可能指向同一块存储，修改其一会影响另一个；这是与std::map拷贝语义的最大差异。
4. 删除会打乱顺序：remove采用尾元素填补策略，迭代顺序在删除操作后可能改变；任何遍历逻辑都不要依赖顺序。
5. 迭代器失效：更新 Map 后不要对既有迭代器解引用，越界访问会触发FW_ASSERT。
6. 线程安全：属于顺序数据结构，多线程访问需要外部加锁或经组件队列串行化。
7. 类型约束：键与值类型必须默认可构造、可赋值（编译期 static_assert 强制）。
8. 非类型化存储的对齐：使用ByteArray版本时务必用getByteArrayAlignment()对齐、用getByteArraySize(capacity)计算所需字节数，二者均为constexpr，可放心用于alignas定长数组。

11. 延伸阅读

• Fw/DataStructures 库总览：size/capacity 概念、顺序数据结构定义、完整类图
• MapBase抽象基类：Map 统一接口与copyDataFrom语义
• ArraySetOrMapImpl：数组型实现细节（Set/Map 共用）
• MapConstIterator：迭代器接口与断言行为
• SetOrMapImplEntry：条目类型与编译期约束
• 兄弟容器：ArrayMap（内部存储版）、ExternalArraySet（外部存储的集合版）、ExternalRedBlackTreeMap（O(log n) 外部存储版）
• 源码与测试：ExternalArrayMap.hpp、ExternalArrayMapTest.cpp

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