c++ code producing different outputs through Visual Studio c++ and Gcc

Question

I have the following C++ Program:

//============================================================================
// Name        :
// Author      : Bryce Sandlund
// Version     :
// Copyright   :
// Description : Code skeleton
//============================================================================

#include <iostream>
#include <iomanip>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <sstream>
#include <list>
#include <map>
#include <fstream>
#include <string>
#include <time.h>
#include <queue>
#include <tuple>
#include <functional>
#include <unordered_set>
#include <unordered_map>

#define INF 1000000000
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EP .00001

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<ii> vii;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef long long LL;

vvi adjList;
unordered_map<string, int> targs;

int add(string &s)
{
    if (targs.count(s))
        return targs[s];

    targs[s] = targs.size();
    adjList.push_back(vi());
    return targs.size()-1;
}

void connect(int si, int ti)
{
    if (si == ti)
        return;

    for (int i = 0; i < adjList[si].size(); ++i)
    {
        if (adjList[si][i] == ti)
            return;
    }

    adjList[si].push_back(ti);
}

vi bfs(int s)
{
    queue<ii> q;
    q.push(ii(s, -1));

    vi dist(adjList.size(), INF);

    while (!q.empty())
    {
        int top = q.front().first;
        int hops = q.front().second;
        q.pop();
        if (dist[top] != INF)
            continue;

        dist[top] = hops;
        for (int i = 0; i < adjList[top].size(); ++i)
        {
            q.push(ii(adjList[top][i], hops+1));
        }
    }

    return dist;
}

int main() {
    int caseNum = 1;
    cout << "Case " << caseNum << ":" << endl;
    string line;
    while (getline(cin, line))
    {
        stringstream ss(line);

        string command;
        ss >> command;
        if (command == "add")
        {
            string s, t;
            ss >> s;

            int si = add(s);
            if (ss >> t)
            {
                int ti = add(t);

                connect(si, ti);
                connect(ti, si);
            }
        }
        else if (command == "connections")
        {
            string s;
            ss >> s;

            if (!targs.count(s))
            {
                cout << "target does not exist" << endl;
                continue;
            }

            int st = targs[s];
            if (adjList[st].empty())
            {
                cout << "no connections" << endl;
            }
            else
            {
                vi dist = bfs(st);

                vi away(adjList.size(), 0);
                int maxd = -1;
                for (int i = 0; i < dist.size(); ++i)
                {
                    if (dist[i] == INF || dist[i] == -1)
                        continue;

                    ++away[dist[i]];
                    maxd = max(maxd, dist[i]);
                }

                for (int i = 0; i <= maxd; ++i)
                {
                    cout << i << ": " << away[i] << endl;
                }
            }
        }
        else if (command == "associated")
        {
            string s, t;
            ss >> s >> t;

            if (!targs.count(s) || !targs.count(t))
            {
                cout << "target does not exist" << endl;
                continue;
            }

            int si = targs[s], ti = targs[t];
            vi dist = bfs(si);

            if (dist[ti] == INF)
            {
                cout << "no" << endl;
            }
            else
            {
                cout << "yes " << dist[ti] << endl;
            }
        }
        else
        {
            adjList.clear();
            targs.clear();
            cout << "----------" << endl;
            cout << "Case " << ++caseNum << ":" << endl;
        }
    }

    cout << "----------" << endl;
    return 0;
}

I am using this as input:

add a b
add a c
add b d
add e b
add c f
add c g
add f h
add h i
add j k
associated a i
associated i a
associated f k
associated a h
connections a
connections i
add k g
associated a j
connections a
add h a
connections a
associated a h
add m
add n n
connections n
add a n
connections n

In Visual C++, the code produces this output (it does so on Debug or Release):

Case 1:
yes: 3
yes: 3
no
yes: 2
0: 2
1: 4
2: 1
3: 1
0: 1
1: 1
2: 1
3: 2
4: 1
5: 2
yes: 3
0: 2
1: 4
2: 2
3: 2
0: 3
1: 5
2: 1
3: 1
yes: 0
no connections
0: 1
1: 3
2: 5
3: 1
4: 1
----------

On gcc g++, it produces this output:

Case 1:
no
no
yes 0
no
0: 2
1: 2
2: 2
3: 1
0: 1
no
0: 2
1: 2
2: 2
3: 1
0: 3
1: 2
2: 2
3: 1
yes 0
----------

For reference, I am trying to solve this problem: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=620&page=show_problem&problem=4574.

Any ideas why the input and output would be different on the different compilers? I don't believe I am using any undefined behavior.

Answer 1

The cause of the differences in the behavior of the code in the two platforms is the add function. You have:

int add(string &s)
{
    if (targs.count(s))
        return targs[s];

    targs[s] = targs.size();
    adjList.push_back(vi());
    return targs.size()-1;
}

In that function, the problematic line is:

    targs[s] = targs.size();

The line is tricky because depending on which side of the assignment operator gets evaluated first, you get different behavior. Please note that targs[s] involves a function call that changes the object.

You can change the function a little bit to make it consistent and predictable across platforms.

int add(string &s)
{
    if (targs.count(s))
        return targs[s];

    int size = targs.size();
    targs[s] = size;
    adjList.push_back(vi());
    return size;
}