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之后是连续的吗？(只是为了保留对我之前的声明的评论与未来的读者相关.)

Answer 1

它大致看起来像这样(借口我的MS Paint杰作):

在std::vector你有堆栈的实例是包含一个指向堆分配的缓冲区,再加上一些额外的变量来跟踪的大小和与向量的容量的小物件.

因此,当我push_back()对numbers向量时,它的旧元素似乎改变了它们的位置.

堆分配的缓冲区具有固定容量.当到达缓冲区的末尾时,将在堆上的其他位置分配新缓冲区,并将所有先前的元素移动到新的缓冲区中.因此他们的地址会改变.

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

粗略地说,是的.std::vector 只有在不进行重新分配的情况下,才能保证元素的迭代器和地址稳定性.

我知道,std::vector自从C++ 17以来,这是一个连续的容器

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

Answer 2

答案

它是一个连续的存储(1d阵列).每次它耗尽容量时,它都会被重新分配,并且存储的对象会被移动到新的更大的位置 - 这就是为什么你观察存储对象的地址会发生变化的原因.

一直都是这样,而不是从那以后C++17.

TL; DR

存储在几何上增长以确保摊销的要求O(1) push_back().在C++标准库(GCC,Clang,STLPort)和1.5(Cap _{n + 1}  = Cap _n  + Cap _n  / 2)的大多数实现中,增长因子是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具有更大块的块相同).这样,对于每列和每行查询,数据可以被合理地良好地存储(尽管这也可能需要来自存储器分配器的一些帮助).

Answer 3

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

但是,对矢量的许多操作可以重新定位整个存储器.

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

Answer 4

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

这正是它的工作方式以及为什么在重新分配时,追加元素确实使所有迭代器和内存位置无效¹.这不仅仅是自C++ 17以来一直有效,从那时起就一直如此.

这种方法有几个好处:

• 它非常易于缓存,因此效率很高.
• 该data()方法可用于将底层原始内存传递给使用原始指针的API.
• 在分配新的存储器的成本push_back,reserve或resize归结为恒定的时间,作为几何增长(每次摊销随时间push_back通过1.5在MSVC的因子被称为容量加倍了libc ++和libstdc ++,和大约赘生物).
• 它允许最受限制的迭代器类别,即随机访问迭代器,因为经典指针算法在连续存储数据时效果很好.
• 从另一个移动矢量实例的构造非常便宜.

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

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

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

Answer 5

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