C ++ Заполнение deque плохое размещение

Question

C ++ Заполнение deque плохое размещение

Я пытаюсь сделать огромную коллекцию случайных чисел, чтобы сделать анализ алгоритма. Потом я столкнулся с этой проблемой, которую не могу объяснить. Рассмотрим следующий код:

#include <exception>
#include <iostream>
#include <deque>

typedef unsigned long long mytype;

const mytype SIZE = 150000000;

int main()
{
std::deque<mytype> rand;

try
{
for (mytype i = 0; i< SIZE; i++)
{
rand.push_back(1); //Just push a dummy number into the deque
}

}
catch (std::exception& e)
{
{
std::cout << e.what() << std::endl;
}
}

return 0;
}

Это приведет к неправильному распределению.
Дело в том, что если я использую vector и reserve (), это будет работать. Поправьте меня, если я не правильно понимаю, разве не требуется структура данных с большей емкостью, поскольку она не выделяет память непрерывно, как вектор?

Я запускаю это на Win8 x64, Visual Studio 2012, Intel i7 с 8G RAM. Спасибо за то, что поделились своими мыслями

1

bad-alloc c++deque

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Проблема вызвана фрагментацией памяти.

Если использовать vector.reserve напрямую, в начале вы получите большой блок памяти. При запуске приложения фрагментация памяти мала, поэтому вероятность выделения огромной памяти в это время высока.

Когда вы используете deque.push_back в цикле, deque сначала зарезервирует небольшой блок памяти (например, размер составляет A байтов), когда цикл выполняется, deque достигает своего предела памяти, затем он выделяет 2 * A байты, затем скопируйте данные в новую память; затем 4 * A байтов, затем 8 * A байтов …. Я давно читал код deque, так что, возможно, что-то не так с деталями, идея здесь в том, что этот цикл вызовет много выделения / освобождения памяти , что приведет к высокой фрагментации памяти, если фрагментация памяти высока, вероятность выделения огромной памяти низка.

Подробнее о фрагментации памяти см. этот.

2