1

我有这个合并排序功能

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 */    
}

这是我的主要方法

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;
}

链接到bitbucket.org 项目

我的问题是这个。

如果列表从切片函数正确返回，为什么它不能正确返回到主函数，如果它以相同的方式完成？

[更新]添加了功能，因为它们目前正在以应有的方式运行。完整版本已在 bitbucket 上发布。

4

1 回答 1

3

检查您提供的链接中的完整代码后，我可以肯定地说问题是因为您没有赋值运算符。

现在发生的是列表的赋值将使用编译器自动生成的默认赋值运算符。这会进行浅拷贝，因此赋值左侧的列表的指针与右侧列表的指针相同。这意味着当您返回的局部变量超出范围时，它当然会调用删除列表的析构函数。现在副本有指向已删除内存的指针，访问这些指针是未定义的行为。这就是为什么它似乎在一个地方而不是另一个地方工作。

于 2012-11-21T10:59:50.587 回答