STL C++中的内存分配

Question

我对STL C++中的内存重新分配有些困惑。例如，如果我声明一个vector，并不断向其中添加元素，则该向量在某个时刻需要重新分配内存空间，并将所有现有元素复制到其中。对于链表，由于元素未连续存储在堆栈中，因此不需要重新分配；每个元素使用指针指向下一个元素。

我的问题是，其他STL（如string、map、unordered_map）是否也需要重新分配内存？

- dance dance

---

当然，对于每个容器来说都不同，但列出它们可能不适合这个站点。 - BoBTFish

“string” 大多数情况下与 “vector” 相同。 - phantom

重新分配内存会使迭代器失效，因此这几乎是 https://dev59.com/5XA75IYBdhLWcg3wYH3I 的重复。 - Jerry Coffin

你要查找的术语是“容器”，而不是STL。STL是一个库，它强烈地启发了C++标准库中的容器。 - Ulrich Eckhardt

Answer 1

(免责声明: 这里指定的所有具体数据结构可能不是标准所必需的, 但它们有助于将规则与具体内容联系起来)

std::string ~= std::vector; 它是一个动态数组, 如果您一直在其末尾添加元素, 那么在某个时刻它将重新分配您的元素。

std::list: 每个元素都是一个新的链表节点, 因此无论何时插入新元素, 都不会进行任何重新分配。

std::deque: 它通常由多个页面的元素组成; 当一个页面满了时, 会分配一个新页面并将其添加到页面列表中; 出于这个原因, 您的元素永远不会被重新分配, 如果您一直在开头或结尾添加元素, 您的元素也永远不会被移动。

std::map/std::multimap/std::set/std::multiset: 通常是一个二叉树, 每个元素都分配在自己的位置; 永远不会执行任何重新分配。

std::unordered_map/std::unordered_multimap/std::unordered_set/std::unordered_multiset: 一个哈希表; 当表中的元素足够多时, 将发生重新哈希和重新分配。

- Matteo Italia

Answer 2

几乎所有的STL容器内存都是在堆上分配的，即使是vector。普通数组和std::array模板可能是唯一具有栈上内存的数据结构。

如果您的问题是关于连续内存分配（无论是在堆栈还是堆上），那么大概只有普通数组、std::array、std::vector拥有连续的内存。几乎所有其他容器，如list、deque、map、set等都没有连续的内存分配。

- Rushikesh