C ++中的向量存储 [英] Vector storage in C++

问题描述

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

如果将Point定义为vector<int>，我认为vector<Point>将在每个位置存储指向Point的指针.

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

如果答案是数组避免了额外的间接访问，这是否会对扫描vector<Point>时的性能(缓存利用局部性)产生重大影响?

解决方案

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

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存储，该布局与不相邻 pointers 指向动态分配的内存.因此，您可以对单个 Point s进行连续处理，而对于整个结构没有连续性.

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

I wish to store a large vector of d-dimensional points (d fixed and small: <10).

If I define a Point as vector<int>, I think a vector<Point> would store in each position a pointer to a Point.

But if define a Point as a fixed-size object like: std::tuple<int,int,...,int> or std::array<int, d>, will the program store all points in contiguous memory or will the additional level of indirection remain?

In case the answer is that arrays avoid the additional indirection, could this have a large impact on performance (cache exploit locality) while scanning the vector<Point>?

解决方案

If you define your Point as having contiguous data storage (e.g. struct Point { int a; int b; int c; } or using std::array), then std::vector<Point> will store the Points in contiguous memory locations, so your memory layout will be:

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

On the other hand, if you define Point as a vector<int>, then a vector<Point> has the layout of vector<vector<int>>, which is not contiguous, as vector stores pointers to dynamically allocated memory. So you have contiguity for single Points, but not for the whole structure.

The first solution is much more efficient than the second (as modern CPUs love accessing contiguous memory locations).

这篇关于C ++中的向量存储的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！