Reagan Weatherly Reagan Weatherly - 3 days ago 5
C++ Question

dynamic 2d array access violation with remainders

I've got this really strange problem when trying to use this code for implementing a group quick select algorithm. I use a 2D dynamically allocated array to hold the individual elements in groups of the randomly generated unsorted array of 10 numbers. When I run the code with a group size of 2, 5, or 10 it works perfectly. But when I change the group size to a number that would leave one group smaller than the others, it breaks when I try to initialize the contents of the array to some test figures. Thanks for any advice.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <random>
#include <array>

using namespace std;

int groupSize = 0;
int groupSelect(int *, int, int, int);

int main()
{

// randomize array of size 10 with entries between 1 and 20.

random_device rd;
mt19937 eng(rd());
uniform_int_distribution<> distr(1, 20);

int max = 10;

int * Array;
Array = new int[max];

for (int i = 0; i < max; i++)
{
Array[i] = distr(eng);
}

// display array contents (unsorted)

cout << "Array contents are:\n";
for (int i = 0; i < max; i++)
{
cout << Array[i] << ", ";
}

cout << endl;

/*------------------------------------------------------------------------------*/

groupSize = 3;

int poo = groupSelect(Array, 0, 9, 5);

return 0;

/*------------------------------------------------------------------------------*/


delete[] Array;
}


int groupSelect(int* arr, int start, int end, int k)
{
bool remainder = false;
int size = 10;

if ((size % groupSize) != 0)
{
remainder = true;

}

//size = amount of groups of 5 (and remainder group)
size = size - (size % groupSize);
size = size / groupSize;

if(remainder)
size++;


cout << "Size = " << size << endl;

int** groups = new int*[size];
for (int i = 0; i < size; ++i)
{
if (remainder == true)
{
if (size - i == 1)
groups[i] = new int[((size) % (groupSize))];
}
else
groups[i] = new int[groupSize];
}


int testV = 0;
for (int i = 0; i < size; i++)
{

int temp = groupSize;
if (size - i == 1)
{
if (remainder)
temp = size % groupSize;
}
for (int j = 0; j < temp; j++)
{
groups[i][j] = testV; // codes break here
testV++;
}
}

cout << "\nGroup arrays' contents\n" << endl;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < groupSize; j++)
{
cout << "groups[" << i << "]["<<j<<"] contents = " << groups[i][j] << endl;
}
}

delete[] groups;

return 0;
}

Answer

You have a bug in this piece: if remainder is true but size - 1 != 1 you would never initialize your arrays and then you trying to access them

for (int i = 0; i < size; ++i)
{
    if (remainder == true)
    {
        if (size - i == 1)
            groups[i] = new int[((size) % (groupSize))];
    }
    else
    groups[i] = new int[groupSize];
}
Comments