C++中的矢量存储

Question

我希望存储一个大的d维点矢量(d固定和小:<10).

如果我定义一个Pointas vector<int>,我认为a vector<Point>会在每个位置存储指向Point的指针.

但是,如果将a定义Point为固定大小的对象,如: std::tuple<int,int,...,int>或者std::array<int, d>,程序是否会将所有点存储在连续的内存中,还是会保留额外的间接级别？

如果答案是数组避免额外的间接,那么在扫描时,这会对性能(缓存利用局部性)产生很大影响vector<Point>吗？

Answer 1

如果将您定义Point为具有连续数据存储(例如struct Point { int a; int b; int c; }或使用std::array),则将s std::vector<Point>存储Point在连续的内存位置,因此您的内存布局将为:

p0.a, p0.b, p0.c, p1.a, p1.b, p1.c, ..., p(N-1).a, p(N-1).b, p(N-1).c

在另一方面,如果定义Point为vector<int>,那么vector<Point>有布局vector<vector<int>>,这是不连续的,如vector商店的指针动态分配的内存.所以你对单个 Point s 有连续性,但对整个结构没有连续性.

第一种解决方案比第二种解决方案更有效(因为现代CPU喜欢访问连续的内存位置).

Answer 2

vector将存储您的类型包含在连续内存中的任何内容.所以,是的,如果这是一个array或一个tuple,或者甚至更好,一个自定义类型,它将避免间接.

性能方面,一如既往,您必须衡量它.不要推测.至少就扫描而言.

但是,当您首先创建这些点时,肯定会有巨大的性能提升,因为您将避免每个vector存储点的不必要的内存分配.在C++中,内存分配通常非常昂贵.