Meh*_*dad 6 c++ vector deque visual-c++ arraydeque
想知道为什么我的内存访问速度比我预期的慢一些,我终于想通了Visual C++实现deque确实有一个内置的额外间接层,破坏了我的内存局部性.
即它似乎持有一个数组T*,而不是一个数组T.
是否有另一个我可以使用VC++但没有这个"功能"的实现,或者是否有某种方式(虽然我认为不太可能)在这个实现中能够避免它？
我基本上都在寻找一个vector在前面也有O(1)推/弹的东西.
我想我可以自己实现它,但处理allocators等是一种痛苦,需要一段时间才能正确,所以我宁愿使用以前编写/测试的东西,如果可能的话.
Dar*_*rda 10
无论出于何种原因,至少从MSVC 2010开始,std::deque实现似乎使用了一个令人难以置信的小块大小(如果我没有弄错的话,最多16个字节或1个单个元素!).
根据我的经验,这可能会导致非常严重的性能问题,因为数据结构中的每个"块"基本上只会存储单个元素,从而导致各种额外开销(时间和内存).
我不知道为什么这样做.据我所知,设置deque如此小的块大小正是它不应该被完成的方式.
查看gcc stdlib实施情况.从内存中他们使用更大的块大小.
编辑:试图解决其他问题:
std::deque 应该有一个额外的间接层.它通常被实现为"被阻止的"数据结构 - 即存储"节点"的数组,其中每个节点本身是数据元素的数组.它不像链接列表 - 节点数组永远不会像列表那样"遍历",它总是直接索引(即使在每个块1个元素的情况下).
当然,您可以滚动自己的数据结构,在前面保留一些额外的空间.它不会有最坏的情况O(1) push/pop front/back,因此它不会满足std::deque容器的要求.但如果你不关心任何......