嵌入式系统中使用STL且内存非常有限的问题

Question

我目前正在构建一个嵌入式系统，使用 ARM Cortex M3 处理器和 64 KB SRAM。目前，我正在寻找一种方法来确保 STL 容器的确定性能，其中包括确保在运行时不会耗尽内存。

我主要关注 STL 容器如何执行动态内存分配。虽然我可以使用自定义分配器使这些结构从我设置的池中获取内存，但我需要为每个结构设置单独的池，以确保一个实例不能占用另一个实例的空间。

我与其他人一起在此项目上工作，他们不想涉及原始内存分配，而希望能够使用“众所周知”的数据结构（堆栈、队列、deque 等）。因此，我目前正在考虑在 C 数组周围构建包装器以提供这些结构。这将允许静态分配支持这些容器所需的内存，并允许其他开发人员在运行时之前根据编译器提供的代码大小信息了解他们已实例化的容器的大小。在我看来，这保证了内存故障问题不能在运行时发生，并且极大地简化了系统设计。

另一个选项涉及在系统初始化时分配 STL 容器。初始化期后，不会发生额外的动态内存分配。但据我所知，标准 C++ STL 数据结构不支持这一点 - 这将需要像 vector 一样能够预先分配堆栈等容器。

我想听听关于我在标准 C 数组周围构建类的建议？此外，是否有更简单的方法在编译时分配静态大小的 STL 容器，例如静态大小的堆栈或队列？（我知道这对于 vector 可能是可能的，但对于其他容器我不确定）

注意：我已经阅读了另一个问题（Embedded C++ to use STL or not），但该问题的作者没有明确说明他们拥有多少内存（除了使用 ARM7 处理器之外），也似乎没有考虑与我的解决方案类似的解决方案。

第二点说明：我知道对于一些开发人员来说，64 KB的SRAM可能看起来是很大的内存。实际上，我在具有更少内存的AVR处理器上进行过开发，因此我理解这种观点。然而，从我的当前（也许不太了解）的观点来看，在谈论STL容器时，64 KB的内存并不算多。

- BSchlinker

---

最终，我选择了EASTL。它易于使用且运行良好。 - BSchlinker

Answer 1

这个问题有点混乱和奇怪。首先，让我们澄清一些误解。

你提到 "stack、queue、deque" 这三个名称，然而其中两个不是容器。 stack 和 queue 是容器适配器。实际上它们并没有直接存储元素，只是简单地中介它们的接口。 stack 确保你只能 push、pop 和获取顶部元素。 queue 确保你只能 push-back、pop-front 和获取前面的元素（尽管还可以获取后面的元素）。

容器适配器实际上将其模板参数之一作为要使用的实际容器类型。 因此，你可以使用 std::list 与 stack 一起使用。我不一定建议这样做（根据你的用例），但你可以这样做。

容器适配器不关心内存；分配内存的是它们所使用的容器。

如果你在一个非常受限制的内存系统中运行，你会发现标准容器可能不太友好。即使你使用分配器为它们提供固定大小的内存缓冲区，那些分配器也只能通过抛出异常来阻止实际容器分配更多的内存。

举个例子，如果你有一个需要在2KB内工作的 vector，如果它的大小为1KB，并尝试分配2.5KB以上的内存，则分配器不能简单地返回2KB。 它只能返回所请求的2.5KB或者抛出 std::bad_alloc。这是你唯一的两个选择。分配器无法告诉 vector 它可以获得比其拥有的空间更多但不如要求的空间那么多的内存。

同样地，分配器要提供新的内存，即刚刚分配的可以复制到其中的新内存。它不应该仅仅提供同一块内存，只是有更多空间可用。这样做可能会在某些实现中引起问题。

分配器旨在为访问提供不同的内存区域；它们并不适合限制容器本身的大小。

我的建议是查找EASTL的副本。它真正为此类事情而设计。我给你提供的 Github 存储库有一些错误修复等，但它基本上还是相同的。这不是一段糟糕的代码。他们的 STL-like 容器提供了大部分接口，因此它们可以作为基本替换品。但是它们提供了特殊的功能，以专门控制内存分配。

- Nicol Bolas

---

感谢指向EASTL源代码的指针 - 我不知道该源代码曾经被发布过。上次我研究EASTL（很久以前），似乎只有n2271文档可用（http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html）。希望我有时间看一下迄今发布的源代码。 - Michael Burr

这或许是 cplusplus.com 给我带来的又一个例子，因为我从它们（http://www.cplusplus.com/reference/stl/）那里学到了将“STL容器”与堆栈/队列等联系起来。我知道 list 可以被用作堆栈等（我上过数据结构课，在那里我必须构建这些容器适配器）。我知道 EASTL，尽管在其他答案中似乎有一些争议（请参见我在原始问题中链接的答案）。 - BSchlinker

@Ylisar：首先，deque是一个容器，而不是适配器；它实现了一个特定的内存模型。其次，stack和queue是适配器并不是一个实现细节。你可以为它们换用不同的容器，这意味着它们的内存模型取决于你使用的实际容器，而不是stack和queue类本身。因此，如果你想要固定大小的stack，查看stack类本身是错误的地方。 - Nicol Bolas

@NicolBolas--但是它们在左侧列为“STL容器”下。多年来，我一直使用那个小菜单框来选择“queue”，“stack”等，而且总是看到“STL容器”上面 - 从未出现过关于“STL容器适配器”的任何内容。我可能因为没有阅读容器页面以查看澄清而有错 - 但是您可以看到我会变得困惑。 - BSchlinker

请注意，EASTL实现（发布版）不包括deque，尽管根据EASTL文档，这里似乎有一种尝试实现的方法：http://www.mpgh.net/forum/174-battlefield-3-bf3-hacks/380016-eastl-deque-reverse-engineered.html。 - BSchlinker

Answer 2

我知道这是一个旧的帖子，但对于任何有兴趣的人，我维护了一个类似STL的嵌入式应用程序模板库。完全没有堆使用。

嵌入式模板库（MIT许可证）https://www.etlcpp.com

- JWellbelove

Answer 3

除了EASTL之外，您还可以使用boost中的static_vector。它与std::vector共享大部分API，并且可以与容器适配器（队列、堆栈）一起使用。它不会抛出std::bad_alloc，而是可以调用throw_bad_alloc()，因此也可以在嵌入式环境中使用，而无需使用异常。

- KovBal