Containers

[rikki cattermole]

On 02/09/2021 8:55 AM, Per Nordlöw wrote:
> On Wednesday, 1 September 2021 at 12:09:19 UTC, rikki cattermole wrote:
>> Unrolled linked list, a linked list with X number of entries per node.
> 
> Yes, where each node typically is sized to fit in a single cache-line. 
> Suitable for small element types.
> 
> I don't know why an UnrolledList is preferred over a traditional vector 
> type bundled with an allocator that does the same grouping of 
> allocations, though.

All depends on how the vector is implemented. If its just an array that 
is resized as required with extra capacity, then obviously there is 
memory fragmentation issues that can result in allocation failing.

But I think each have different memory patterns associated with it, so 
it may not be clear cut.

For example I'm working on a color palette data structure using an 
unrolled linked list as the basis.

Insertions, removals are both quite common here, but so is only 
appending. And of course quite importantly you want fairly fast skipping 
of entries (hence unrolled rather than a straight linked list) to find 
the one you want.