我正在为正确的心智模型和对 std::vector 的理解而苦苦挣扎。

我以为我知道的

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

// 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| | ]

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

自定义对象

对于未知/可变大小的自定义对象，我的心智模型会崩溃。例如，

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 个元素，如何实现随机访问时间？

最佳答案

您的尺寸概念有问题。 std::vector<type>有一个编译时间已知的空间大小，它将占用。它还有一个可以使用的运行时大小(这是在运行时分配的， vector 持有指向它的指针)。你可以把它想象成这样

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

所以当你有一个包含 vector 的 vector 时，每个 vector Element成为 vector ，然后那些点指向他们自己的存储在其他地方

+--------+
|        |
| 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 |
          |         |         |         |         |         |
          +---------+---------+---------+---------+---------+
          

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

请注意，这适用于所有分配器感知容器，因为它们不会直接将元素存储在容器内。这对于 std::array 是不正确的因为，就像原始数组一样，元素是容器的一部分。如果你有 std::array<int, 20>那么它至少是sizeof(int) * 20字节大小。

关于c++ - std::vector 如何支持未知大小的自定义对象的连续内存，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55478523/