1

I have a std::vector of a simple datatype, and would like to convert it in O(1) to a std::vector of std::arrays of the same simple datatype.

In particular both forms represent an array of all the vertex indices of a triangle mesh. They both contain exactly the same number of indices, in exactly the same order, they just have different notions of boundaries.

So eg,

std::vector<uint32_t> X;
std::vector<std::array<uint32_t, 3>> = < ??? > (X);
orion elenzil
  • 4,484
  • 3
  • 37
  • 49
  • What do you want the value of the arrays to be? – NathanOliver Feb 24 '20 at 19:22
  • 2
    I'm pretty sure you can't do that in constant time. You'll have to copy the data; which is `O(N)` – Marshall Clow Feb 24 '20 at 19:24
  • why do you need this transformation? Do you really need both structures? Cant you use one or the other? – 463035818_is_not_an_ai Feb 24 '20 at 19:36
  • 3
    i would rather write an iterator that lets you treat a `std::vector` as if it was a `std::vector>` or vice versa, that shouldnt be too dificult to write and it avoids the explicit conversion completely – 463035818_is_not_an_ai Feb 24 '20 at 19:39
  • 1
    Something like `std::span`? – Marc Glisse Feb 24 '20 at 19:46
  • 1
    This is probably one of those infuriating situations where your information is likely contiguous and you can just wail away on `X.data()->data()` in the 80% case, but it's unavoidably undefined behavior because of strict aliasing rules and corner cases on exotic architectures. Here's a lawyer-ly QA for the same situation with a 2D `std::array`: https://stackoverflow.com/questions/7269099/may-i-treat-a-2d-array-as-a-contiguous-1d-array/7273599#7273599 – parktomatomi Feb 24 '20 at 19:55
  • There might be an argument for casting the result of `data()` from one to the other, but certainly not for casting the whole `vector`. The `size` of a vector doesn't care how you reinterpret it's elements. An `array` is still exactly 1 element as far as the `vector` is concerned. – François Andrieux Feb 24 '20 at 20:53
  • 1
    Please make the title match the actual question. The title asks the other way around – Jan15 Feb 24 '20 at 21:11

1 Answers1

2

std::vector is not the right tool for this. std::vector is owning, thus if you want to reinterpret the memory allocated by X as a "vector" of arrays of ints, you should use a non-owning container such as std::span. Even then, you would have to use reinterpret_cast, which is recommended to avoid whenever possible. Such as:

std::span<std::array<uint32_t, 3>> points (reinterpret_cast<std::array<uint32_t, 3>*>(
    X.data()), X.size()/3);

Beware though, depending on the number of values in the std::array that you cast into, you might get into issues because of padding: consecutive arrays don't have to touch each other in memory.

For all of these reasons, I would instead recommend to either iterate over each third element or provide a wrapper class around X, which encapsulates the strong semantic bond between the owned data and the view on it. That's also because the view is now ephemeral: it has to be recreated whenever X reallocates.

Jan15
  • 499
  • 3
  • 11