我正在进行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); }如果我改变了while循环条件
( outPut.size() < (firstList.size() + secondList.size() -1)){至
( outPut.size() < (firstList.size() + secondList.size())){虽然列表排序成功直到编译器吐出，但它大约有一半：
playList（27898,0x7fff78b7b000）malloc： * mach_vm_map（size = 7526769998340063232）失败（错误代码= 3）*错误：无法分配区域***在malloc_error_break中设置断点以调试libc ++ abi.dylib：终止未捕获std :: bad_alloc类型的异常：std :: bad_alloc中止陷阱：6
我非常感谢任何人的帮助。 从盯着它看，我的眼睛模糊不清。
I am working on an implementation of merge-sort which will sort a list of songs by their length. I have written the following and have been unable to fins the flaw in my logic. Instead of returning a sorted list these functions return a list of one item from the middle of the original list.
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); }If I change the while loop condition from
( outPut.size() < (firstList.size() + secondList.size() -1)){to
( outPut.size() < (firstList.size() + secondList.size())){it gets about halfway though the list sorting successfully until the compiler spits out:
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 really appreciate anyones help. My eyes are going fuzzy from staring at this.
最满意答案
在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); }In merge(), the code doesn't check to see if the end of a vector has been reached, specifically, if i >= firstList.size() or n >= secondList.size(), in which case the remainder of the other vector would be copied. The while statement should not have the -1 near the end.
VS complains about the temp vector creation using &playlist[playlist.size()], since the subscript is out of range. An optional way to do this is to use begin() + index, which is an iterator:
vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope); vector<song> secondHalf( playlist.begin()+scope, playlist.begin()+playlist.size());It's been over a day, so posting a fixed version in case anyone is interested. All that vector creation and push backs add a lot of overhead, it would have been better to do a one time allocation, and then just use iterators or indices to deal with the sub-vectors.
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); }更多推荐
发布评论