我试图使这个合并排序函数对 vector 或单词节点(包含单词长度、出现次数和单词本身)进行排序它似乎进入合并函数一次,然后程序失败,有什么想法吗?
bool Utility::mergeSort_occurences(vector<Word> &invector){
if (invector.size() <= 1){
return true;
}
vector<Word> left, right;
int middle = (invector.size()/2);
for(int i = 0 ; i < middle ; i++){
left.push_back(invector[i]);
}
for(int i = middle ; i < invector.size() ; i++){
right.push_back(invector[i]);
}
mergeSort_occurences(left);
mergeSort_occurences(right);
invector = mergeOccurences(left, right);
return true;
}
vector<Word> Utility::mergeOccurences(vector<Word> &left, vector<Word> &right){
vector<Word> mergelist;
while(left.size() > 0 || right.size() > 0){
if(left.size() > 0 && right.size() > 0){
if(left[0].getOccurences() <= right[0].getOccurences()){
mergelist.push_back(left[0]);
left.erase(left.begin());
}else{
mergelist.push_back(right[0]);
right.erase(right.erase(right.begin()));
}
}
else if(left.size() > 0){
mergelist.push_back(left[0]);
left.erase(left.begin());
}
else if(right.size() > 0){
mergelist.push_back(right[0]);
right.erase(right.erase(right.begin()));
}
}
return mergelist;
}
最佳答案
您的 right.erase(right.erase(right.begin()));
代码看起来很狡猾。 erase
函数返回一个迭代器,指向被删除元素的后继元素,如果删除最后一个元素,则为 end()
。
您使用 right.size() > 0
来保护这段代码,它只保证只有一项。您有两个删除操作。
您是否研究过在 right.end()
上执行 erase
的后果?
关于C++合并排序不会合并?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10081781/