vector <bool> iterator not dereferencable

Question

I am trying to debug my program after writing it and I run into this error:

Here is my code:

#include<fstream>
#include <iostream>
#include <vector>
#include <string>
#define MAXINT 2147483647

using namespace std;

struct Edge
{
int id, weight;

Edge(int y, int w)
{
    id = y;
    weight = w;
}
};

struct Node
{
vector <Edge *> Edges;
};

struct Graph
{
vector < Node *> vertices;
vector < int > indices;

void Resize(int x)
{
    if (vertices.capacity() < x)
        vertices.resize(x);
}

void InsertEdge(int x, int y, int weight)
{
    Resize(((x > y) ? x : y) + 1);
    InsertVertex(x);
    InsertVertex(y);
    vertices[x]->Edges.push_back(new Edge(y, weight));
}

void InsertVertex(int x)
{
    if (vertices[x] == NULL)
    {
        Node *t = new Node;
        vertices[x] = t;
        indices.push_back(x);
    }
}
};



void Dij(Graph const &g, int start)
{
Node *temp;
vector<bool> check;
vector<int>  distance, prev;
int v, w, weight, dist;

for (int i = 0; i <= g.indices.size(); i++)
{
    check.push_back(false);
    distance.push_back(MAXINT);
    prev.push_back(-1);
}

v = start;
distance[v] = 0;

while (!check[v])
{
    check[v] = true;
    temp = g.vertices[v];


    for (int i = 0; i < temp->Edges.size(); i++)
    {
        w = temp->Edges[i]->id;
        weight = temp->Edges[i]->weight;

        if (distance[w] > (distance[v] + weight))
        {
            distance[w] = distance[v] + weight;
            prev[w] = v;
        }
    }

    v = 1;
    dist = MAXINT;

    for (int x = 0; x < g.indices.size(); x++)
    {
        int i = g.indices[x];

        if (!check[i] && dist > distance[i])
        {
            dist = distance[i];
            v = i;
        }
    }
}
}

int main()
{
int startNode, nodeOne, nodeTwo, number;
Graph g;
ifstream myReadFile;
myReadFile.open("P:\\Documents\\New Folder\\Test\\src\\Read.txt");
while (!myReadFile.eof()) 
{
    myReadFile >> nodeOne;
    myReadFile >> nodeTwo;
    myReadFile >> number;
    g.InsertEdge(nodeOne, nodeTwo, number);
}

cout<< "Enter the starting node: ";
cin >> startNode;

Dij(g, startNode);

return 0;
}

I apologize for the annoying formatting =/. It breaks during the last for loop in the dij method. Anyone know what I might be omitting?

Answer 1

Paddy is right!

But as a suggestion, don't use vector<bool>...

See, the C++ gods wanted to create a space saving storage structure to store bools. To make it space efficient, they used bits . Because there is no bits unit in C++: they were forced to use chars. But a char is 8 bits!! The C++ gods came up with a unique solution: they made a special member type: reference to access the bools. You CANNOT access the boolean values any other way. Technically, vector<bool> isn't even a container: due to the fact that the elements are chars, iterators can't be dereferenced.

A much better and cleaner way to store bits is to use the bitset class.

Answer 2

I think you are pre-populating the wrong number of elements into those vectors. You are iterating over g.indices.size(), where it should be g.vertices.size().

The rest of your code knows that indices can be shorter than vertices. You index the check, distance, and prev vectors with values that you pull out of indices. The runtime error you're getting is probably due to iterator bounds-checking in Debug mode.

This should fix your problem:

for (int i = 0; i <= g.vertices.size(); i++)  // <-- notice the change here
{
    check.push_back(false);
    distance.push_back(MAXINT);
    prev.push_back(-1);
}