Have Geek Brain

Mergesort problem in C ++

vector<int>& mergesort(vector<int> &a) {
    if (a.size() == 1) return a;
    int middle = a.size() / 2;
    vector<int>::const_iterator first = a.begin();
    vector<int>::const_iterator mid = a.begin() + (middle - 1);
    vector<int>::const_iterator last = a.end();
    vector<int> ll(first, mid);
    vector<int> rr(mid, last);

    vector<int> l = mergesort(ll);
    vector<int> r = mergesort(rr);
    vector<int> result;
    result.reserve(a.size());
    int dp = 0, lp = 0, rp = 0;

    while (dp < a.size()) {
        if (lp == l.size()) {
            result[dp] = (r[rp]);
            rp++;
        } else if (rp == r.size()) {
            result[dp] = (l[lp]);
            lp++;
        } else if (l[lp] < r[rp]) {
            result[dp] = (l[lp]);
            lp++;
        } else {
            result[dp] = (r[rp]);
            rp++;
        }
        dp++;
    }
    a = result;
    return a;
}

It compiles correctly, but at runtime I get:

This application requested a runtime to terminate in an unusual way.

This is a strange error.

Is there something that is fundamentally wrong with the code?

+2


a source to share


4 answers


One issue is usage reserve()

(either use resize()

or add elements with push_back()

instead of accessing the index).

if (a.size() == 1) return a;
int middle = a.size() / 2;
vector<int>::const_iterator first = a.begin();
vector<int>::const_iterator mid = a.begin() + (middle - 1);
vector<int>::const_iterator last = a.end();
vector<int> ll(first, mid);
vector<int> rr(mid, last);


This could be another problem. If the size is 2, it ll

turns out to be an empty vector, and this function doesn't seem to be able to handle it. There seems to be no reason to subtract 1 from the middle.

It is also possible that you are copying things a lot more than you need to: you don't need vectors l

and r

(because they will just be instances of ll

and rr

), similarly I don't think you need a vector result

, since you can just write the combined results back to a

.

+5


a source


This result.reserve(a.size())

only affects the vector capacity , not the size . (The capacity of a vector indicates to what size the vector can grow, without having to reallocate and copy all the members. Basically this is just there for optimization purposes.) After that caveat, you cannot access any members in result

, since there aren't any ... Use result.push_back(...)

instead of result[dp] = ...

or result.resize(a.size())

instead of result.reserve(a.size())

.



I believe the former could be more effective.

+7


a source


reserve () does not change the amount of content in the vector. You created an empty vector, reserved a specific size for it, and then used v [i] = x; This is not a valid use of the vector, since the vector does not yet have the i-th element.

Use resize () instead.

+1


a source


The error message is very unclear because it is a standard VC ++ message when an exception is handled without handling. You can add a trigger to your main time to get an exception and a more meaningful error:

int main() {
    try {
        // do main stuff here
    }
    catch ( std::exception & e ) {
        std::cout << e.what() << std::endl;
    }
}

This is for the command line. If your application doesn't have one, use a message box or write the error to a log file.

Regarding the problem in your code, all other answers seem to be correct.

0


a source






More articles:


All Articles