I think TLV (tag-length-value; length can be implied by the tag) is more commonly used in this context due to its better caching properties, and it least it provides meaningful forward iteration. See getdents/inotify/Netlink messaging.
The caption to figure 4 suggests that the AoVA pattern is not a good fit if you need to retain the full order of inserted elements:
> Compared to the SoA layout from before, we have a partial order instead of a total order. So upon insertion, we get back a tagged index that holds both the enum tag and the index in the particular variant array.
So by my reading, ordered access is considered out of scope here. (I suppose you could recover ordered iteration by storing a global index in each element, but that still wouldn't help with ordered random access, and it would likely lead to some really branchy code.)
These are essentially pointers. If you want to iterate, you store the pointers in an array in the order you want to use. It’s the same thing a program would do if it allocated memory from a heap.
Storing things based on their size is also done by garbage collectors and general-purpose allocators. They might get some efficiency from knowing all possible object sizes, though. Also, like an arena, they could gain some efficiency from having a simpler way of deallocating.
In these cases, the arrays can be just one component (could think of it as an arena) of a heap-ish structure. [1]
The cost is that your indices now need to be two dimensional (tag_idx, va_for_tag_idx). But the number of tags is known at compile time and you can optimize storage by packing so that tag_idx is the upper 4-5 bits and va_for_tag_idx uses the rest.
See: [1] https://www.cs.cornell.edu/~asampson/blog/flattening.html
In any case it wouldn't be particularly expensive; you'd have to make a new member of the destination type which is as expensive as an append. The "hole" that remains in the original vector can be filled in constant time by taking the last member of it and moving it there, then shrinking its size by 1.