How is sort for std::deque implemented?

Question

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.

Solution

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 talking 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.

Comments

[WhozCraig]

The math behind them not withstanding, std::deque has random access iterators, and as such any in-place sorting algorithm will be able to sort the data within using that functionality and not requiring O(N) additional storage. std::list doesn't provide random access iteration, and thus is not std::sort-able. (it is, however, std::list::sort-able). See the Type requirements section of the documentation of std::sort.

[101010]

You are missing STL's Containers <- Iterator -> Algorithms scheme. Sorting is the same as with any other container that has random access iterators.

[Mankarse]

std::sort works on any pair of random access iterators. Both std::vector and std::deque provide random access iterators, but std::list does not. There is not (necessarily) any template specialisation magic or anything, as std::sort works by swapping elements in the provided range; this does not require significant additional storage, and also does not require special knowledge of the container/range/whatever behind the iterators.

[101010]

Very good reading: stroustrup.com/Programming/20_containers.ppt

[James Kanze]

Re his second question: the important point to make is that std::sort swaps the actual data, irrespective of where it is located, so it is completely agnostic with regards to the underlying structure of the container.