Проблема с Mergesort в C ++ - PullRequest
Новая
       14

Проблема с Mergesort в C ++

2 голосов
/ 19 апреля 2010 
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;
}

Правильно компилируется, но во время выполнения получаю:

Это приложение запросило время выполнения, чтобы закончить его необычным способом.

Это странная ошибка.

Есть ли что-то, что в корне неправильно в коде?

Ответы [ 4 ]

7 голосов
/ 19 апреля 2010

Это result.reserve(a.size()) влияет только на емкость вектора , а не размер . ( емкость вектора указывает, до какого размера вектор может расти без необходимости перераспределения и копирования всех членов. По сути, он существует только для целей оптимизации.) Вы не можете получить доступ к любым членам в result после этой оговорки, поскольку их нет. Либо используйте result.push_back(...) вместо result[dp] = ... или result.resize(a.size()) вместо result.reserve(a.size()).

Полагаю, первое может быть более эффективным.

5 голосов
/ 19 апреля 2010

Одна проблема связана с использованием reserve() (либо используйте resize(), либо добавьте элементы с push_back() вместо доступа к индексу). 

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

Это может быть еще одна проблема. Если размер равен 2, то ll окажется пустым вектором, и эта функция не справится с этим. В любом случае, нет особой причины вычитать 1 из середины.

Также возможно, что вы копируете вещи куда больше, чем нужно: вам не нужны векторы l и r (потому что они будут просто копиями ll и rr), аналогично Я не думаю, что вам нужен вектор result, так как вы можете просто записать объединенные результаты обратно в a.

1 голос
/ 19 апреля 2010

reserve () не изменяет количество содержимого в векторе. Вы создали пустой вектор, зарезервировали для него определенный размер, а затем использовали v [i] = x; Это недопустимое использование вектора, поскольку в векторе до сих пор нет i-го элемента.

Вместо этого используйте resize ().

0 голосов
/ 19 апреля 2010

Сообщение об ошибке очень неясно, потому что это стандартное сообщение VC ++, когда исключение остается необработанным. Вы можете добавить в свой основной список try-catch-clock, чтобы получить исключение и более значимую ошибку: 

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

Это для командной строки. Если в вашем приложении его нет, используйте окно сообщения или запишите ошибку в лог-файл.

Что касается проблемы в вашем коде, все остальные ответы кажутся правильными.

...