3 ms·
If really needed you can have it both ways, you could roll a data structure that is a linked list of arrays. Then you have constant time growth and good caching
by voidlogic 13y ago
If really needed you can have it both ways, you could roll a data structure that is a linked list of arrays. Then you have constant time growth and good caching/prefetching.
Toy example:
struct ListSegment {
T[64] items
int nextItem = 0
ListSegment* nextSeg, prevSeg
}
- Bill_Dimm 13y agoIf you're using C++ you don't need to roll your own because the standard library provides it. It is called deque.