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 に答える