std :: vector如何支持未知大小的自定义对象的连续内存 [英] How does std::vector support contiguous memory for custom objects of unknown size

问题描述

我正在为正确的思维模式和对 std :: vector 的理解而苦苦挣扎。

I'm struggling with the correct mental model and understanding of std::vector.

当您创建类型为T的向量，然后为该向量保留N个元素时，编译器基本上会找到并保留一个连续的内存块，即 N * sizeof（T）个字节。例如，

When you create a vector of type T and then reserve N elements for the vector, the compiler basically finds and reserves a contiguous block of memory that is N * sizeof(T) bytes. For example,

// Initialize a vector of int
std::vector<int> intvec;

// Reserve contigious block of 4 4-byte chunks of memory
intvec.reserve(4);  // [ | | | ]

// Filling in the memory chunks has obvious behavior:
intvec.push_back(1);  // [1| | | ]
intvec.push_back(2);  // [1|2| | ]

然后，我们可以在随机访问时间内访问任何元素，因为如果我们要求向量，我们只需从向量开始处的内存地址开始，然后跳转 k * sizeof（T）字节即可到达第k个元素。

Then we can access any element in random access time because, if we ask for the kth element of the vector, we simply start at the memory address of the start of the vector and then "jump" k * sizeof(T) bytes to get to the kth element.

我的思维模型针对大小未知/变化的自定义对象分解。例如，

My mental model breaks down for custom objects of unknown/varying size. For example,

class Foo {

public:
    Foo() = default;
    Foo(std::vector<int> vec): _vec{vec} {}

private:
    std::vector<int> _vec;
};

int main() {

    // Initialize a vector Foo
    std::vector<Foo> foovec;

    // Reserve contigious block of 4 ?-byte chunks of memory
    foovec.reserve(4);  // [ | | | ]

    // How does memory allocation work since object sizes are unkown?
    foovec.emplace_back(std::vector<int> {1,2});        // [{1,2}| | | ]
    foovec.emplace_back(std::vector<int> {1,2,3,4,5});  // [{1,2}|{1,2,3,4,5}| | ]

    return 0;
}

由于我们不知道每个Foo的大小，如何 foovec.reserve（）分配内存？此外，您如何获得随机访问时间，而我们不知道要跳多远才能到达第k个元素？

Since we don't know the size of each instance of Foo, how does foovec.reserve() allocate memory? Furthermore, how could you achieve random access time we don't know how far to "jump" to get to the kth element?

推荐答案

您的尺寸概念有缺陷。 std :: vector< type> 具有已知的编译时间，它将占用空间大小。它还具有可以使用的运行时大小（这是在运行时分配的，并且向量包含指向它的指针）。您可以像这样

Your concept of size is flawed. A std::vector<type> has a compile time known size of space it is going to take up. It also has a run time size that it may use (this is allocated at run time and the vector holds a pointer to it). You can picture it laid out like

+--------+
|        |
| Vector |
|        |
|        |
+--------+
     |
     |
     v
+-------------------------------------------------+
|         |         |         |         |         |
| Element | Element | Element | Element | Element |
|         |         |         |         |         |
+-------------------------------------------------+

因此，当您拥有包含矢量的事物的矢量时，每个元素成为向量，然后指向其他位置的自己的存储点

So when you have a vector of things that have a vector in them, each Element becomes the vector and then those point of to their own storage somewhere else like

+--------+
|        |
| Vector |
|        |
|        |
+----+---+
     |
     |
     v
+----+----+---------+---------+
| Object  | Object  | Object  |
|  with   |  with   |  with   |
| Vector  | Vector  | Vector  |
+----+----+----+----+----+----+
     |         |         |   +---------+---------+---------+---------+---------+
     |         |         |   |         |         |         |         |         |
     |         |         +-->+ Element | Element | Element | Element | Element |
     |         |             |         |         |         |         |         |
     |         |             +-------------------------------------------------+
     |         |    +-------------------------------------------------+
     |         |    |         |         |         |         |         |
     |         +--->+ Element | Element | Element | Element | Element |
     |              |         |         |         |         |         |
     |              +-------------------------------------------------+
     |    +-------------------------------------------------+
     |    |         |         |         |         |         |
     +--->+ Element | Element | Element | Element | Element |
          |         |         |         |         |         |
          +---------+---------+---------+---------+---------+

这样，所有向量都彼此相邻，但元素向量可以位于内存中的任何其他位置。因此，您不想将 std：vector< std :: vector< int>< 用作矩阵。所有子向量都将存储到任何地方，因此行之间没有局部性。

This way all of the vectors are next to each other, but the elements the vectors have can be anywhere else in memory. It is for this reason you don't want to use a std:vector<std::vector<int>> for a matrix. All of the sub vectors get memory to wherever so there is no locality between the rows.

请注意，这适用于所有可识别分配器的容器，因为它们不会将元素直接存储在容器中。对于 std :: array 而言，情况并非如此，因为像原始数组一样，元素是容器的一部分。如果您有 std :: array< int，20> ，则至少为 sizeof（int）* 20 字节大小。

Do note that this applies to all of the allocator aware containers as they do not store the elements inside the container directly. This is not true for std::array as, like a raw array, the elements are part of the container. If you have an std::array<int, 20> then it is at least sizeof(int) * 20 bytes in size.

这篇关于std :: vector如何支持未知大小的自定义对象的连续内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！