CODEWITHSUNDEEP
c++c++11iteratorauto
mcdito13
mcdito13

Reputation: 321

C++ using auto vs a defined iterator

Could anyone explain the differences in the for loops in my code? I understand that an iterator is a pointer to some data, and when I type "*iter" I'm accessing the value that this pointer points to (an int). But I don't understand why auto doesn't work the same way here. Why don't I need to dereference vertex in the other for loop?

#include <iostream>
#include <list>
#include <queue>

class Graph {
    public:
        Graph(int num_v): num_vertices(num_v), adj_list(new std::list<int>[num_v]) {}

        void add_edge(int u, int v) { adj_list[u].push_back(v); }

        void bfs_traversal(int start) {
            bool* visited = new bool[num_vertices];
            for (int i = 0; i < num_vertices; i++)
                visited[i] = false;
            std::queue<int> q;
            visited[start] = true;
            q.push(start);
            //std::list<int>::iterator iter;
            while(! q.empty()) {
                int node = q.front();
                std::cout << node << " ";
                q.pop();

                /*
                for (iter = adj_list[node].begin(); iter != adj_list[node].end(); ++iter) {
                    if (! visited[*iter]) {
                        visited[*iter] = true;
                        q.push(*iter);
                    }
                */

                for (auto vertex : adj_list[node]) {
                    if (! visited[vertex]) {
                        visited[vertex] = true;
                        q.push(vertex);
                    }
                }

            }
        }

    private:
        int num_vertices;
        std::list<int>* adj_list;
};

int main() 
{
    Graph graph(4);
    graph.add_edge(0,1);
    graph.add_edge(0,2);
    graph.add_edge(1,2);
    graph.add_edge(2,0);
    graph.add_edge(2,3);
    graph.add_edge(3,3);

    std::cout << "breadth first traversal starting from vertex 2\n";

    graph.bfs_traversal(2);

    return 0;
}

compile with: g++ -std=c++11 source: https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

Upvotes: 1

Views: 4307

Answers (2)

You
You

Reputation: 23794

Because the range-based for-loop does it for you. In this specific case (assuming ), it's required to produce code equivalent to the following (variable names are for exposition only):

{
  auto && __range = adj_list[node]; 
  for (auto __begin = __range.begin(), __end = __range.end(); 
       __begin != __end; ++__begin) { 
    auto vertex = *__begin; 
    // ... 
  } 
}

Note line 5, where a copy is made after dereferencing the iterator.

As @Bathsheba points out, it's likely that you want const auto& instead of just auto.

Upvotes: 5

Bathsheba
Bathsheba

Reputation: 234785

The uncommented version is using the range-based for loop.

Note that there is a subtle difference; unlike the iterator version, vertex is a value copy of the container element. It's for this reason that 

for (const auto& vertex : adj_list[node]) {

is preferred when working with larger containee types, or even auto&& vertex.

Under the hood, the range based notation uses iterators. It's important to remember therefore that the C++03 rules for iterator invalidation still apply.

Upvotes: 6

Related Questions