为什么C++标准库没有具有连续内存的deque版本？

Question

根据我的理解,deque会根据您的需要分配新的常量内存块,而不保证它们是连续的.这确保从任一侧删除不会使当前指向双端队列的任何迭代器无效.

这种内存布局在某些情况下很方便,但它通常比连续存储内存慢.

更快的连续内存的首选容器是矢量,但它不允许您从前面推或弹.

我不明白为什么会这样.

我确信可以实现一个使用连续内存的双端队列,而且看起来它会严格优于向量.它的内存布局同样快,它还可以从前面有效地推/弹.

不仅如此,我觉得从设计角度来看也更有意义.连续的双端队列将是它速度的首选,并且当它的内存布局更好地适应手头的问题时,将使用非连续的双端队列.

如果我遗失某些东西或者看上去非常短视,请告诉我.为什么标准库中没有连续的双端队列？

Answer 1

标准库中的容器并不意味着涵盖所有可能的用例,它们只是一些有用的数据结构(主要是)非重叠属性(如果将四个关联容器统计为一个单独的族,并且四个无序)容器作为另一个家庭).

对于连续内存,请使用向量.要进行高效拼接,请使用列表.为了在任何一端进行有效的插入和移除而不需要大量的重新分配和改组,请使用deque等.

如果你想要一个不同的数据结构然后编写它,这就是STL设计的要点:遵循相同原则的任何其他容器都将与STL风格的算法完美配合.

你提出的结构比矢量有更多的开销,需要四个指针而不是三个.它可能需要前端容量和后容量成员函数,因此您可以知道在任一端插入是否会重新分配和/或使迭代器无效.当它在一端用完空间时,你必须决定是否重新分配或者只是将一切都移动到另一端的自由空间中.根据使用模式的不同,做出错误的决定可能会很昂贵(例如,重新分配并在两端都有更大的增长空间可能会更好,但这可能会导致一端浪费大量空间,如果你洗牌而不是重新分配你可能只是推迟不可避免的事情,并且无论如何都必须重新分配).

但这些都不是无法解决的问题,所以原则上没有什么能阻止你写这样的容器.这并不意味着它必然需要在标准库中.

标准库也没有像Boost.Container的flat_map和stable_vector这样的容器,但您可以在第三方库中找到它们.同样,这种可扩展性是STL设计的重点.

Answer 2

它已经存在。您可以在向量的前面插入。

是的，当然，它使引用和迭代器无效，并要求复制（或移动）向量的内容，但如果您想要连续内存，这是您必须做出的权衡。

双端队列为您提供的是保证在任一端插入不会使对现有元素的引用无效。这是唯一可能的，因为它不使用连续内存。