Sorting large array of pairs

Question

我需要一種算法，根據每對中的第一個元素對一組數組進行排序。以下代碼適用於v_size <〜2^19，但是，在接近2^19的大小時，由於分段錯誤而崩潰。是什麼原因？大小約爲524000並不是很大。 （我正在使用gcc（Debian 4.7.2-5）4.7.2）

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <time.h> 

using namespace std; 


int main(int argc, char ** argv) 
{ 
    srand(time(NULL)); 

    int v_size=524000; 
    std::pair<double, int> AB_large[v_size]; 

    for(int i = 0; i<v_size; ++i) 
    { 
     AB_large[i].first = static_cast <double> (rand())/static_cast <double> (RAND_MAX); 
     AB_large[i].second = i; 
    } 

    std::sort(AB_large, AB_large+v_size); 
    return 0; 
} 

Answer 1

它看起來像堆棧溢出。

儘量不要使用自動變量對於這樣大的物體：

std::vector< std::pair<double, int> >AB_large(v_size); 

// ... 

std::sort(AB_large.begin(), AB_large.end()); 

Answer 2

你的陣列是一個局部變量，因此它是在棧上創建。堆棧大小通常有限制。在Linux上，通常可以通過ulimit命令查看和修改它。 （在Windows上，C++可執行文件的堆棧限制在編譯時確定，並且可以通過編譯器選項或編譯指示進行更改。）

對的一個實例是8 + 4 = 12字節大小。默認的堆棧限制通常是8兆字節。由於編譯器的設置爲alignment，可能有12個字節被填充到16個字節。所以，2個字節是相同的8兆字節。