std::deque абсолютно не решает проблемы.
Еще раз о фрагментации адресного пространства. Речь идет о 32-битных системах. 32-битный указатель может адресовать до 4GB памяти. Когда оператор new или функция alloc/malloc/calloc запрашивает блок памяти размером 1GB, менеджер памяти резервирует кусок адресного пространства и возвращает указатель на начало этого куска. Предположим, что это указатель 0x00000000 и он является вполне нормальным указателем. Тогда адреса [0x00000000;0x40000000) зарезервированы под этот блок. До тех пор, пока программа не освободила его, менеджер памяти не может вернуть указатель из диапазона [0x00000000;0x40000000). Если теперь для наращивания размера массива данных до 1.5GB использовать new, то менеджер памяти может быть вернет указатель 0x40000000 и адреса [0x40000000;0xA0000000) будут зарезервированы под этот новый блок. Затем происходит переписывание данных и освобождение первого блока. Последующая попытка расширить блок при помощи оператора new до 2GB не пройдет, хотя в системе есть еще 2.5GB. Просто эти 2.5GB разбиты на два блока размером 1GB (адреса [0x00000000;0x40000000)) и 1.5GB (адреса [0xA0000000;0xFFFFFFFF]), а нужен один размером 2GB. При использовании realloc в описанном выше случае проблема фрагментации не возникнет. В рамках new/delete я решения не вижу. Аллокаторы предоставляют методы allocate/deallocate, но нет reallocate. В std::deque наращивание зарезервированного блока происходит при помощи последовательности вызовов allocate-copy-deallcoate, что работать не будет.