std::vector 如何支持未知大小的自定义对象的连续内存
我正在为正确的心智模型和对 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 个元素，我们只需从向量开始的内存地址开始，然后跳转"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 有一个编译时已知的空间大小.它还有一个可以使用的运行时大小(这是在运行时分配的，向量持有一个指向它的指针).你可以把它想象成这样
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 |
| | | | | |
+-------------------------------------------------+
所以当你有一个向量，其中有一个向量时，每个 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 用于矩阵.所有子向量都将内存分配到任何地方，因此行之间没有位置.
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 那么它的大小至少是 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.
相关文章