Как реализована сортировка для 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::sort с std::list так как std::listИтераторы не являются итераторами с произвольным доступом. Если вы хотите, вы можете реализовать свою собственную тривиальную (медленную) версию итератора с произвольным доступом для std::list, Вы сможете подать заявку std::sort диапазон таких итераторов и, таким образом, сортировать std::list с std::sort, Но по понятным причинам это будет непомерно неэффективно.

В случае std::deque итераторы произвольного доступа более чем достаточно эффективны.

Я не готов ответить на третий вопрос. На самом деле я не удивлюсь, если узнаю, что эти размеры выбираются опытным путем, основываясь на ряде экспериментов. И, конечно же, вероятно, нет единого решения для всех.