Почему я не могу вставить 6 миллионов элементов в набор STL?

Question

Почему я не могу вставить 6 миллионов элементов в набор STL?

Я пытаюсь вставить чуть более 6,5 миллионов элементов (целых) в набор STL. Вот код:

set<int> s;
cout << s.max_size() << endl;
for(int i = 0; i < T.MULT * T.MAXP; i++) {
s.insert(a[i]);
}

T.MULT является 10; T.MAXP является 666013,

a это массив — статически размещенный — (int a[T.MULT * T.MAXP];), который содержит различные элементы.

После примерно 4,6 миллиона элементов s.insert() бросает bad_alloc исключение. Монитор ресурсов, доступный в Windows 7, говорит, что у меня осталось 3 ГБ свободной памяти.
Что я делаю неправильно? Почему STL не может выделить память?

Изменить: вот полный код: http://ideone.com/rdrEnt

Edit2: очевидно, что вставленные элементы могут быть не различимы, но это не должно быть проблемой.

Edit3: вот упрощенная версия кода: http://ideone.com/dTp0fZ

0

c++max-size set stl

Решение

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

Возможно, вы захотите взглянуть на STXXL.

1

Хотя я не могу ответить на ваш вопрос напрямую, я думаю, что более эффективно хранить ваши данные в std :: vector, сортировать их, а затем использовать std :: binary_search для проверки существования элемента. Хранение в std :: set относительно дорого по сравнению с std :: vector. Это связано с тем, что при хранении каждого элемента возникают некоторые накладные расходы.

В качестве примера, вот как вы могли бы это сделать. Это сортирует статический массив.

std::sort(a,a+(T.MULT*T.MAXP));
bool existence=std::binary_search(a,a+(T.MULT*T.MAXP),3);

Быстро и просто.

1

Источник

Accepted Answer

Проблема на самом деле заключается в том, что вы статически наделили массив A более чем 6,5 миллионами элементов, что повреждает пространство стека вашей программы. Если вы размещаете массив в куче, он на самом деле работает. Я сделал некоторые изменения кода на основе вашего описания, он работал нормально.

int *A = new int[T.MULT * T.MAXP];
for (int i= 0; i <  T.MULT * T.MAXP; ++i)
{
A[i] = i; //for simplicity purpose, your array may have different elem. values
}

set<int> s;
for (int i = 0; i <  T.MULT * T.MAXP; ++i )
{
s.insert(A[i]);
}

cout << s.size();

set<int>::iterator iter;
int count = 0;
for (iter = s.begin(); iter != s.end(); ++ iter)
{
cout << *iter << " ";
count ++;
if (count == 100)
{
cout <<endl;
count = 0;
}
}

delete [] A;

return 0;

Он отлично работал как с вектором, так и с сетом. Он может распечатать все эти 6,6 миллиона элементов на экране.

Как указано в других сообщениях, вы также можете попробовать STXXL, если у вас есть интерес.

3