Home > Blockchain >  how to store pair key in map c
how to store pair key in map c

Time:01-02

I trying to do my homework and there is this BFS question, I want to save the source and target vertices and the index of their input as a map but the thing is that I can't. I keep getting this error for my input(which you can see down in terminal) and I don't know what to do. the strange thing is that when I input 2 1 it's fine without error but for 3 1 it crashes. index in here is like if the input of edges are:

3 1
2 1
3 2

index of 3 1 is 1 and index of 2 1 is 2. [1]: https://i.stack.imgur.com/jZ3Aw.png

this is my whole code:

#include<iostream>
#include <list>
#include <stack>
#include <map>
using namespace std;
class Graph {
int numVertices;
list<int>* adjLists;
map<pair<int, int>, int> indices;
bool* visited;

public:
Graph(int vertices);
void addEdge(int src, int dest, int index);
void BFS(int startVertex,int size);
};

// Create a graph with given vertices,
// and maintain an adjacency list
Graph::Graph(int vertices) {
numVertices = vertices;
adjLists = new list<int>[vertices];
//    indices = new map<pair<int, int>, int >;
}

// Add edges to the graph
void Graph::addEdge(int src, int dest, int index) {
adjLists[src].push_back(dest);
adjLists[dest].push_back(src);
indices.insert(make_pair(make_pair(src, dest),index));
//cout<<index<<" "<<indices.[make_pair(src, dest)]<<endl;
}

// BFS algorithm
void Graph::BFS(int startVertex,int size) {
list<int> output;
int num=0;
visited = new bool[numVertices];
for (int i = 1; i <= numVertices; i  )
    visited[i] = false;

list<int> queue;

visited[startVertex] = true;
queue.push_back(startVertex);

list<int>::iterator i;

while (!queue.empty()) {
    int currVertex = queue.front();
    cout << "Visited " << currVertex << " ";
    queue.pop_front();

    for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end();   i) {
        int adjVertex = *i;
        if (!visited[adjVertex]) {
            visited[adjVertex] = true;
            num  ;
            queue.push_back(adjVertex);
            cout<<indices[make_pair(currVertex, adjVertex)]<<endl;
            //output.push_back(indices[make_pair(currVertex, adjVertex)]);
        }
    }
}
cout<<endl<<num<<endl;
for (auto const& i : output) {
    std::cout << i<<" ";
}
}

int main() {
int m,n;
cin>>n>>m;
Graph g(n);
for (int i=1; i<=m; i  ) {
    int u,v;
    cin>>u>>v;
    g.addEdge(u, v, i);
  }
g.BFS(1, n);
return 0;
}

CodePudding user response:

I can't be certain but I think there's a good chance that you're incorrectly accessing adjLists. If you've only added three vertices, then your constructor will allocate three lists, located at adjLists[0], adjLists[1] and adjLists[2]. Note that indexing starts at 0, and ends at your target size minus 1 (the index represents the offset from the start, so the first element is offset '0' elements from the start). When you attempt to add an edge linking vertex 3 to any other vertex, it will attempt to access adjLists[3], which doesn't exist. This is what causes the bad access. The error is a bit misleading because it seems to happen inside std::list but is actually a result of calling push_back on a null std::list.

CodePudding user response:

Lets discuss your approach first

list<int>* adjLists;

So, its perfectly fine to access adjLists[] which is basically just accessing an array of pointers with an index. However, if it starts with 0-index in cpp.

So when you create a "n" index array you should only access 0...n-1 values of the array. Accessing adjLists[n] will result in undefined behaviour and can can result in a crash.

Solution So either allocate "n 1" in the Graph Constructor or when adding an edge decrement its values by 1 to start from 0 or in your input use 0 based indices

CodePudding user response:

You have defined adjLists

list<int>* adjLists;

but then you write

adjLists[src].push_back(dest);

You cannot directly access a member of a list! I am surprised the compiler passes this.

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position

https://www.cplusplus.com/reference/list/list/

  • Related