在 C++ 中每次输出不同（意外行为）

Question

这是合并排序的代码，有时它给出正确的输出，但有时它给出一个值改变的输出。

#include "bits/stdc++.h"
using namespace std;

//function to merge two array
vector<int> merging(vector<int> a,vector<int> b){   
    int x = (int)a.size() + (int)b.size();
    vector<int> v(x);
    int p = 0;
    int q = 0;
    for(int i=0;i<x;++i){
        if((q<(int)b.size())?a[p]<b[q]:true && p<(int)a.size()){
            v[i] = a[p];
            p++;
        }else{
            v[i] = b[q];
            q++;
        }
    } 
    return v;
}


//splitting the array and then merging the array
vector<int> mergeSort(vector<int> k){
   int x = (int)k.size();
   if(x<2){
       return k;
   }
   vector<int> a(k.begin(),k.begin()+(x/2));
   vector<int> b(k.begin()+(x/2),k.end());
   return merging(mergeSort(a),mergeSort(b));
}


int main(){
    vector<int> v = {3,5,34,11,32,7,35,54,67,89,23,4,3};
    //calling the merge function
    vector<int> b = mergeSort(v);
    for(int i=0;i<(int)b.size();++i){
        cout << b[i] << "\n";
    }
  return 0;
}

预计有时会输出 3 3 4 5 7 11 23 32 34 35 54 67 89

有时输出是 3 3 4 5 7 11 23 32 34 -423887504 35 54 67

Answer 1

好的首先

if((q<(int)b.size())?a[p]<b[q]:true && p<(int)a.size()){

哎呀。

这真是一个令人费解的逻辑。你在 if 中有一个三元组，你有true && ...（这...和那里的东西是一样的）并且任何地方都绝对没有空格，这使得整个事情变得更加不可读。这不会通过发生在我 100 英尺范围内的任何代码审查。甚至在我深入研究您的代码之前，我就猜到这就是问题所在。

因此，在您的示例中，当您尝试最后一次合并时，您将拥有以下值：

a = {35, 54, 67}
b = {3, 4, 23, 89}

让我们通过您的合并来完成它......对于前几个循环来说一切都很好，直到您拥有：

p = 3
q = 3
x = 7
i = 6
v = {3, 4, 23, 35, 54, 67, 0}

现在，我们正在进入循环，这i < x是真的，所以我们仍在继续。我们得到你的兴趣如果。

q < b.size()是真的，3 < 4。所以我们看看a[p] < b[q]or a[3] < b[3]。哦哦！你看到问题了吗？a[3]超出范围。这意味着未定义的行为。

我不会尝试在一个循环中完成所有操作，而是尝试编写干净的代码而不是短代码并使用另一个循环。在您清空另一个循环后，此循环将清空a或清空b您留下的任何一个（或按照我编写的方式，它将是两个循环，其中只有一个将运行）。

那看起来像：

size_t p = 0, q = 0, i = 0;

while(p < a.size() && q < b.size()) {
    if(a[p] < b[q]) {
        v[i++] = a[p++];
    } else {
        v[i++] = b[q++];
    }
}

while(p < a.size()) {
    v[i++] = a[p++];
}

while(q < b.size()) {
    v[i++] = b[q++];
}

你会注意到我在这里改变了几件事：

• 我已经从intto转移了，size_t这样你就可以在任何地方避免所有那些丑陋的强制转换，因为你的变量已经与向量大小的类型相匹配。
• 我已经拆分了两个循环以清空两个向量中仍然有值的任何一个。
• 我已经搬到了while's，因为我认为它们在这里看起来更好。