c++ - std::deque 的排序是如何实现的？

Question

到目前为止，我还没有了解 std::deque 是如何在后台实现的，并且发现它类似于指向 n 字节数组的指针数组，数据实际存储在其中.所以现在我有几个与双端队列相关的问题。

描述我目前对其结构的了解的图片:

问题是:

1. 当执行 push_front 操作并且数据 block 0 中没有可用空间时，会在堆上分配一个新的数据 block ，并将指向这个新分配的内存的指针插入到'Map' 数组和普通数组一样——在 O(number_of_blocks) 时间内，是吗？

2. 如何分类这头野兽？无法想象比将所有数据复制到数组中更好的方法，对其进行排序，然后将其放回原处。但是这种方法需要 O(n) 辅助内存……但是! std::sort 为 std::vector 和 std::deque 的排序提供了类似的接口(interface)。不同数据结构的不同算法是如何实现的？使用模板特化？如果是这样，为什么 std::list 不能使用 std::sort 进行排序？或者，也许 std::sort 不关心这个容器的内部结构，只使用迭代器和方法，这在 std::vector 和 std::deque(如 operator[]、size() 等)？这个想法听起来很合理，也是对“为什么 std::sort 不能对 std::list 排序？”的答案。变得明显。

3. 如何选择数据 block 的大小？您会说“它取决于实现”，但请详细说明不同的实现和解决方案背后的动机。

这里需要澄清。谢谢。

Answer 1

要回答您的第一个问题，是的，这就是它的工作原理。可以注意到，这种方法可以扩展到多层次的层次结构。但实际的实现通常坚持两级结构，正如您的图片所示。

对于第二个问题，如果您正在谈论 std::sort，那么 std::sort 可以在不了解实际容器机制的情况下工作。如果适用于一系列随机访问迭代器。由于 std::deque 的迭代器是随机访问迭代器，因此 std::sort 可以应用于 std::deque。事实上，人们可以争辩说，随机访问这种数据结构的元素是相当有效的。它不如 vector 中的随机访问有效，但在 std::sort 的上下文中仍然很有效。

您不能将 std::sort 与 std::list 一起使用，因为 std::list 的迭代器不是随机访问迭代器。如果您愿意，您可以为 std::list 实现自己的简单(慢)版本的随机访问迭代器。您将能够将 std::sort 应用于一系列此类迭代器，从而使用 std::sort 对 std::list 进行排序.但由于显而易见的原因，它的效率会非常低。

在 std::deque 的情况下，随机访问迭代器的效率绰绰有余。

我不准备回答第三个问题。事实上，我不会惊讶地发现这些尺寸是根据大量实验根据经验选择的。而且，当然，可能没有“一刀切”的解决方案。