Я работаю над внешним алгоритмом сортировки, который используетstd::queue и должен тщательно ограничивать использование памяти. Я заметил, что во время фазы слияния (которая использует несколькоstd::queues фиксированной длины), мое использование памяти увеличивается примерно в 2,5 раза, что я ожидал. посколькуstd::queue по умолчанию используетstd::deque в качестве основного контейнера, я провел несколько тестов наstd::deque определить его служебную память. Вот результаты, работающие на VC ++ 9, в режиме выпуска, с 64-битным процессом:

При добавлении 100 000 000charсstd::dequeиспользование памяти возрастает до 252,216K. Обратите внимание, что 100Mchars (1 байт) должен занимать 97 656 КБ, так что это служебная нагрузка 15 4560 КБ.

Я повторил тест сdoubles (8 байт) и память пилы увеличиваются до 1 976 676K, а 100Mdoubles должен занимать 781 250 КБ, а накладные расходы - 1 195 426 КБ!

Теперь я понимаю, чтоstd::deque обычно реализуется как связанный список «чанков». Если это так, то почему издержки пропорциональны размеру элемента (поскольку размер указателя должен быть фиксированным в 8 байтов)? И почему он такой огромный?

Кто-нибудь может пролить свет на то, почемуstd::deque использует столько испорченной памяти? Я думаю, что я должен поменять свойstd::queue лежащие в основе контейнерыstd::vector поскольку нет накладных расходов (учитывая, что соответствующий размерreserveред). Я думаю, что преимуществаstd::deque в значительной степени сводятся на нет тем фактом, что он имеет такие огромные накладные расходы (что приводит к пропаданию кэша, сбоям страниц и т. д.) и стоимости копированияstd::vector элементов может быть меньше, учитывая, что общее использование памяти намного ниже. Это просто плохая реализацияstd::deque от Microsoft?