STL map是如何分配内存的？是在栈上还是堆上？

Question

我想知道C++中的STL map是否拥有连续的内存空间，还是分配在堆上？

- Master Oogway

---

这个问题与“对齐”有什么关系？ - Kerrek SB

你不能在“堆栈”内存中使用"map"；这是不可能的。 - user541686

@Mehrdad: 我的自定义“stack_allocator”想和你聊聊。 :P - Xeo

@Xeo：我觉得我们对“stack”这个词的意思理解不一样。:P 我说的是CPU堆栈，而不仅仅是看起来像堆栈的任何东西。但实际上，我一直在考虑制作一个类似堆栈的分配器。你的分配器的目的是在以堆栈方式发生时提供高效的分配吗？如果是这样，你介意分享一下吗？:D 编写分配器真是一件痛苦的事情... - user541686

你关心这个问题有什么具体原因吗？如果你能解释一下为什么想知道，或许我们可以提供更多帮助。 - Martin York

Answer 1

由于map是一个动态容器，它的元素内存是动态分配的（这取决于可配置的分配器！）。

此外，map是一个基于节点的容器，因此每个元素都进入不同的、单独的分配（以便允许最大的迭代器和引用非失效）。元素几乎肯定是不连续的，可能散布在反映添加方式的方式上。

实际上，为了实现对数级别的查找、插入和删除时间，map将被实现为某种平衡树。

（如果您需要具有连续存储和对数查找时间的数据结构，请考虑使用排序向量。）

- Kerrek SB

---

除非您使用一种内存分配器使项目在内存中连续，或者您非常幸运，否则所有情况都是真的。 :) - abarnert

@abarnert：它们可以很容易地与stack_allocator相邻，后者以内存缓冲区作为输入进行分配，但它们可能不会按照内存中的排序顺序排列。 - Xeo

@Xeo：每个节点可能都有一些节点开销，这意味着实际数据可能永远不会是连续的。 - Kerrek SB

@Kerrek：确实如此，迭代的节点之间的链接。 - Xeo

Answer 2

这很可能是与实现相关的问题，您可以更改任何STL容器的分配器，但这并不适合新手，您需要查看使用的标准库文档。

无论如何，map通常被实现为红黑树，而树节点位于堆上。

（如果我理解正确）树节点包含value_type的实例，这些实例是您的映射的键/值对。

请注意，对于任何容器来说，堆栈都不是一个好的存储想法，因为堆栈应该被视为一种稀缺资源。

- user195488