如何分配STL映射？堆栈还是堆？ [英] How is a STL map allocated? Stack or Heap?

问题描述

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

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

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

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

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

I would like to know if the STL map in c++ has contiguous memory - or is the memory assigned to the heap?

解决方案

Since map is a dynamic container, the memory for its elements is dynamically allocated (whatever that means (it depends on a configurable allocator)!).

Moreover, map is a node-based container, so each element goes into a distinct, separate allocation (so as to permit maximal iterator and reference non-invalidation). Elements are almost certainly not contiguous in memory, and probably scattered about in a way that reflects how you added them.

Practically, a map will be implemented as some type of balanced tree in order to achieve logarithmic lookup, insertion and deletion times.

(If you want a data structure with contiguous storage and logarithmic lookup time, consider a sorted vector.)

这篇关于如何分配STL映射？堆栈还是堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！