CODEWITHSUNDEEP
c++cpointersstructqsort
user3813057
user3813057

Reputation: 911

Qsort on struct containing pointer

I'd like to write a program sorting rows of a matrix lexicographically by the qsort function. Since the compare function needs to know the size of each row, and there are no way to pass a third parameter, I make each row a ROW struct containing the row size. Then the problem is reduced to sort the structs in lexicographic order.

I write the default constructor, the copying cnostructor and the destructor. And I overload the assignment operator.

When I run the program on VS2010, it occasionally report the error below. When I run it in Linux with g++, it may modify some elements to unexpected status or run in core dumped.

Could anyone tell me where should I modify the code? Thanks

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

using namespace std;

struct ROW
{
    int *ptr;
    int L;
    ROW();
    ROW(ROW &obj);
    ~ROW();
    ROW& operator = (const ROW& obj);
};

ROW::ROW()
{
    ptr = 0;
    L = 0;
}

ROW::ROW(ROW &obj)
{
    L = obj.L;
    ptr = new int [L];
    memcpy(ptr,obj.ptr,L*sizeof(int));
}

ROW::~ROW()
{
    if (ptr)
        delete [] ptr;
    ptr = NULL;
}

ROW& ROW::operator = (const ROW& obj)
{
    if (this != &obj)
    {
        //this->ptr = obj.ptr;
        if (ptr)
            delete [] ptr;
        ptr = new int [L];
        memcpy(ptr,obj.ptr,L*sizeof(int));
    }
    return *this;
}

int MyCMP(const void *a, const void *b)
{
    ROW *L = (ROW*)a;
    ROW *R = (ROW*)b;
    for (int i=0; i < (L->L); i++)
        if ((L->ptr[i]) < (R->ptr[i]))
            return -1;
        else if ((L->ptr[i]) > (R->ptr[i]))
            return 1;
    return 0;
}

int main()
{
    srand(time(0));
    int R_size = 23;
    int R = 7;
    ROW* A = new ROW[R];
    //scanf("%d %d",&R, &R_size);
    R = rand()%20+1;
    R_size = rand()%30+1;
    printf("Row: %d, Column: %d.\n",R,R_size);

    for (int i=0; i<R; i++)
    {
        A[i].ptr = new int [R_size];
        A[i].L = R_size;
        for (int j=0; j<R_size; j++)
        {
            A[i].ptr[j] = rand()%100;
            printf("%d ",A[i].ptr[j]);
        }
        printf("\n");
    }
    printf("After sorting\n");
    qsort(A,R,sizeof(ROW),MyCMP);

    for (int i=0; i<R; i++)
    {
        for (int j=0; j<R_size; j++)
            printf("%d ",A[i].ptr[j]);
        printf("\n");
    }

    /*
    for (int i=0; i<R; i++)
    {
        if (A[i].ptr)
        {
            delete [] (A[i].ptr);
            A[i].ptr = NULL;
        }
    }
    delete [] A; 
    */
    return 0;
}

WINDOWS error
    TestArraySort.exe has stopped working 
        windows can check online for a solution to the problem.

      Problem Event Name:   APPCRASH
      Application Name: TestArraySort.exe
      Application Version:  0.0.0.0
      Application Timestamp:    53dd642c
      Fault Module Name:    TestArraySort.exe
      Fault Module Version: 0.0.0.0
      Fault Module Timestamp:   53dd642c
      Exception Code:   c0000005
      Exception Offset: 00011727
      OS Version:   6.1.7601.2.1.0.256.4
      Locale ID:    1033
      Additional Information 1: 0a9e
      Additional Information 2: 0a9e372d3b4ad19135b953a78882e789
      Additional Information 3: 0a9e
      Additional Information 4: 0a9e372d3b4ad19135b953a78882e789

Upvotes: 0

Views: 235

Answers (1)

WhozCraig
WhozCraig

Reputation: 66204

You're completely changing the row-dimension of your array after allocation.

int R_size = 23;
int R = 7;            // SET HERE
ROW* A = new ROW[R];  // USED AS ALLOC SIZE HERE

R = rand()%20+1;      // CHANGED HERE
R_size = rand()%30+1;

unless R ends up being less than or equal to 7 (odds are 7/20) you'll invoke undefined behavior. If it does end up being <= 7, you'll report partially sorted data. In a word, yuck.

Doing This With Modern C++

