如何排序std :: deque实现？ [英] How is sort for std::deque implemented?

问题描述

到目前为止，我已经学会了 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 sort std :: list ？




3. 如何选择数据块的大小？

$

b $ b

需要说明。
谢谢。

解决方案

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

对于你的第二个问题，如果你正在考虑 std :: sort ，然后 std :: sort 在没有任何关于实际容器的机制的知识的情况下工作。如果在一系列随机访问迭代器上工作。由于 std :: deque 的迭代器是随机访问迭代器，因此 std :: sort 可以应用于 std :: deque 。并且实际上可以认为对这种数据结构的元素的随机访问是相当有效的。它不像在向量中的随机访问一样有效，但是在 std :: sort 的上下文中仍然有效。

您不能使用 std :: list 使用 std :: sort $ c> std :: list 的迭代器不是随机访问迭代器。如果你愿意，你可以为 std :: list 实现你自己的简单（慢）版本的随机访问迭代器。您将能够将 std :: sort 应用于一系列此类迭代器，从而对 std :: list 与 std :: sort 。但是由于显而易见的原因，这将是非常低效的。

在 std :: deque 的情况下，随机存取迭代器效率非常高。

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

Not so far I've learned how std::deque is implemented under the hood, and discovered that it's something like an array of pointers to n-byte arrays, where the data is actually stored. So now I have a couple of questions related to deques.

A picture that describes my current knowledge about it's structure:

The questions are:

1. When a push_front operation is being performed and there is no free space in Data Block 0, a new Data Block is allocated on heap and a pointer to this freshly allocated memory is inserted into 'Map' array like in ordinary array -- in O(number_of_blocks) time, yes?

2. How to sort this beast? Can't imagine anything better then copy all the data into array, sort it, and then put it back. But this approach requires O(n) auxiliary memory... But! std::sort provides similar interface for sorting both std::vector and std::deque. How are different algoritms for different data structures implemented? Using a template specialization? If so, why std::list can't be sorted using std::sort? Or, maybe, std::sort doesn't care about internal structure of this containers and just uses iterators and methods, that are similar in both std::vector and std::deque (like operator[], size(), etc)? This idea sounds reasonable and an answer to "why can't std::sort sort std::list?" becomes evident.

3. How are the sizes of data blocks being chosen? You'll say "It's implementation dependent", but please tell more about different implementations and motivation behind solutions.

Need clarifications here. Thanks.

解决方案

To answer to your first question, yes, that's pretty much how it works. One can note that this approach can be extended into a multi-level hierarchical structure. But practical implementations usually stick to two-level structure, exactly as shown in your picture.

For your second question, if you are taking about std::sort, then std::sort works without any knowledge about the mechanics of the actual container. If works on a range of random-access iterators. Since std::deque's iterators are random-access iterators, std::sort can be applied to std::deque. And one can actually argue that random access to elements of such data structure is rather efficient. It is not as efficient as random access in a vector, but it is still pretty efficient to make sense in the context of std::sort.

You cannot use std::sort with std::list because std::list's iterators are not random access iterators. If you wish, you can implement your own trivial (slow) version of random-access iterator for std::list. You will be able to apply std::sort to a range of such iterators and thus sort an std::list with std::sort. But for obvious reasons it will be prohibitively inefficient.

In case of std::deque random access iterators are more than adequately efficient.

I'm not prepared to answer the third question. In fact I wouldn't be surprised to find out that these sizes are chosen empirically, based on a bunch of experiments. And, of course, there's probably no "one size fits all" solution.

这篇关于如何排序std :: deque实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！