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

Question

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

但是,我经常需要a list(或a map)的功能.所以我想知道我是否可以编写自己的分配器,这是一个vector底层.每当我push_back,我自己的分配器将从每个分配的分配一个新项目vector.

当我旅行list/时map,保留缓存局部性.

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

Answer 1

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

从问题的描述来看，你确实需要deque。双端队列被实现为数组列表。它是向量和列表之间的折衷。它对于迭代来说是缓存友好的，并且在插入时比数组更快。

因此，您可以选择自定义分配器或双端队列，具体取决于您的集合大小。