Ошибка C++ New/Delete?

Question

Я в настоящее время реализую сито с простыми числами в C++, и я разработал код, чтобы я мог контролировать размер сита (через целостный литерал в основной функции), но я получаю некоторые нечетные ошибки. на протяжении. Я не использовал C++ через несколько лет, но я помню, используя операторы new и delete для управления памятью кучи.

Моя проблема вроде как следует ...

Программа работает для некоторых размеров сит, но не другие, и эффект не является строго линейными. Например, если я делаю сито размером 10 000, программа работает нормально, но если я делаю его размером 1000, программа вылетает с довольно загадочным (по моему опыту) сообщением, которое всегда приводит меня к страницам о C malloc ошибки утверждения (через google). Кроме того, программа отлично работает для 10 000 с инструкциями удаления, набитыми, НО будет сбой, если я забегу через valgrind с другим бесполезным (мне) сообщением. В результате я даже не могу отладить эту проклятую вещь на своем собственном DX

Любые слова мудрости?

В частности, почему программа сбой с меньше? Теоретически это будет меньше, которые могут вызвать ошибки кучи, не так ли? Кроме того, почему valgrind не сможет запустить программу, пока она может работать сама по себе? Я подозреваю, что (опять же) это связано с неправильным или уродливым использованием новых/удаленных операторов, но я не совсем уверен. Часть (около valgrind), которая особенно беспокоит меня, заключается в том, что она упоминает в ошибке, что я использую оператор new на unsigned long, который, насколько я могу судить, - это не то, что я делаю (по крайней мере, не конкретно). Я предполагаю, что это некоторые детали, связанные с компилятором, с которыми я не знаком, но опять же я не совсем уверен.

кода (с ВЕЬЕТЕ, работает с размером 10000, но не через 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 погрешность выше:

==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. 

Ошибка изменения размера до 1000:

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) 

EDIT:

Я очень благодарен за всю (актуальную) помощь! Благодаря ответам ниже, программа будет работать для большинства входов (не тоже большой, конечно), но я все еще получаю ошибку Valgrind. Я действительно не возражаю , что много, но мне любопытно понять, что происходит. Я попробовал следующее предложение, чтобы изменить механизм выбора случайного штриха на (((long) rand_int1) % prime_list_size);, а не на (((long) rand_int1) * prime_list_size)/RAND_MAX, но у меня не было никаких заметных результатов на стороне Valgrind. Я до сих пор не могу точно указать, откуда происходит недопустимая запись кучи. Я буду изменять код, чтобы узнать, являются ли это мои удаления, которые вызывают и будут отчитываться.

Answer 1

Петля

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

делает присвоение sieve[b*a] перед проверкой, если b*a < size.Это позволяет назначить элемент за конец массива. Это неопределенное поведение на последней итерации этого цикла.

Вы бы лучше использовать std::vector<bool> [отметив, что она имеет некоторые ограничения, что и другие векторы не имеют] или std::bitset, а не возиться вручную с операторами new и delete. Имейте в виду, что по-прежнему необходимо обеспечить, чтобы ваш код не упал с конца стандартных контейнеров.

Answer 2

Я мог видеть две проблемы в вашем коде.

Первый здесь:

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

Это не может предотвратить запись за пределы size, потому что проверка происходит после о назначении `решето [б * а] = FALSE;

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? Вы можете просто сделать это так:

long rand_num1 = (((long) rand_int1) % prime_list_size); 
long rand_num2 = (((long) rand_int2) % prime_list_size); 

Удостоверьтесь, что это не даст идеального равномерного распределения, но оно будет работать. Для лучшего распространения взгляните на число случайных генераторов библиотеки std и его vector, что является очень хорошим инструментом для того, что вы делаете.