7 ms·
I learned to love linked lists as soon as I discovered that I can just store them in vectors to get the performance of guaranteed contiguous memory: // Linke
by xaedes 4y ago
I learned to love linked lists as soon as I discovered that I can just store them in vectors to get the performance of guaranteed contiguous memory:
// LinkedListItem[k]: item[k], prev[k], next[k]
std::vector<T> item;
std::vector<uint> prev;
std::vector<uint> next;
Similar is used in transparency rendering with per-pixel linked-lists.
- anthomtb 4y agoInteresting idea but how does C++ guarantee contiguous memory for a vector? I just don’t see how a data structure with an arbitrary, dynamic size can also reside in a contiguous range of address space.
- frankchn 4y agoSimple, you just allocate a bigger contiguous chunk of memory and copy the entire vector over when the current chunk maxes out.
- fnbr 4y agoWhen the array is resized, it’s moved to a new contiguous block of memory: everything is copied or moved over. See: https://stackoverflow.com/questions/8261037/what-happen-to-pointers-when-vectors-need-more-memory-and-realocate-memory https://stackoverflow.com/questions/8261037/what-happen-to-p...
- zabzonk 4y agothe size of a c++ object is fixed at compile-time
- nynx 4y agoThe performance of vectors comes from iterating through them and letting the cpu prefetch items before you need them. Random access in a vector doesn’t really get you that if the vector is larger than your L1/L2 caches, which linked lists would be in anyway if you used them recently enough.