c++ - 在 LLVM 和 gcc 中运行时的不同结果

Question

几天前，在我的笔记本电脑上运行的脚本与在另一个 Linux 机器上运行的脚本运行方式不同(我运行的脚本彼此相同)。我的猜测是我的编译器遗漏了一些东西。我不知道问题是什么。

运行 g++ -v 后，这是我得到的结果:

Apple LLVM version 7.0.0 (clang-700.1.76)
Target: x86_64-apple-darwin14.5.0
Thread model: posix

在另一个 Linux 机器上运行 g++ -v 后，我得到:

Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/4.8.3/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++,objc,obj-c++,java,fortran,ada,go,lto --enable-plugin --enable-initfini-array --disable-libgcj --with-isl=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-redhat-linux/isl-install --with-cloog=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-redhat-linux/cloog-install --enable-gnu-indirect-function --with-tune=generic --with-arch_32=x86-64 --build=x86_64-redhat-linux
Thread model: posix
gcc version 4.8.3 20140911 (Red Hat 4.8.3-9) (GCC) 

以下脚本是计算从一个源顶点到所有顶点的最短路径的脚本，在本例中为顶点 1。此脚本的输出列出了每个顶点及其从源到它的最短距离。有问题的输入文件也在下面列出。这是我的脚本:

#include <iostream>
#include <sstream>
#include <fstream>
#include <list>
#include <limits>

using namespace std;

struct Node{
    int dist;
    int v;

    bool operator==(const Node& a){
        return dist == a.dist;
    }

    bool operator!=(const Node& a){
        return (!(dist  == a.dist));
    }

    bool operator<(const Node& a){
        return dist < a.dist;
    }
    bool operator>(const Node& a){
        return a.dist < dist;
    }
    int operator+(const Node& a){
        return a.dist+dist;
    }
};

struct cheapHeap{
    int curSize;
    Node * minHeap;
};

class DijkstraSolution{

    private:
        int size;
        int sourceV;
        list<Node> *container; //this is the container to hold input data
        int *results;          //this is the array to hold final results
        cheapHeap ch;          //this is the array that holds each dist looked at

    public:
        DijkstraSolution(string fname, int inSourceV, int inSize): size(inSize), sourceV(inSourceV){

            //read the file and initialize the list<Node> container
            container = new list<Node>[size];

            ifstream infile;
            infile.open(fname.c_str());
            string line = "";

            if (infile){
                while (getline(infile, line)){
                    istringstream iss(line);
                    int vertex;
                    int v;
                    int dist;
                    iss >> vertex;
                    while(iss >> v >> dist){
                        Node edges;
                        edges.dist = dist;
                        edges.v = v;
                        container[vertex].push_back(edges);
                    }
                }
            }
            infile.close();

            //initialization of results and minHeap array
            int maxVal = numeric_limits<int>::max();
            results = new int[size];

            ch.curSize = size-1; 
            ch.minHeap = new Node[size];

            for (int i = 0; i < size; i++){
                results[i] = maxVal;
                ch.minHeap[i].dist = maxVal;
            }
            results[sourceV] = 0;
            ch.minHeap[sourceV].dist = 0;
            ch.minHeap[sourceV].v = sourceV;

        }

        //find min of all nodes inserted into minHeap
        Node findMin(){
            Node minimum;
            minimum.dist = numeric_limits<int>::max();
            minimum.v = 0;

            for (int i=1; i <= size; i++){
                if ((ch.minHeap[i] < minimum) && (ch.minHeap[i].dist != -1)){
                    minimum = ch.minHeap[i];

                }
            }
            ch.minHeap[minimum.v].dist = -1;
            ch.curSize--;
            return minimum;
        }

        //for every min that findMin() spits out, insert this min into the results array 
        int * dijkstra(){
            while (ch.curSize != 0){
                Node minimum = findMin(); 
                results[minimum.v] = minimum.dist; 

                for (list<Node>::iterator it = container[minimum.v].begin(); it != container[minimum.v].end(); it++){
                    if ((*it)+minimum < ch.minHeap[(*it).v].dist){
                        Node inserted;
                        inserted.dist = *it + minimum;
                        inserted.v = (*it).v;
                        ch.minHeap[(*it).v] = inserted;

                    }
                }
            }
            return results;
        }

        //this prints the contents from the file input
        void printContainer(){
            for (int i=1; i < size; i++){
                cout << i << " ";
                list<Node>::iterator iter;
                for (iter = container[i].begin(); iter != container[i].end(); iter++){
                    cout << iter -> v << " " << iter -> dist << " ";
                }
                cout <<endl;
            }
        }

        //this prints out the contents from the results array   
        void printResults(){
            for (int i = 1; i < size; i++){
                cout << i << " -> " << results[i] << endl;
            }
        }
};

int main(){

    DijkstraSolution ds("pa5_test1.txt", 1, 9);

    ds.dijkstra(); 
    ds.printResults();

}

这是我的输入文件:

1   2 1 8 2
2   1 1 3 1
3   2 1 4 1
4   3 1 5 1
5   4 1 6 1
6   5 1 7 1
7   6 1 8 1
8   7 1 1 2

这是我从我的 Mac 获得的输出，这是不正确的:

1 -> 0
2 -> 2147483647
3 -> 2147483647
4 -> 2147483647
5 -> 2147483647
6 -> 2147483647
7 -> 2147483647
8 -> 2147483647

这是我从其他 Linux 机器获得的输出，这是正确的:

1 -> 0
2 -> 1
3 -> 2
4 -> 3
5 -> 4
6 -> 4
7 -> 3
8 -> 2

显然，我的编译器没有更新结果数组。显然，它将第一个条目更新为 0，然后就停止更新了。这真的很奇怪，因为我在不同的机器上运行了完全相同的代码并且结果与 Linux 机器相同，所以我猜这是我的编译器。令人沮丧的是我没有收到任何错误，所以我什至不知道从哪里开始寻找答案。另外，不确定这是否相关，但是当我启动 gdb 时，它不会调试作为类编写的脚本。它只调试具有 main 和函数的代码，当我编写实例化某个类的 main 函数时它会跳闸。如果我的编译器确实坏了，关于如何重建它有什么建议(婴儿步骤)吗？很抱歉这篇文章很长。

Answer 1

一个问题是:

    for (int i=1; i <= size; i++){  // <-- Index goes out of bounds here
        if ((ch.minHeap[i] < minimum) && (ch.minHeap[i].dist != -1)){
            minimum = ch.minHeap[i];

您正在循环到 size，但是 minHeap[size] 是越界访问。