[xaedes]

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.

[nynx]

The 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.

[anthomtb]

Interesting 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.

[fnbr]

When 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-p...

[frankchn]

Simple, you just allocate a bigger contiguous chunk of memory and copy the entire vector over when the current chunk maxes out.

[zabzonk]

the size of a c++ object is fixed at compile-time