There are multiple ways you can do this with modern C++. This is one of them, which takes a step further by sorting the rows before insertion into the matrix, thereby allowing us to exploit the standard library comparator for containers of sortable entities. This is only one of several ways to do this, it is not, nor does not claim-to-be, some silver bullet. Rather it was chosen to demonstrate just some of the vast features the modern C++ language and standard library have to offer. Among them:

  • <random> for random management. Truly the cat's whiskers.
  • std::vector<int> for dynamic row storage.
  • std::vector<> for dynamic rows storage.
  • std::sort for sorting both individual rows and row-vs-row.
  • ranged-for-loop usage (see if you can find it)

The standard library is amazing for accomplishing many, many tasks, and this is but a gnat on the arse of a fly on the bum of an elephant in demonstrating some of its capabilities. As you learn C++, spend time every day learning more of that library. You won't regret it.

So, some code:

#include <iostream>
#include <vector>
#include <random>

int main()
{
    std::mt19937 prng{ std::random_device{}() };
    std::size_t R = std::uniform_int_distribution<std::size_t>(1,20)(prng);
    std::size_t R_size = std::uniform_int_distribution<std::size_t>(1,30)(prng);
    std::uniform_int_distribution<> dist(1,100);
    std::cout << "Row: " << R << ", Column: " << R_size << '\n';

    std::vector< std::vector<int> > rows;
    rows.reserve(R);
    for (size_t i=0; i<R; ++i)
    {
        std::vector<int> row;
        row.reserve(R_size);
        for (size_t j=0;j<R_size;++j)
        {
            row.emplace_back(dist(prng));
            std::cout << row.back() << ' ';
        }
        std::cout << '\n';
        std::sort(row.begin(), row.end());
        rows.emplace_back(std::move(row));
    }

    std::sort(rows.begin(), rows.end());
    std::cout << "After sorting\n";
    for (auto const& row : rows)
    {
        for (auto x : row)
            std::cout << x << ' ';
        std::cout << '\n';
    }
    return 0;
}

Some sample output runs appear below, which will obviously vary form run-to-run.

Sample Output #1

Row: 9, Column: 19
90 16 9 66 78 38 28 52 27 61 24 42 10 52 83 27 74 52 20 
37 68 5 12 10 72 42 55 44 91 43 88 34 77 11 39 40 89 72 
47 67 86 74 13 88 88 65 64 60 81 10 42 26 58 5 6 88 83 
11 49 56 63 97 41 48 67 60 85 7 84 47 20 97 76 58 3 89 
83 15 87 63 88 10 54 20 16 82 5 33 69 21 23 16 36 47 3 
17 95 13 13 11 33 89 25 29 80 52 38 92 21 90 98 7 51 100 
12 4 74 64 11 73 9 1 24 28 49 92 57 69 20 50 53 80 20 
10 70 54 79 27 72 15 43 67 99 56 5 18 21 69 96 35 21 65 
90 75 26 86 45 92 47 70 27 81 18 23 64 71 51 31 10 81 94 
After sorting
1 4 9 11 12 20 20 24 28 49 50 53 57 64 69 73 74 80 92 
3 5 10 15 16 16 20 21 23 33 36 47 54 63 69 82 83 87 88 
3 7 11 20 41 47 48 49 56 58 60 63 67 76 84 85 89 97 97 
5 6 10 13 26 42 47 58 60 64 65 67 74 81 83 86 88 88 88 
5 10 11 12 34 37 39 40 42 43 44 55 68 72 72 77 88 89 91 
5 10 15 18 21 21 27 35 43 54 56 65 67 69 70 72 79 96 99 
7 11 13 13 17 21 25 29 33 38 51 52 80 89 90 92 95 98 100 
9 10 16 20 24 27 27 28 38 42 52 52 52 61 66 74 78 83 90 
10 18 23 26 27 31 45 47 51 64 70 71 75 81 81 86 90 92 94

Sample Output #2

