I don't know whether it already exists or if it has a name, but internally I call it Virtual List.
- Reasoning: It's used in cases where you'd ideally use an array because you want contiguous memory (because you'll usually iterate through them in order), but you don't know beforehand how many elements you'll insert. But you can't use a resizeable version like std::vector, because it invalidates any pointers to the elements you've already allocated, and you need to store those pointers.
- Implementation: As a black box, it's used like a list: you index elements with an integer, and you can append to the end. But internally it uses different lists. Like a std::vector, it starts with an allocated size, and when it needs a bigger size, it allocates newer blocks that are "added" to the end, but doesn't move the already allocated elements.
- Downsides: Data is not all contiguous, at some point there are jumps between elements that should be close together. For performance when iterating, it's negligible since those cache misses happen "rarely" (depends on the block size, bigger block size means better cache performance but more potential wasted allocated memory), and most of the time you're iterating from start to end. But this means that you can't use this structure with algorithms that use "pointer + size", since internally it doesn't work like that. And since internally you can't shrink the lists and invalidate pointers, there's no way to delete elements, but in my case it's not a problem since I'd reuse indices afterwards with an added structure.
- Applications: I used it when coding games, when you have a big list of entities/components but you don't know how many beforehand. You access them by index, you might store pointers to elements, and most of the time you'll iterate through the whole list (when updating, drawing, etc.).
Although specifically, in an unrolled linked list, the blocks are connected by a chain of pointers from one to the next. You can alternatively just keep pointers to each block in a top-level array. it's not clear from your description which you're doing.
The JDK has a twist on the latter, which it calls a spined buffer, where the blocks double in size every time one is added, which makes sense if you have absolutely no idea how many elements there will be when you start.
Yeah that's pretty similar. I keep a list of pointers to blocks and they're all the same size, that way you can easily address elements via a linear index. I tried doing the doubling size thing like std::vector, but the addressing became more complex and I didn't find a need for it, but I might consider it in the future. But yeah, it seems like it's almost the same kind of structure. Thanks for the pointer!
I remember checking whether I would use std::deque, and I don't remember exactly why but I decided to implement this other system instead. I think it was because you can invalidate pointers with it if you delete somewhere in the middle, either manually or by calling an algorithm with it.
Of course you have the option to just not do that in your code, but it's nice to have a hard guarantee that this can never happen, even by accident. I could have used a deque as a backend and wrapped it in the class, though.
- Reasoning: It's used in cases where you'd ideally use an array because you want contiguous memory (because you'll usually iterate through them in order), but you don't know beforehand how many elements you'll insert. But you can't use a resizeable version like std::vector, because it invalidates any pointers to the elements you've already allocated, and you need to store those pointers.
- Implementation: As a black box, it's used like a list: you index elements with an integer, and you can append to the end. But internally it uses different lists. Like a std::vector, it starts with an allocated size, and when it needs a bigger size, it allocates newer blocks that are "added" to the end, but doesn't move the already allocated elements.
- Downsides: Data is not all contiguous, at some point there are jumps between elements that should be close together. For performance when iterating, it's negligible since those cache misses happen "rarely" (depends on the block size, bigger block size means better cache performance but more potential wasted allocated memory), and most of the time you're iterating from start to end. But this means that you can't use this structure with algorithms that use "pointer + size", since internally it doesn't work like that. And since internally you can't shrink the lists and invalidate pointers, there's no way to delete elements, but in my case it's not a problem since I'd reuse indices afterwards with an added structure.
- Applications: I used it when coding games, when you have a big list of entities/components but you don't know how many beforehand. You access them by index, you might store pointers to elements, and most of the time you'll iterate through the whole list (when updating, drawing, etc.).