如何实现std :: deque的排序？

Question

到目前为止,我已经了解了如何std::deque在引擎盖下实现,并发现它类似于指向n字节数组的指针数组,其中数据实际存储在其中.所以现在我有几个与deques相关的问题.

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

问题是:

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

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

3. 如何选择数据块的大小？你会说"它依赖于实现",但请详细说明解决方案背后的不同实现和动机.

需要澄清这里.谢谢.

Answer 1

要回答你的第一个问题,是的,这几乎就是它的工作原理.可以注意到,这种方法可以扩展到多级分层结构.但实际的实现通常坚持两级结构,完全如图所示.

对于你的第二个问题,如果你正在接受std::sort,那么std::sort在不了解实际容器的机制的情况下工作.如果适用于一系列随机访问迭代器.由于std::deque迭代器是随机访问迭代器,std::sort因此可以应用于std::deque.人们实际上可以争辩说,随机访问这种数据结构的元素是相当有效的.它不像向量中的随机访问那样有效,但它在上下文中有意义仍然非常有效std::sort.

你不能使用std::sortwith std::list因为std::list迭代器不是随机访问迭代器.如果您愿意,可以实现自己的随机访问迭代器的简单(慢)版本std::list.您将能够应用std::sort到一系列这样的迭代,从而进行排序的std::list用std::sort.但由于显而易见的原因,这将是非常低效的.

在std::deque随机访问的情况下,迭代器的效率非常高.

我不准备回答第三个问题.事实上,根据一系列实验,我发现这些尺寸是根据经验选择的,我不会感到惊讶.当然,可能没有"一刀切"的解决方案.