在 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()){

在使用 a[p] 之前，您没有检查数组 'a' 的大小。所以，有时（由于内存浪费），a[p]可以小于b[q]，有时不能。

当然是变体。让我们在使用前检查数组大小。

Answer 2

好的，先关

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] 或 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++];
}

您会注意到我在此处更改了一些内容：

我已经从 int 移动到 size_t 这样你就可以避免所有那些丑陋的转换，因为你的变量已经匹配向量大小的类型。
我已经拆分了两个循环来清空两个向量中仍然有值的那个。
我搬到 while 了，因为我觉得这里看起来更好。

Answer 3

注意事项：

运算符优先级 - ((q < b.size()) ? a[p] < b[q] : true && p < a.size()) 相当于：(q < b.size() ? a[p] < b[q] : p < a.size())。请注意，您不考虑 p，不幸的是，p 可能已经结束（未定义的行为）——请注意，这是您的错误。修复相当简单 -

(q < b.size() && p < a.size() ? a[p] < b[q] : p < a.size())

仅当两个数组上都有任何元素时才应用比较。

此外，您的代码中有很多错误模式：

首先，你有很多多余的 C 风格转换。这很糟糕，原因有二： 1.你正在写C++，使用C++强制转换！（static_cast 在你的情况下） 2. 你没有明显的理由在选角。向量（通常在 C++ 中）的大小类型是 std::size_t 是有充分理由的。使用它！

您代码中的另一件事是您将参数作为值而不是作为 const-ref 传递，这是一种非常糟糕的做法，会导致到处发生不必要的复制。

第三，你的变量名没有意义。

第四，强烈不推荐使用命名空间 std。

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

Different output every time in c++(unexpected behavior)

c++

mergesort