CODEWITHSUNDEEP
c++linked-listmergesort
bitcycle
bitcycle

Reputation: 7792

Why is this merge sort function returning linked list with zeroes (c++)?

I've got this merge sort function

namespace sorted{

    template<typename T>
    class list {

        /* other stuff */

        list<T>* slice(int from, int to){
            from = (from < 0) ? 0 : from;
            to = (to > this->len) ? this->len : to;
            list<T>* result = new list<T>();
            node<T> *n = this->head;
            int idx = 0;
            while (n && (idx < this->len)){
                if ((from <= idx) && (idx <= to)) result->append(n->value);
                if (idx > to) break;
                n = n->next;
                idx++;
            }
            return result;
        }            
    }

    template<typename T>
    list<T>* merge(list<T>* left, list<T>* right){
        list<T>* result = new list<T>();
        while ((left->length() > 0) || (right->length() > 0)){
            if ((left->length() > 0) && (right->length() > 0)){
                T l = left->get(0);
                T r = right->get(0);
                if (l <= r){
                    result->append(l);
                    left->remove(0);
                } else{
                    result->append(r);
                    right->remove(0);
                }
                continue;
            }

            if (left->length() > 0) {
                result->append(left->get(0));
                left->remove(0);
            }

            if (right->length() > 0) {
                result->append(right->get(0));
                right->remove(0);
            }
        }
        return result;
    }

    template<typename T>
    list<T>* merge_sort(list<T>* original){
        if (original->length() <= 1) {
            return original;
        }
        int len = original->length();
        list<T>* left = NULL;
        list<T>* right = NULL;
        if (len > 2){
            left = original->slice(0,(len/2));
            right = original->slice((len/2)+1,len-1);
        }else if (len == 2){
            left = original->slice(0,0);
            right = original->slice(1,1);
        }
        left = merge_sort(left);
        right = merge_sort(right);
        delete original;
        list<T>* result = merge(left, right);
        delete left;
        delete right;
        return result;
    }

    /* other stuff */    
}

And here's my main method

int main(int argc, char** argv){
    sorted::list<int>* l = get_random_list();
    l = merge_sort(l);
    for (int i = 0; i < (l->length() - 1); i++){
        int t = l->get(i);
        int u = l->get(i+1); 
        if (t > u){
            sorted::list<int>* m = l->slice(i - 5, i + 5);
            cout << m << endl;
            delete m;
            break;
        }
    }
    delete l;
    return 0;
}

Link to bitbucket.org project

My question was this.

If the list is returned properly from the slicing function, why would it not be returned to the main function properly, if its being done the same way?

[Update] Added functions as they're currently functioning the way they should be. A full version is up on bitbucket.

Upvotes: 1

Views: 222

Answers (1)

Some programmer dude
Some programmer dude

Reputation: 409176

After checking your full code in the link you provided, I can definitely say the problem is because you don't have an assignment operator.

What happens now is that the assignments of the lists will use the default assignment operator that is automatically generated by the compiler. This does a shallow copy, so the list on the left hand side of the assignment will have its pointers be the same as for the list on the right hand side. This means that when the local variable you return goes out of scope, it will of course invoke the destructor which deletes the lists. Now the copy have pointers which points to deleted memory, and accessing thos pointers is undefined behavior. This is why it seems to work in one place and not the other.

Upvotes: 3

Related Questions