educative.io

Educative

If I create generic graph data structure using adjacency list representation what are the property of iterators you expect?

That’s a great question. Let’s start by creating a pretty simple graph using the STL list:

class Graph
{
  int vertices;
  list<int> *adj_lists;
  ...
};

“vertices” is just the number of vertices in the graph. Now, a simple method that we might want is “printGraph” that would print the destination vertices from each vertex. We would have to iterate each list in the adj_lists array for this right? Let’s do that.

void Graph::printGraph(){
  for(int i = 0; i < vertices; i++){
    for(std::list<int>::iterator it = adj_lists[i].begin(); it != adj_lists[i].end(); ++it){
      std::cout << *it << " ";
    }
    std::cout << std::endl;
  }
}

As we can see, the iterator works just as it would for other containers like vectors. The “auto” keyword can be used to deduce the type of the iterator in the loop. We can also have a reverse iterator in the form “std::list<int>::reverse_iterator”.

“iterator” is also convertible to “const_iterator” as per your need. I hope this clarifies things.