Using custom allocator to make std::list cache friendly?

Question

During my daily work, I am always advised by senior member of the team that list is not cache friendly so I should vector. I understand that list is not continuous so that the memory allocation is scattered around the whole memory.

However, very often I do need the functionality of a list (or a map). So I am wondering if I can write my own allocator, which is a vector underneath. Every time when I push_back, my own allocator will allocate a new item from a per-allocated vector.

When I travel the list/map, the cache locality is preserved.

Does this make sense to any of you?

Answer 1

std::list and std::set (I believe you need set as alternative to list, not a map) both will use allocator for there internals. You can preallocating a block of memory and use it to create your objects and containers. If you google, you will find several. In this case your objects instead if "scattered around the whole memory" will be scattered around your block of memory. If block fit on the cache, you will get some improvement. But it will not completely solve you problem.

From description of the problem, you really need deque. Deque is implemented as a list of arrays. It is compromise between vector and a list. It is cache friendly for iteration and faster then array when you insert.

So you can choose either custom allocator or deque, depends on your collection size.