分配内存时合并排序逻辑失败。

Question

我正在研究合并排序的实现，它将按长度对歌曲列表进行排序。我写了以下内容，但无法找出我逻辑中的缺陷。这些函数 return 不是 return 排序列表，而是原始列表中间的一个项目的列表。

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

如果我将 while 循环条件从

( 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

非常感谢任何人的帮助。我的眼睛因为盯着这个而变得模糊。

Answer 1

我没有看到很多关注，但也许你想要

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

没有 -1 的 &playlist[playlist.size()] 我认为是你问题的根源，但是我没试过。

Answer 2

在 merge() 中，代码不会检查是否已到达向量的末尾，特别是如果 i >= firstList.size() 或 n >= secondList.size ()，在这种情况下，将复制另一个向量的剩余部分。 while 语句的末尾不应该有 -1。

VS 抱怨使用 &playlist[playlist.size()] 创建临时矢量，因为下标超出范围。一种可选的方法是使用 begin() + index，它是一个迭代器：

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

已经过了一天多了，所以发布一个固定版本以防有人感兴趣。所有向量的创建和推回都会增加很多开销，最好是一次性分配，然后只使用迭代器或索引来处理子向量。

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

分配内存时合并排序逻辑失败。

Merge sort logic failure in allocating memory.

c++

sorting

logic

mergesort