std::vector 在内存中是什么样的？

Question

我读到 std::vector 应该是连续的。我的理解是，它的元素应该存储在一起，而不是分散在内存中。我只是接受了这一事实，并在例如使用其 data() 方法来获取底层连续内存时使用了这一知识。

但是，我遇到了一种情况，向量的内存以一种奇怪的方式表现：

 std::vector<int> numbers;
std::vector<int*> ptr_numbers;
for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
}

我希望这会给我一个包含一些数字的向量和一个指向这些数字的指针向量。但是，当列出 ptr_numbers 指针的内容时，会有不同的看似随机的数字，就好像我访问了错误的内存部分一样。

我试图检查每一步的内容：

 for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
    for (auto ptr_number : ptr_numbers)
       std::cout << *ptr_number << std::endl;
    std::cout << std::endl;
}

结果大致如下：

 1

some random number
2

some random number
some random number
3

所以似乎当我 push_back() 到 numbers 向量时，它的旧元素改变了它们的位置。

那么 std::vector 是一个连续的容器究竟是什么意思，为什么它的元素会移动？它是否可能将它们存储在一起，但在需要更多空间时将它们一起移动？

编辑： std::vector 仅从 C++17 开始是连续的吗？ （只是为了保持对我之前声明的评论与未来的读者相关。）

原文由 egst 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

它大致看起来像这样（请原谅我的 MS Paint 杰作）：

堆栈上的 std::vector 实例是一个小对象，其中包含指向堆分配缓冲区的指针，以及一些额外的变量来跟踪向量的大小和容量。

---

所以似乎当我 push_back() 到 numbers 向量时，它的旧元素改变了它们的位置。

堆分配的缓冲区具有固定容量。当你到达缓冲区的末尾时，一个 新的缓冲区 将被分配到堆上的其他地方，所有以前的元素都将被移动到新的缓冲区中。他们的地址因此会改变。

---

它是否可能将它们存储在一起，但在需要更多空间时将它们一起移动？

大致，是的。元素的迭代器和地址稳定性通过 std::vector 保证 只有在 没有重新分配发生的情况下。

---

我知道， std::vector 是一个连续的容器，仅自 C++17 起

std::vector 的内存布局自其首次出现在标准中以来没有改变。 ContiguousContainer 只是一个“概念”，用于在编译时将连续容器与其他容器区分开来。

原文由 Vittorio Romeo 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

答案

它是一个连续的存储（一维数组）。每次容量用完时，它都会重新分配并将存储的对象移动到新的更大的地方——这就是为什么你会观察到存储对象的地址发生变化的原因。

一直都是这样，不是从 C++17 。

TL;博士

存储量呈 几何 增长，以确保摊销 O(1) push_back() 的要求。在 C++ 标准库（ GCC 、 Clang 、 STLPort ）的大多数实现中，增长因子为 2（ Cap n+1 = Cap n + Cap n ），在 MSVC 变体。

如果您使用 vector::reserve(N) 和足够大的 N 预先分配它，那么当您添加新对象时，存储对象的地址不会改变。

在大多数实际应用中，通常值得将其预分配给至少 32 个元素，以跳过紧随其后的前几次重新分配（0→1→2→4→8→16）。

有时也可以放慢速度，切换到算术增长策略（ Cap n+1 = Cap n + Const ），或者在相当大的大小后完全停止，以确保应用程序不会浪费或增长内存。

最后，在一些实际应用中，例如基于列的对象存储，可能值得完全放弃连续存储的想法，转而采用分段存储（与 std::deque 所做的相同，但块更大） .通过这种方式，可以为每列和每行查询合理地本地化存储数据（尽管这也可能需要内存分配器的一些帮助）。

原文由 bobah 发布，翻译遵循 CC BY-SA 4.0 许可协议