Joseph Stack Joseph Stack - 1 month ago 14
C++ Question

Vector storage in C++

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

Answer

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).