Ошибка слияния логики сортировки при распределении памяти.

Question

Я работаю над реализацией merge-sort, которая сортирует список песен по их длине. Я написал следующее и не смог исправить недостаток в своей логике. Вместо того, чтобы возвращать отсортированный список, эти функции возвращают список из одного элемента из середины исходного списка.

vector<song> merge(vector<song> firstList, vector<song> secondList){ 
vector<song> outPut; 
int i = 0; int n = 0; 
while(outPut.size() < (firstList.size() + secondList.size()-1)){ 
    if(firstList[i].length < secondList[n].length){ 
     outPut.push_back(firstList[i]); 
     i++; 
    }else{ 
     outPut.push_back(secondList[n]); 
     n++; 
    } 
} 
return outPut; 
} 
vector<song> mergeSortLength(vector<song> playlist){ 
int scope = playlist.size()/2; 
vector<song> firstHalf(&playlist[0], &playlist[scope]); 
vector<song> secondHalf(&playlist[scope], &playlist[playlist.size()]); 
if (firstHalf.size() != 1){ 
    firstHalf = mergeSortLength(firstHalf); 
} 
if (secondHalf.size() != 1){ 
    secondHalf = mergeSortLength(secondHalf); 
} 
return merge(firstHalf, secondHalf); 
} 

Если изменить состояние в то время как петли от

(outPut.size() < (firstList.size() + secondList.size() -1)){ 

в

(outPut.size() < (firstList.size() + secondList.size())){ 

он получает примерно на полпути, хотя список сортировки успешно, пока компилятор не выплевывает:

playList(27898,0x7fff78b7b000) malloc: * mach_vm_map(size=7526769998340063232) failed (error code=3) * error: can't allocate region *** set a breakpoint in malloc_error_break to debug libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc: std::bad_alloc Abort trap: 6

I r зная, что кто-то помогает. Мои глаза неловко смотрят на это.

Answer 1

В файле merge() код не проверяет, достигнут ли конец вектора, в частности, если i> = firstList.size() или n> = secondList.size(), в котором если бы остальная часть другого вектора была скопирована. Оператор while не должен иметь -1 ближе к концу.

VS жалуется на создание временного вектора, используя & плейлист [playlist.size()], так как индекс находится за пределами допустимого диапазона. Дополнительный способ сделать это состоит в использовании начать() + индекс, который является итератором:

vector<song> firstHalf(playlist.begin()+0, playlist.begin()+scope); 
    vector<song> secondHalf(playlist.begin()+scope, 
       playlist.begin()+playlist.size()); 

Это было в течение дня, поэтому размещение исправленной версии в случае, если кто заинтересован. Все это создание вектора и push backs добавляет много накладных расходов, было бы лучше сделать одноразовое распределение, а затем просто использовать итераторы или индексы для работы с подвекторами.

vector<song> merge(vector<song> firstList, vector<song> secondList){ 
    vector<song> outPut; 
    size_t i = 0; size_t n = 0; 
    while(outPut.size() < (firstList.size() + secondList.size())){ 
     if(firstList[i].length < secondList[n].length){ 
      outPut.push_back(firstList[i]); 
      if(++i >= firstList.size()){ 
       do 
        outPut.push_back(secondList[n]); 
       while(++n < secondList.size()); 
       break; 
      } 
     }else{ 
      outPut.push_back(secondList[n]); 
      if(++n >= secondList.size()){ 
       do 
        outPut.push_back(firstList[i]); 
       while(++i < firstList.size()); 
       break; 
      } 
     } 
    } 
    return outPut; 
} 

vector<song> mergeSortLength(vector<song> playlist){ 
    size_t scope = playlist.size()/2; 
    vector<song> firstHalf(playlist.begin()+0, playlist.begin()+scope); 
    vector<song> secondHalf(playlist.begin()+scope, playlist.begin()+playlist.size()); 
    if (firstHalf.size() != 1){ 
     firstHalf = mergeSortLength(firstHalf); 
    } 
    if (secondHalf.size() != 1){ 
     secondHalf = mergeSortLength(secondHalf); 
    } 
    return merge(firstHalf, secondHalf); 
} 

Answer 2

я не видел с большим вниманием, но, может быть, вы хотите

vector<song> secondHalf(&playlist[scope+1], &playlist[playlist.size()-1]); 

& плейлист [playlist.size()] без -1 Я думаю, что это источник вашей проблемы, но Я не пробовал.