想知道为什么我的内存访问比我预期的要慢一些，我终于发现 Visual C++ 实现deque确实有一个额外的内置间接层，破坏了我的内存局部性。
即它似乎持有一个数组T*，而不是一个数组T。
是否有另一种我可以与 VC++ 一起使用但没有此“功能”的实现，或者是否有某种方法（尽管我认为不太可能）能够在此实现中避免它？
我基本上是在寻找一个vector在前面也有 O(1) 推送/弹出的。
我想我可以自己实现它，但是处理allocators 等是一件痛苦的事情，而且需要一段时间才能把它做好，所以如果可能的话，我宁愿使用以前编写/测试过的东西。
无论出于何种原因，至少从 MSVC 2010 开始，该std::deque实现似乎使用了令人难以置信的小块大小（如果我没记错的话，最大为 16 个字节或 1 个单个元素！）。
根据我的经验，这可能会导致非常严重的性能问题，因为基本上数据结构中的每个“块”最终只存储一个元素，这会导致各种额外的开销（时间和内存）。
我不知道为什么会这样。据我了解，设置deque如此小的块大小正是不应该这样做的。
检查gcc stdlib实施。从内存中，他们使用更大的块大小。
编辑：为了解决其他问题：
std::deque 应该有一个额外的间接层。它通常被实现为“阻塞”数据结构——即存储一个“节点”数组，其中每个节点本身就是一个数据元素数组。它永远不像链表 - 节点数组永远不会像列表一样“遍历”，它总是直接索引（即使在每个块 1 个元素的情况下）。
当然，您可以滚动自己的数据结构，在前面保留一些额外的空间。它不会有最坏情况O(1) push/pop front/back的行为，因此它不会满足std::deque容器的要求。但如果你不关心这些...
C++ 标准不允许std::deque对前推或后推进行重新分配。这些操作始终是常数时间。不摊销，总是。
C++ 标准没有这样的容器。据我所知，Boost 没有一个（认为Boost.Container库可能；我还没有研究过）。
您抱怨的间接性实际上是由标准要求强制要求的，即引用/指针永远不会被push//无效（显然，那些指向已删除元素的引用pop front/back指针除外）。
因此，您会看到此要求与任何复杂性要求无关。
当没有可用空间时，这种间接也允许更快（但仍然是 O(size)）push front/ 。back