c++ - 关于 deque 的额外间接寻址

Question

想知道为什么我的内存访问比我预期的要慢一些，我终于发现 deque 的 Visual C++ 实现确实有一个 extra 内置的间接层，破坏了我的内存位置。

即它似乎包含一个 T* 数组，而不是一个 T 数组。

是否有另一个我可以与 VC++ 一起使用的没有此“功能”的实现，或者是否有某种方法(尽管我认为这不太可能)能够在此实现中避免它？

我基本上是在寻找一个 vector，它在前面也有 O(1) 推/弹出。
我想我可以自己实现它，但是处理 allocator 之类的东西很痛苦，需要一段时间才能正确完成，所以如果可能的话，我宁愿使用以前编写/测试过的东西。

Answer 1

无论出于何种原因，至少从 MSVC 2010 开始，std::deque 实现似乎使用了令人难以置信的小块大小(如果我'，则最大为 16 个字节或 1 个单个元素我没记错!)。

根据我的经验，这会导致非常严重的性能问题，因为基本上数据结构中的每个“ block ”最终只会存储一个元素，这会导致各种额外的开销(时间和内存)。

不知道为什么会这样。据我所知，设置一个 block 大小如此小的 deque 正是不应该做的。

检查 gcc stdlib 实现。从内存来看，他们使用了更大的 block 大小。

编辑:试图解决其他问题:

• std::deque 应该 有一个额外的间接层。它通常被实现为一个“ block 状”数据结构——即存储一个“节点”数组，其中每个节点本身就是一个数据元素数组。它永远不像链表 - 节点数组永远不会像列表那样“遍历”，它总是直接索引(即使在每个 block 1 个元素的情况下)。

• 当然，您可以滚动自己的数据结构，在前面保留一些额外的空间。它不会有最坏的情况 O(1) push/pop front/back 行为，因此它不会满足 std::deque 容器的要求。但如果你不关心这些……