CODEWITHSUNDEEP
c++algorithmvector
Nalin Bhardwaj
Nalin Bhardwaj

Reputation: 223

Inconsistency between int and bool

I just implemented breadth first search in c++ and instead of declaring a vector as bool, I declared it as an int. This lead to a very odd observation. When I used int, the code printed the following:

1
32763
-524268732

Throughout the entire code, I don't provide any such value to variable as the 2nd and 3rd node receive, so I assume that they are just garbage values, but why do garbage values even come up, when I'm initialising the vector to be full of zeroes ??? You may check the code to be that below:

#include <iostream>
#include <queue>
using namespace std;

queue<int> neigh;
vector< vector<int> > graph(3);
vector<int> flag(3, 0);

int main(void)
{
    graph[0].push_back(1); graph[0].push_back(2);
    graph[1].push_back(0); graph[1].push_back(2);
    graph[2].push_back(0); graph[3].push_back(1);
    neigh.push(0);
    while(!neigh.empty())
    {

        int cur = neigh.front();
        neigh.pop();
        flag[cur] = 1;

        for(int i = 0, l = graph[cur].size();i < l;i++)
        {
            if(!flag[graph[cur][i]])
                neigh.push(graph[cur][i]);
        }
    }
    for(int i = 0;i < 3;i++)
    {
        cout << flag[i] << endl;
    }
}

Alright, then I changed just a single line of code, line number 7, the one where I declare and initialise the flag vector.

Before:

vector<int> flag(3, 0);

After:

vector<bool> flag(3, false);

And voila! The code started working:

1 //The new output
1
1

So, my question is, what is the problem with the code in the first place ? I believe it may be some kind of error I made, or possibly that its only by chance that my bfs implementation works at all... So, what is the truth, SO? What is my (possible) mistake ?

Upvotes: 0

Views: 82

Answers (1)

juanchopanza
juanchopanza

Reputation: 227370

You are accessing your vector out of bounds here:

graph[3].push_back(1);

At this moment, graph only has three elements. This leads to undefined behaviour.

Upvotes: 4

Related Questions