使用自定义分配器使std :: list缓存友好？

Question

在我的日常工作中，我总是被团队的高级成员建议，该列表不是缓存友好的，所以我应该vector。我知道list不是连续的，因此内存分配分散在整个内存中。

但是，我经常需要list（或map）的功能。所以我想知道我是否可以编写我自己的分配器，这是一个下面的vector。每当我push_back时，我自己的分配器将从每个分配的vector中分配一个新项目。

当我旅行list/map时，缓存位置被保留。

这对你们中的任何人都有意义吗？

Answer 1

std::list和std :: set（我相信你需要设置为列表的替代，而不是地图）都将使用分配器的内部。 您可以预先分配一块内存并使用它来创建对象和容器。如果你是谷歌，你会发现几个。在这种情况下，如果“散布在整个内存中”，您的对象将散布在您的内存块周围。如果块适合缓存，则会得到一些改进。但它不会完全解决你的问题。

从问题描述中，您确实需要deque。 Deque被实现为数组列表。它是向量和列表之间的折衷。在插入时，它对迭代更加友好，并且数组速度更快。

因此，您可以选择自定义分配器还是双向取决于您的集合大小。