Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

I am having problem with sorting a dynamic allocated array of struct, please help me find out what goes wrong.

Here's my code

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct Box{
    int *dimval;
    int dim;

    ~Box(){
        delete[] dimval;
    }

    friend bool operator < (const Box& a, const Box& b){
        for(int i=0; i<a.dim;i++){
            if(a.dimval[i]>b.dimval[i])
                return false;
        }
        return true;
    }

    void msort(){
        sort(dimval, dimval+dim);
    }

} *boxes;

int main(){
    int num_box, dim;

    scanf("%d%d", &num_box, &dim);

    boxes = new Box[num_box];
    for(int i=0;i<num_box;i++){
        boxes[i].dim = dim;
        boxes[i].dimval = new int[dim];
    }

    for(int i=0;i<num_box; i++){
            for(int j=0;j<dim; j++){
                scanf("%d", &(boxes[i].dimval[j]));
            }
            boxes[i].msort();
    }

    for(int i=0;i<num_box; i++){
            for(int j=0;j<dim; j++){
                cout<<boxes[i].dimval[j]<<" ";
            }
            cout<<endl;
    }
    cout<<"-----"<<endl;

    sort(boxes, boxes+num_box);
    for(int i=0;i<num_box; i++){
        for(int j=0;j<dim; j++){
            cout<<boxes[i].dimval[j]<<" ";
        }
        cout<<endl;
    }
    cout<<"xxxxxxx"<<endl;
}

Given the sample input

8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

The output for the above code snippet is

1 2 5 10 20 30 
3 7 9 11 15 23 
4 14 24 34 40 50 
9 10 11 12 13 14 
4 8 17 18 27 31 
13 19 19 32 41 44 
1 2 3 4 5 6 
9 18 21 37 47 80 
-----
1 2 3 4 5 6 
1 2 5 10 20 30 
201056 200608 9 11 15 23 
4 14 24 34 40 50 
9 10 11 12 13 14 
4 8 17 18 27 31 
201728 200784 19 32 41 44 
9 18 21 37 47 80 
xxxxxxx

As you can see, sorting inside a Box struct is good, but sorting among Box is troublesome, can anyone help explain the problem here and how should it be resolved. Thanks

----------------------UPDATE---------------------------------------

I know using pointer to box might be the devil, but I cannot see why, please enlighten me with reasons and examples. Besides, the following is a code snippet from a sample solution. Here, the only difference is that it's using an array of struct instead of a pointer to a dynamically allocated array, and it's getting the correct output

here's the code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
    int A[12];
    int k;
    void Sort(){
        sort(A,A+k);
    }
    friend bool operator < (const Node&a, const Node&b){
        for(int i=0; i<a.k; ++i){
            if(a.A[i]>b.A[i])return false;
        }
        return true;
    }
}arr[32];

int n,k;

int main(){
scanf("%d%d",&n,&k);
       for(int i=0; i<n; ++i){
            for(int j=0; j<k; ++j)
                scanf("%d",&arr[i].A[j]);
            arr[i].k=k;
            arr[i].Sort();
        }
        for(int i=0;i<n; i++){
            for(int j=0;j<k; j++){
                cout<<arr[i].A[j]<<" ";
            }
            cout<<endl;
        }
        cout<<"-----"<<endl;

        sort(arr,arr+n);
        for(int i=0;i<n; i++){
            for(int j=0;j<k; j++){
                cout<<arr[i].A[j]<<" ";
            }
            cout<<endl;
        }
        cout<<"xxxxxx"<<endl;
}

1 2 5 10 20 30 
3 7 9 11 15 23 
4 14 24 34 40 50 
9 10 11 12 13 14 
4 8 17 18 27 31 
13 19 19 32 41 44 
1 2 3 4 5 6 
9 18 21 37 47 80 
-----
1 2 3 4 5 6 
1 2 5 10 20 30 
3 7 9 11 15 23 
4 14 24 34 40 50 
9 10 11 12 13 14 
4 8 17 18 27 31 
13 19 19 32 41 44 
9 18 21 37 47 80 
xxxxxx

----------------------------UPDATE 2-----------------------

I tried to add a copy constructor and an assignment overload to my Box struct, but this didn't work out as expected. The error code is ntdll!RtlpNtEnumerateSubKey() at 0x779d0725
Anything wrong with this implementation?

struct Box{
    int *dimval;
    int no;
    int dim;

    Box(){};

    Box(const Box& another){
        no = another.no;
        dim = another.dim;
        dimval = new int[no];
        memcpy(dimval, another.dimval, dim*sizeof(int));
    }

    Box& operator = (const Box& another){
        if(this != &another){
            no = another.no;
            dim = another.dim;
            int* tmp = new int[no];
            delete [] dimval;
            dimval = tmp;
            memcpy(dimval, another.dimval, dim*sizeof(int));
        }
        return *this;
    }

    ~Box(){
        delete[] dimval;
    }

    friend bool operator < (const Box& a, const Box& b){
        for(int i=0; i<a.dim;i++){
            if(a.dimval[i]>=b.dimval[i])
                return false;
        }
        return true;
    }

    void msort(){
        sort(dimval, dimval+dim);
    }

} *boxes;
share|improve this question
1  
Please avoid pointers (new/delete) –  Dieter Lücking yesterday
    
why? I wanted a dynamic array so have to use pointers new –  Daniel yesterday
5  
std::vector is the way you write dynamic array in C++. –  James Kanze yesterday
3  
You doing it wrong. Example: int main() { Box it; } // crash –  Dieter Lücking yesterday
1  
Does anyone know how to debug today? It it a lost art? Is debugging illegal now, some law? –  Martin James yesterday
show 14 more comments

1 Answer

up vote 2 down vote accepted

It's obvious why the ordering is incorrect. Your operator < is wrong, it should return true as soon as one element is less than the other.

As for the data corruption, it's because you violated the "rule of three" - you have a custom destructor but not a copy constructor or assignment operator. sort makes copies of elements that it sorts, and when the destructor hits it deletes the pointer it was holding. This results in undefined behavior.

Edit: the reason the code works with a fixed array but not a pointer is that the default copy constructor and assignment operators will make a full copy - when the original gets destroyed, it doesn't mess up the copies or invalidate their memory.

Your "fix" may appear to work, but now you've got a memory leak. Nobody is ever going to delete those pointers.

One other point about operator <, it should never return true with A=B; if(A<B) but yours does.

share|improve this answer
    
no that's not the way < is defined in my context. Here I wanted < to mean a component wise small. i.e., every element in a Box is smaller than that in another Box –  Daniel yesterday
    
@Daniel, OK I guess that's legit, as long as the result is always consistent. –  Mark Ransom yesterday
    
@Daniel Which doesn't provide a strict weak ordering. –  James Kanze yesterday
    
The illegal comparison operator could also cause the problem, since it could easily lead to sort going out of bounds, and copying from one into another. (But the violation of the rule of three is the killer. All because he didn't use std::vector.) –  James Kanze yesterday
    
@MarkRansom I tried deleting the destructor and it worked! Thanks so much I didn't know this rule and it turned out to be nothing related to dynamic array.. –  Daniel yesterday
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.