Не так далеко, я узнал, какstd::deque реализован под капотом и обнаружил, что это что-то вроде массива указателей на n-байтовые массивы, где данные фактически хранятся. Итак, теперь у меня есть пара вопросов, связанных с Deques.

Картина, которая описывает мои текущие знания о его структуре:

Вопросы:

Когдаpush_front выполняется операция, и в блоке данных 0 нет свободного места, новый блок данных выделяется в куче, и указатель на эту вновь выделенную память вставляется в массив «Map», как в обычном массиве - за время O (number_of_blocks) , да?

Как отсортировать этого зверя? Не могу представить ничего лучше, чем скопировать все данные в массив, отсортировать их и затем вернуть обратно. Но этот подход требует O (n) вспомогательной памяти ... Но!std::sort обеспечивает похожий интерфейс для сортировки какstd::vector а такжеstd::deque, Как реализуются разные алгоритмы для разных структур данных? Используете шаблонную специализацию? Если так, то почемуstd::list не может быть отсортировано с помощьюstd::sort? Или, может быть,std::sort не заботится о внутренней структуре этих контейнеров и просто использует итераторы и методы, которые похожи в обоихstd::vector а такжеstd::deque (лайкoperator[], size(), так далее)? Эта идея звучит разумно и ответ на вопрос «почему не можетstd::sort Сортироватьstd::list? »становится очевидным.

Как выбираются размеры блоков данных? Вы скажете«Это зависит от реализации», но, пожалуйста, расскажите подробнее о различных реализациях и мотивации решений.

Нужны уточнения здесь. Благодарю.