c++ - STL 映射是如何分配的？堆栈还是堆？

Question

我想知道mapC++ 中的 STL 是否具有连续内存 - 或者内存是否分配给堆？

Answer 1

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

此外，map它是一个基于节点的容器，因此每个元素都进入不同的、单独的分配（以允许最大迭代器和引用非无效）。元素在内存中几乎可以肯定是不连续的，并且可能以反映您添加它们的方式分散在各处。

实际上，映射将被实现为某种类型的平衡树，以实现对数查找、插入和删除时间。

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

Answer 2

它很可能是特定于实现的，您当然可以更改任何 STL 容器的分配器，但这不适合胆小的人，您需要查看您正在使用的标准库的文档。

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

（如果我理解正确，树节点包含value_type 的实例，它们是地图的键/值对）。

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