时间戳

首页 > 解决方案 > std::vector 如何支持未知大小的自定义对象的连续内存

c++ - std::vector 如何支持未知大小的自定义对象的连续内存

问题描述

我正在为正确的心理模型和对std::vector.

我以为我知道的

当您创建一个类型为 T 的向量，然后为该向量保留 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| | ]

然后我们可以在随机访问时间内访问任何元素，因为如果我们请求向量的第 k 个元素，我们只需从向量开头的内存地址开始，然后“跳转”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 个元素？

标签： c++vector

解决方案

你的大小概念是有缺陷的。Astd::vector<type>有一个编译时间知道它要占用的空间大小。它还具有可以使用的运行时大小（这是在运行时分配的，并且向量包含指向它的指针）。你可以把它想象成这样

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

因此，当您有一个包含向量的事物的向量时，每个向量都Element成为向量，然后指向它们自己的存储点，例如

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

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

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

推荐阅读