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 是一个连续的容器，它的确切含义是什么？为什么它的元素会移动？它是否可以将它们存储在一起，但在需要更多 space 时将它们一起移动？

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

Answer 1

答案

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

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

TL;博士

存储空间正在呈几何增长，以确保满足分摊 O(1) push_back() 的需求。增长因子为2(Cap_n+1 =Cap_n +Cap_n) 在大多数 C++ 标准库实现中（GCC, Clang, STLPort) and 1.5 (Cap_n+1 = Cap_n + Cap_n / 2) in the MSVC 变体。

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

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

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

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

Answer 2

std::vector 作为一个连续的容器意味着您所想的那样。

但是，向量上的许多操作可以重新定位整块内存。

一个常见的情况是当你向它添加元素时，向量必须增长，它可以重新分配并复制所有元素到另一块连续的内存。

Answer 3

大致是这样的（原谅我的 MS Paint 杰作）：

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

So it seems as though when I push_back() to the numbers vector, its older elements change their location.

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

Does it maybe store them together, but moves them all together, when more space is needed?

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

I am aware, that std::vector is a contiguous container only since C++17

std::vector 的内存布局自从它首次出现在标准中以来就没有改变过。 ContiguousContainer 只是添加的 "concept" 以在编译时将连续容器与其他容器区分开来。

Answer 4

So what does it exactly mean, that std::vector is a contiguous container and why do its elements move? Does it maybe store them together, but moves them all together, when more space is needed?

这正是它的工作原理，以及为什么在重新分配发生时追加元素确实会使所有迭代器和内存位置无效¹。这不仅自 C++17 以来有效，而且从那时起一直如此。

这种方法有几个好处：

它对缓存非常友好，因此效率很高。
data() 方法可用于将底层原始内存传递给使用原始指针的 API。
在 push_back、reserve 或 resize 时分配新内存的成本归结为常数时间，因为几何增长会随着时间的推移而摊销（每次 push_back称为容量在 libc++ 和 libstdc++ 中翻了一番，在 MSVC 中大约增长了 1.5 倍）。
它允许最受限制的迭代器类别，即随机访问迭代器，因为经典指针算法在数据连续存储时效果很好。
从另一个矢量实例移动构造非常便宜。

这些含义可以被认为是这种内存布局的缺点：

所有迭代器和指向元素的指针在对向量进行暗示重新分配的修改时失效。例如，这可能会导致细微的错误。在遍历向量的元素时擦除元素。
不提供像 push_front（如 std::list 或 std::deque 提供）的操作（insert(vec.begin(), element) 有效，但可能很昂贵¹），以及高效的 merging/splicing 多个矢量实例。

¹ 感谢@FrançoisAndrieux 指出这一点。

Answer 5

就实际结构而言，std::vector 在内存中看起来像这样：

struct vector {    // Simple C struct as example (T is the type supplied by the template)
  T *begin;        // vector::begin() probably returns this value
  T *end;          // vector::end() probably returns this value
  T *end_capacity; // First non-valid address
  // Allocator state might be stored here (most allocators are stateless)
};

Relevant code snippet from the libc++ implementation as used by LLVM

打印std::vector的原始内存内容：
（如果您不知道自己在做什么，请不要这样做！）

#include <iostream>
#include <vector>

struct vector {
    int *begin;
    int *end;
    int *end_capacity;
};

int main() {
    union vecunion {
        std::vector<int> stdvec;
        vector           myvec;
        ~vecunion() { /* do nothing */ }
    } vec = { std::vector<int>() };
    union veciterator {
        std::vector<int>::iterator stditer;
        int                       *myiter;
        ~veciterator() { /* do nothing */ }
    };

    vec.stdvec.push_back(1); // Add something so we don't have an empty vector

    std::cout
      << "vec.begin          = " << vec.myvec.begin << "\n"
      << "vec.end            = " << vec.myvec.end << "\n"
      << "vec.end_capacity   = " << vec.myvec.end_capacity << "\n"
      << "vec's size         = " << vec.myvec.end - vec.myvec.begin << "\n"
      << "vec's capacity     = " << vec.myvec.end_capacity - vec.myvec.begin << "\n"
      << "vector::begin()    = " << (veciterator { vec.stdvec.begin() }).myiter << "\n"
      << "vector::end()      = " << (veciterator { vec.stdvec.end()   }).myiter << "\n"
      << "vector::size()     = " << vec.stdvec.size() << "\n"
      << "vector::capacity() = " << vec.stdvec.capacity() << "\n"
      ;
}

std::vector 在记忆中是什么样子的？

What does std::vector look like in memory?

c++

memory

vector

contiguous

答案

TL;博士