Using a custom allocator to create a friendly std :: list cache?

Question

During my daily work, the senior member of the team always advises me that the list is not cached, so I have to vector . I understand that list not continuous, so the memory allocation is scattered throughout the memory.

However, very often I need the functionality of list (or map ). Therefore, I am wondering if I can write my own distributor, which is vector under it. Every time I push_back , my own dispenser allocates a new element from the selected vector .

When I move list / map , cache location is saved.

Does that make sense for any of you?

Answer 1

std :: list and std :: set (I believe that you need to install an alternative to the list, not the map), both will use a distributor for the internal ones there. You can pre-allocate a block of memory and use it to create your objects and containers. If you are Google, you will find several. In this case, your objects instead, if “scattered throughout memory” will be scattered around your memory block. If the block fits in the cache, you will get some improvement. But this will not completely solve your problem.

From the problem description, you really need deque . Deque is implemented as a list of arrays. This is a tradeoff between vector and list. This is a cache interface for iteration and faster than an array on insert.

Thus, you can choose either a custom allocator or deque, depending on the size of your collection.