4

If I create

std::vector<std::array<double, 2>> points;
std::vector<double> points2;

I know that points2 will be a contiguous chunk of memory holding doubles in the heap. I think that points will be a contiguous chunk of memory of double* to the stack? But will those array be contiguous in the stack? Let's say that I am storing pairs of doubles to represents some points.

points2 is in memory like this: [x0 y0 x1 y1 x2 y2 ...] What about points? What is the best way to store pair of doubles in this case? Thanks for any tip.

lucmobz
  • 453
  • 3
  • 8
  • 4
    I'd use `struct Point { double x; double y; }` and `vector points;` – Eljay Dec 28 '20 at 20:42
  • Does this answer your question? [std::vector of std::vectors contiguity](https://stackoverflow.com/questions/10898007/stdvector-of-stdvectors-contiguity) – scohe001 Dec 28 '20 at 20:43
  • 3
    `std::array` is a thin wrapper around a C-style array. So it stores the actual array, not pointers to arrays – UnholySheep Dec 28 '20 at 20:43
  • They should be, but the necessary casing is ugly IMO. If you need to paas that as a raw pointer to a 3rd party legacy interface, it should work though. – πάντα ῥεῖ Dec 28 '20 at 20:44
  • 6
    @scohe001 why would you expect std::array to behave like std::vector in this respect? You understand the difference between the two, right? – Sneftel Dec 28 '20 at 20:45
  • The arrays will be stored in a contiguous chunk of memory but there's no guarantee the elements will be contiguously aligned between arrays. – Galik Dec 28 '20 at 21:14
  • 2
    _"What is the best way to store pair of doubles in this case?"_ — This may depend on the operations you want to do with them. In some cases, it may be even better to store them as two separate vectors (x and y coordinates). You may also want to provide stronger than the default alignment to make them more SIMD/cache-friendly. – Daniel Langr Dec 28 '20 at 21:25
  • If the addres of `std::array` was equal to `std::array::data` pointer then vector of arrays would be contiguous. But I didn’t see this proposition in the standard. – alex_noname Dec 28 '20 at 21:37
  • Why do you ask? Are you planning to reinterpret_cast it as an array of double? That is not allowed even if it was continuous (strict aliasing). If you just want to ensure no space wasted due to padding, then yes most likely it will be continuous. – rustyx Dec 28 '20 at 21:38
  • @rustyx It may be very important for SIMD efficiency of processing the elements. It's not just about space efficiency. – Daniel Langr Dec 28 '20 at 21:40
  • @DanielLangr SIMD can stride across values, too. Chances are even in the presence of padding the access could still be vectorized. But anyway it would be prudent to use a structure that guarantees continuity. So `vector` would be a better idea. – rustyx Dec 28 '20 at 21:53

2 Answers2

2

Is a vector of arrays contiguous?

No, it is not. std::array may contain padding or even additional members at the end. More details, e.g., here:

But I believe this is very unlikely to happen and you can simply check such situations by comparing 2 * sizeof(double) with sizeof(std::array<double, 2>).

Daniel Langr
  • 22,196
  • 3
  • 50
  • 93
  • But in the [Working draft](http://open-std.org/JTC1/SC22/WG21/docs/papers/2020/n4878.pdf) it says in 22.3.7 Class template array [array]: `The header defines a class template for storing fixed-size sequences of objects. An array is a contiguous container` and in 22.3.11 Class template vector [vector]: `A vector meets all of the requirements of a container and... and, for an element type other than bool, of a contiguous container`. I am not sure if OP was asking if the data in two consecutive arrays is contiguous or just the `std::array` object it self... – Tony Tannous Dec 28 '20 at 21:19
  • 2
    @TonyTannous Sure, a single `std::array` is a contiguous container. But this does not imply that if you put two arrays next to each other (to a vector's buffer), then there won't be any "gap" between their elements. – Daniel Langr Dec 28 '20 at 21:20
  • That's fine then, I guess OP was asking about elements in the std array and not the object itself, in such case I agree with you. – Tony Tannous Dec 28 '20 at 21:21
  • Even if you check that the sizes are the same, there is no guarantee they will continue to be the same on a different compiler, or a different architecture with the same compiler or even with the same compiler using different flags to compile. – Galik Dec 28 '20 at 21:33
  • @galik Yes, but this is generally a matter of portability and also ABI. For instance, can you work with a single `std::array` object in two translation units compiled with different compilers or different flags and then linked together? Once a memory representation of a type may have different sizes (or memory layout) under different conditions, you basically cannot use it in libraries etc. – Daniel Langr Dec 28 '20 at 21:45
  • I was asking if it's better to go with just a vector or if it makes sense to do a vector>. I am assuming it's okay to have the points layed out as pairs of double instead of having all xs and then all ys. My doubt is if it's more efficient to have everything in the heap or if putting the data in the stack and keeping the pointers in the vector is better (I am assuming a vector is stored as a bunch of pointers to the stack, is this correct?). By reading all the answers I feel like the first solution is better. – lucmobz Dec 28 '20 at 21:50
  • @lucmobz No, it's not correct. In a vector of arrays, all the array elements are stored in a single memory part (there is a single buffer allocated on the heap at any moment). Just, it's not guaranteed that there are no gaps between them (very likely there are not). If you want to be 100% sure, use either a single vector, or two separate vectors for _x_ and _y_ coordinates. – Daniel Langr Dec 28 '20 at 21:58
  • @lucmobz This question is highly relevant: https://stackoverflow.com/q/54197195/580083. – Daniel Langr Dec 28 '20 at 22:03
  • Thank you. I somehow always assumed that an array is a pointer to the stack and a vector of arrays is therefore a buffer (in the heap) of pointers to the stack. I will investigate more and accept the answer. – lucmobz Dec 28 '20 at 22:05
  • @lucmobz That's a common misunderstanding. Array is not a pointer. It just sometimes behaves as a pointer. Moreover, this holds only for C-arrays. `std::array` is a structure (`struct`): http://eel.is/c++draft/array.overview#5. – Daniel Langr Dec 28 '20 at 22:07
-1

Assuming that sizeof(std::array<double, 2>) is an integer multiple of alignof(std::array<double, 2>), then they should be stored contiguously with no padding.

And it's pretty likely that this will always be the case.

Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
  • Isn’t `sizeof(T)` an integer multiple of `alignof(T)` for *any* type? – Sneftel Dec 28 '20 at 21:04
  • There are no guarantees here though that one array will contiguously run into the next in memory. – Galik Dec 28 '20 at 21:16
  • @Sneftel: Yes: https://stackoverflow.com/questions/54384522/will-sizeof-always-be-a-multiple-of-alignof – mrks Dec 28 '20 at 21:21