Row: 10, Column: 15
13 33 61 44 2 69 89 95 84 29 24 87 16 96 74 
44 60 72 37 78 17 94 6 88 5 61 41 37 33 13 
56 53 26 4 67 32 50 41 21 79 41 21 17 97 85 
88 84 7 93 41 13 46 10 50 70 38 71 3 55 77 
82 53 53 71 77 33 48 36 25 82 73 58 67 63 56 
27 83 5 42 81 4 86 6 51 4 29 16 6 38 78 
94 5 87 13 4 76 66 47 97 72 55 63 96 78 43 
96 2 36 55 64 25 34 27 70 44 21 2 46 54 46 
83 85 23 48 42 14 19 89 37 73 3 15 38 41 41 
98 64 49 9 61 46 49 24 94 76 51 46 98 3 26 
After sorting
2 2 21 25 27 34 36 44 46 46 54 55 64 70 96 
2 13 16 24 29 33 44 61 69 74 84 87 89 95 96 
3 7 10 13 38 41 46 50 55 70 71 77 84 88 93 
3 9 24 26 46 46 49 49 51 61 64 76 94 98 98 
3 14 15 19 23 37 38 41 41 42 48 73 83 85 89 
4 4 5 6 6 16 27 29 38 42 51 78 81 83 86 
4 5 13 43 47 55 63 66 72 76 78 87 94 96 97 
4 17 21 21 26 32 41 41 50 53 56 67 79 85 97 
5 6 13 17 33 37 37 41 44 60 61 72 78 88 94 
25 33 36 48 53 53 56 58 63 67 71 73 77 82 82

Sample Output #3

Row: 19, Column: 17
28 40 51 8 76 81 57 43 66 4 52 81 88 88 92 16 16 
39 38 78 10 50 24 53 72 4 43 87 92 75 51 20 62 45 
76 93 5 84 35 92 54 33 1 41 96 8 70 80 21 25 10 
1 58 19 24 42 39 17 93 53 35 64 73 27 13 96 34 55 
13 99 94 54 52 14 73 50 32 2 16 64 40 14 71 70 62 
39 7 43 60 72 66 21 70 74 95 25 29 35 95 56 42 80 
74 41 88 51 55 73 45 41 8 17 8 2 64 91 66 25 37 
23 34 45 71 70 25 63 39 85 38 51 32 75 54 99 44 28 
76 84 81 52 1 22 20 89 13 11 48 82 8 21 67 9 15 
2 16 34 51 54 35 14 86 78 84 93 47 35 77 36 4 20 
23 13 36 24 14 83 38 7 84 9 97 87 62 82 27 43 3 
78 28 8 52 50 24 8 76 36 7 45 75 34 67 30 62 49 
27 52 90 65 19 88 81 78 44 53 51 59 22 51 75 52 40 
89 63 56 65 77 52 91 32 68 2 99 73 94 90 23 34 2 
67 18 43 46 30 16 44 10 86 27 76 7 71 22 15 60 20 
59 59 42 79 24 27 11 98 36 82 29 82 58 85 10 77 15 
44 83 58 21 1 33 30 77 17 94 16 81 36 40 73 46 28 
99 78 78 59 41 75 49 84 41 15 57 55 9 72 64 83 54 
48 15 4 92 37 13 76 1 46 68 52 66 39 29 76 21 70 
After sorting
1 4 13 15 21 29 37 39 46 48 52 66 68 70 76 76 92 
1 5 8 10 21 25 33 35 41 54 70 76 80 84 92 93 96 
1 8 9 11 13 15 20 21 22 48 52 67 76 81 82 84 89 
1 13 17 19 24 27 34 35 39 42 53 55 58 64 73 93 96 
1 16 17 21 28 30 33 36 40 44 46 58 73 77 81 83 94 
2 2 23 32 34 52 56 63 65 68 73 77 89 90 91 94 99 
2 4 14 16 20 34 35 35 36 47 51 54 77 78 84 86 93 
2 8 8 17 25 37 41 41 45 51 55 64 66 73 74 88 91 
2 13 14 14 16 32 40 50 52 54 62 64 70 71 73 94 99 
3 7 9 13 14 23 24 27 36 38 43 62 82 83 84 87 97 
4 8 16 16 28 40 43 51 52 57 66 76 81 81 88 88 92 
4 10 20 24 38 39 43 45 50 51 53 62 72 75 78 87 92 
7 8 8 24 28 30 34 36 45 49 50 52 62 67 75 76 78 
7 10 15 16 18 20 22 27 30 43 44 46 60 67 71 76 86 
7 21 25 29 35 39 42 43 56 60 66 70 72 74 80 95 95 
9 15 41 41 49 54 55 57 59 64 72 75 78 78 83 84 99 
10 11 15 24 27 29 36 42 58 59 59 77 79 82 82 85 98 
19 22 27 40 44 51 51 52 52 53 59 65 75 78 81 88 90 
23 25 28 32 34 38 39 44 45 51 54 63 70 71 75 85 99

Upvotes: 3

Related Questions