STL 세트에 600 만 개의 요소를 삽입 할 수없는 이유는 무엇입니까?

Question

650 만 개가 넘는 요소 (ints)를 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,600 만 개가 넘으면 s.insert()은 bad_alloc 예외를 던집니다. Windows 7에서 사용할 수있는 리소스 모니터에 3GB의 사용 가능한 메모리가 남아 있다고 표시됩니다. 내가 뭘 잘못하고 있니? 왜 STL이 메모리를 할당 할 수 없습니까?

편집 : 여기에 전체 코드입니다 : http://ideone.com/rdrEnt

Edit2가 : 분명히 삽입 된 요소는 결국 구별되지 않을 수도 있습니다,하지만 그건 문제가되지 않습니다.

EDIT3 : 여기에 코드의 단순화 된 버전입니다 : 내가 직접 귀하의 질문에 대답 할 수는 없지만 http://ideone.com/dTp0fZ

Answer 1

, 나는 표준 : : 벡터에 데이터를 저장하는 것이 더 효율적이라고 생각이 정렬이, 그런 다음 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); 

빠르고 쉽습니다.

Answer 2

STXXL을 살펴볼 수 있습니다.

Answer 3

실제로 문제는 프로그램 스택 공간을 손상시키는 650 만 개 이상의 요소로 배열 A를 정적으로 할당했다는 사실에 있습니다. 힙에 배열을 할당하면 실제로 작동합니다. 나는 당신의 설명에 기초하여 약간의 코드 변경을했는데, 그것은 잘 동작했다.

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; 

벡터와 세트 모두 완벽하게 작동했습니다. 화면에 표시된 660 만 개 요소를 모두 인쇄 할 수 있습니다.

다른 게시물이 표시되어 관심이 있으시면 STXXL을 사용해 볼 수도 있습니다.