C++數組分配分割錯誤11新手

我正在學習Robert Sedgewick在C++算法中的C++。現在我正在使用Eratosthenes的Sieve，並且在用戶指定的最大素數上限上工作。當我使用max 46349運行代碼時，它運行並打印出所有素數達46349，但是當我使用max 46350運行代碼時，會發生分段錯誤。有人可以幫助解釋爲什麼嗎？C++數組分配分割錯誤11新手

./sieve.exe 46349 
2 3 5 7 11 13 17 19 23 29 31 ... 

./sieve.exe 46350 
Segmentation fault: 11

代碼：

#include<iostream> 

using namespace std; 

static const int N = 1000; 

int main(int argc, char *argv[]) { 
    int i, M; 

    //parse argument as integer 
    if(argv[1]) { 
     M = atoi(argv[1]); 
    } 

    if(not M) { 
     M = N; 
    } 

    //allocate memory to the array 
    int *a = new int[M]; 

    //are we out of memory? 
    if(a == 0) { 
     cout << "Out of memory" << endl; 
     return 0; 
    } 

    // set every number to be prime 
    for(i = 2; i < M; i++) { 
     a[i] = 1; 
    } 

    for(i = 2; i < M; i++) { 
     //if i is prime 
     if(a[i]) { 
      //mark its multiples as non-prime 
      for(int j = i; j * i < M; j++) { 
       a[i * j] = 0; 
      } 
     } 
    } 

    for(i = 2; i < M; i++) { 
     if(a[i]) { 
      cout << " " << i; 
     }  
    } 
    cout << endl; 

    return 0; 
}

來源

2013-03-02 David Williams

分段錯誤通常是由超出分配內存邊界的寫入引起的。您應該使用調試器（或添加打印語句）來跟蹤程序的進度，以便找出發生這種情況的時間點。 – 2013-03-02 17:00:04

請注意，如果分配失敗，'new'不會返回'NULL'（除非指定'nothrow'，否則它不在此處）。它會拋出一個'std :: bad_alloc'異常。 – Cornstalks 2013-03-02 17:00:41

我看，問題聲明中號爲int。當我宣佈我，M和J只要，這似乎工作正常。

來源

2013-03-02 17:01:06

我不會指望'長'這樣做。 'long'至少爲32位，任何32位的實現都會導致溢出。不過，long long至少是64，而且它正式成爲C++ 11的一部分。如果處理器是32位處理器並且處理64位數字的話，那麼速度可能會有問題，但我甚至不知道，直到我有多少時間纔會有多少差異。 – chris 2013-03-02 17:03:15

正如'NPE'所示，如果'int'是32位，那麼'i * j'將溢出並且可能發生不好的事情（如崩潰）。如果'long'有更多的位，那麼使它成爲'long'將會工作，對於你和你的編譯器來說，'long'可能是64位，所以'i * j'不再溢出。 – Cornstalks 2013-03-02 17:05:03

在任何合理的現代C++中，如果分配失敗，您將不會從new返回空指針，除非您使用非拋出new。您的代碼部分無法按預期工作 - 您必須將std::bad_alloc可能從呼叫中發出，而不是new。

你也想聲明你的數組索引類型爲size_t。

來源

2013-03-02 17:01:07

你會推薦任何關於這方面的學習資料嗎？我對這種語言完全陌生，而且還沒有接觸到內存管理。 – 2013-03-02 17:07:43

@DavidWilliams，[好書]（http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list）總是一個好的開始。請記住，現代C++不像內存管理那麼重要，就像RAII一樣，你不需要管理它。 – chris 2013-03-02 17:10:46

你有整數溢出這裏：

 for(int j = i; j * i < M; j++) { 
      a[i * j] = 0; 
     }

46349 * 46349不適合在int。

在我的機器，改變j到long類型能夠運行程序較大輸入：

for(long j = i; j * i < M; j++) {

取決於你的編譯器與架構，你可能需要使用long long得到同樣的影響。

來源

2013-03-02 17:01:41 NPE

當您使用調試器運行您的程序，你會看到它失敗在

a[i * j] = 0;

i * j溢出併產生負。這個負數小於M，這就是爲什麼它再次進入循環，然後失敗訪問a[-2146737495]。

來源

2013-03-02 17:05:20

迂腐，我相信你*知道這一點，但它技術上不一定是-2146737495。 – chris 2013-03-02 17:09:41

@chris這只是從gdb剪切和粘貼。 – 2013-03-02 17:16:13

C++數組分配分割錯誤11新手

回答

相關問題