48

我读到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 开始是连续的吗？（只是为了保持对我之前声明的评论与未来的读者相关。）

4

6 回答 6

73

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

矢量内存布局

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

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

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

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

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

我知道，这std::vector只是自 C++17 以来的连续容器

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

于 2018-09-14T10:30:16.107 回答
17

答案

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

一直都是这样，从那以后就没有了C++17。

TL; 博士

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

增长的 std::vector

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

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

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

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

于 2018-09-14T10:29:04.720 回答
7

std::vector作为一个连续的容器意味着你认为它意味着什么。

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

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

于 2018-09-14T10:29:11.233 回答
5

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

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

这种方法有几个好处：

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

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

  • 所有迭代器和指向元素的指针在修改意味着重新分配的向量时都会失效。这可能会导致细微的错误，例如在迭代向量的元素时擦除元素。
  • 不提供push_front（作为std::list或提供）之类的操作（有效，但可能很昂贵¹），以及多个向量实例的有效合并/拼接。std::dequeinsert(vec.begin(), element)

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

于 2018-09-14T10:40:07.650 回答
2

就实际结构而言，anstd::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)
};

libc++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"
      ;
}
于 2018-09-14T17:57:33.510 回答
-2

如果您尝试以这种方式对其进行编码，您将看到值保持不变，并且向量中每个值的地址与其相邻元素的差异为 4（有趣）。

std::vector<int> numbers;
std::vector<int*> ptr_numbers;

// adding values 0 up to 8 in the vector called numbers
for (int i = 0; i < 8; i++) {
    numbers.push_back(i);

}

// printing out the values inside vector numbers 
//and storing the address of each element of vector called numbers inside the ptr_numbers.
for (int i = 0; i != numbers.size(); i++) {
    cout << numbers[i] << endl;
    ptr_numbers.push_back(&numbers[i]);
}
cout << "" << endl;

// printing out the values of each element of vector ptr_numbers
for (int y = 0; y != ptr_numbers.size(); y++) {
    cout << *ptr_numbers[y] << endl;
}

// printing out the address of each element of vector ptr_numbers
for (int y = 0; y != ptr_numbers.size(); y++) {
    cout << &ptr_numbers[y] << endl;
}

当您遍历两个向量时。它们将输出相同的值。

于 2020-04-30T20:17:31.423 回答