0

C ++でのマージソートの次の再帰的実装について頭に浮かぶのに苦労しています

私が得たのは、ベクトルが参照によって渡され、 vec.clear() が呼び出されているため、マージの一部が行われた後でもベクトルが消去されないことです。たとえば、ベースがヒットすると、関数はスタックの一番上のフレームを返し、スタックを下に進めます。ただし、関数は複数回マージする必要があり、各マージの前にベクトルがクリアされます。これは、メモリ内のスペース (参照渡しであるため) がクリアされ、既にマージされたものを失うことを意味すると思いますか? このメソッドが値で渡された場合にどのように機能するかは理解できますが、これは参照で渡されるため、混乱しています。

void merge(vector<int> &final, vector<int> &left, vector<int> &right) {
    while (left.size() > 0 || right.size() > 0) {
        if (right.size() == 0) {
            final.push_back(left.at(0));
            left.erase(remove(left.begin(), left.end(), left.at(0)), left.end());
        }
        else if (left.size() == 0) {
            final.push_back(right.at(0));
            right.erase(remove(right.begin(), right.end(), right.at(0)), right.end());
        } else if (left.at(0) <= right.at(0)) {
            final.push_back(left.at(0));
            left.erase(remove(left.begin(), left.end(), left.at(0)), left.end());
        } else if (right.at(0) < left.at(0)) {
            final.push_back(right.at(0));
            right.erase(remove(right.begin(), right.end(), right.at(0)), right.end());
        }
    }
}

void sort(vector<int> &vec) {
    int n = vec.size();

    // BASE CASE
    if (n <= 1) {
        return;
    }

    // GENERAL CASE / RECURSIVE CASE
    vector<int> leftVec;
    vector<int> rightVec;

    for (int i = 0; i < n; i++) {
        if (i < n / 2) {
            leftVec.push_back(vec.at(i));
        } else {
            rightVec.push_back(vec.at(i));
        }
    }

    sort(leftVec);
    sort(rightVec);
    vec.clear();
    merge(vec, leftVec, rightVec);
}
4

1 に答える 1

2

の内容は呼び出しの前にvecコピーされているleftVecため、情報が失われることはありません。のソースは提供されていませんが、内容が にコピーされていると想定できます。rightVecclearmergevec

于 2013-03-09T04:14:11.180 に答える