C++新規/削除エラー？

Question

私はC++で素数の篩を現在実装していますが、私は篩のサイズを（主関数の整数リテラルを介して）制御することができるようにコードを設計しましたが、全体を通して。私は数年後にC++を使用しませんでしたが、ヒープメモリを管理するために演算子newとdeleteを使用したことを覚えています。次のように

私の問題は、プログラムは、いくつかのふるいサイズではなく、他人のために働く、と効果が厳密に線形ではありません...一種の

です。例えば、私が10000のサイズのふるいを作っても、プログラムはうまく動作しますが、サイズを1000にすると、プログラムがクラッシュして（私の経験量では）、C mallocアサーションエラー（Google経由）。さらに、プログラムはのの削除文が入り込んだ状態で正常に動作しますが、valgrindから別の役に立たない（私にとって）メッセージを実行するとクラッシュします。その結果、私は自分自身のDXで気になることをデバッグすることはできません

知恵の言葉？

特に、より小さいプログラムがクラッシュする理由は？？理論的には、これはより少なく、ヒープエラーを引き起こす可能性が低いでしょうか？さらに、valgrindはなぜそれ自体で問題なく動くことができないのですか？私は（再び）これは新しい/削除演算子の不完全または醜い使用と関係があると思うが、私は完全には確信していない。私にとって特に困惑している部分（約valgrind）は、私がunsigned longでnew演算子を使用していることをエラーで言及しています。これは私がよく慣れていないコンパイラ関連の詳細ですが、やはり私は全く確信していません。

コード（DELETE文で、大き万ではなく、valgrindを介して動作）：上記のため

using namespace std; 

#include <iostream> 
#include <cstdlib> 
#include <map> 
#include <string> 

long count_primes(bool* sieve,int size) 
{ 
    long count = 0; 
    for (int a=0;a<size;a++) 
    { 
     if (sieve[a]) 
     { 
      count++; 
     } 
    } 
    return count; 
} 

int next_prime(bool* primes_so_far,int current_prime,int size) 
{ 
    for (int a=current_prime+1;a<size;a++) 
    { 
     if (primes_so_far[a]) return a; 
    } 
    return -2; 
} 

int prime_number_sieve(int* primes,int size) 
{ 
    if (size<4) return -2; 

    bool* sieve = new bool[size]; 

    for (int a=0;a<size;a++) 
    sieve[a] = true; 

    sieve[0] = false; 
    sieve[1] = false; 

    int a=2; 
    do 
    { 
     int b = a; 
     if (b*a < size) sieve[b*a] = false; 
     do 
     { 
      b++; 
      sieve[b*a] = false; 
     } while (b*a < size); 
     a = next_prime(sieve,a,size); 
    } while (a*a < size); 

    long prime_list_size = (long) count_primes(sieve,size); 
    int* prime_list = new int[prime_list_size]; 

    for (int b=0,c=0;b<size;b++) 
    { 
     if (sieve[b]) prime_list[c++] = b; 
    } 

    srand(time(NULL)); 
    int rand_int1 = rand(); 
    int rand_int2 = rand(); 
    long rand_num1 = (((long) rand_int1) * prime_list_size)/RAND_MAX; 
    long rand_num2 = (((long) rand_int2) * prime_list_size)/RAND_MAX; 

    primes[0] = prime_list[rand_num1]; 
    primes[1] = prime_list[rand_num2]; 

    delete[] sieve; 
    delete[] prime_list; 

    return 0; 
} 

int main() 
{ 
    int* prime = new int[2]; 

    prime_number_sieve(prime,10000); 

    cout << "\n"; 
    cout << prime[0]; 
    cout << "\n"; 
    cout << prime[1]; 
    cout << "\n"; 

    return 0; 
} 

valgrindエラー：1,000にサイズを変更するための

==23738== Invalid write of size 1 
==23738== at 0x400A4B: prime_number_sieve(int*, int) (in /home/botch/Downloads/unsorted/bre_final/a.out) 
==23738== by 0x400C31: main (in /home/botch/Downloads/unsorted/bre_final/a.out) 
==23738== Address 0x5ab83e0 is 0 bytes after a block of size 10,000 alloc'd 
==23738== at 0x4C2E80F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==23738== by 0x4009CD: prime_number_sieve(int*, int) (in /home/botch/Downloads/unsorted/bre_final/a.out) 
==23738== by 0x400C31: main (in /home/botch/Downloads/unsorted/bre_final/a.out) 
==23738== 

valgrind: m_mallocfree.c:303 (get_bszB_as_is): Assertion 'bszB_lo == bszB_hi' failed. 
valgrind: Heap block lo/hi size mismatch: lo = 4063233, hi = 0. 
This is probably caused by your program erroneously writing past the 
end of a heap block and corrupting heap metadata. If you fix any 
invalid writes reported by Memcheck, this assertion failure will 
probably go away. Please try that before reporting this as a bug. 

がエラー：

a.out: malloc.c:2392: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed. 
Aborted (core dumped) 

編集：

私はすべての（実際の）助けに非常に感謝しています！以下の答えのおかげで、プログラムはほとんどの入力に対して実行されるようになりました（でもも大きいですが）、私はまだValgrindエラーを受けています。私は本当に心配していませんその、しかし私は何が起こっているのか理解して奇妙です。私はランダムプライムの選択メカニズムを(((long) rand_int1) * prime_list_size)/RAND_MAXではなく(((long) rand_int1) % prime_list_size);に変更するために以下の提案を試みましたが、Valgrind側では目立った結果はありませんでした。私はまだ無効なヒープ書き込みがどこから来ているのか正確には分かりません。コードを修正して、それが原因で削除されているかどうかを確認し、報告します。

Answer 1

ループ

do 
    { 
     b++; 
     sieve[b*a] = false; 
    } while (b*a < size); 

b*a < size場合はチェックする前sieve[b*a]への割り当てを行います。これにより、配列の最後を通過する要素の割り当てが可能になります。これは、このループの最後の反復で未定義の動作です。

あなたは、むしろ事業者newとdelete使って手動でいじりよりも、またはstd::bitset [それは他のベクターにはないいくつかの制限があります注意する] std::vector<bool>を使用したほうが良いでしょう。コードが標準コンテナの終わりから落ちないようにする必要があることに注意してください。

Answer 2

コードに2つの問題があります。

最初の一つはここにある：

do 
    { 
     b++; 
     sieve[b*a] = false; 
    } while (b*a < size); 

チェックが後に割り当て `ふるいに起こるので、これは[B * A]偽=、限度を超えてsize書き込みを防ぐことはできません。

while (b*a < size) 
    { 
     sieve[b*a] = false; 
     b++; 
    } 

私が見る他の問題はここにある：

long rand_num1 = (((long) rand_int1) * prime_list_size)/RAND_MAX;

long rand_num2 = (((long) rand_int2) * prime_list_size)/RAND_MAX;

乗算中の用語がオーバーフローする可能性があります。私はsizeより小さいランダムなインデックスを取得したいと思いますか？

確かにこれで完全な一様な分布は得られませんが、それはうまくいくでしょう。より良い流通のためには、stdライブラリの乱数発生器の番号を調べてください。また、vectorもあります。これはあなたがやっていることのための非常に良いツールです。