trouble understanding list.begin() | list.end() | list::iterator i

Question

void Graph::max_path(){
    
    for(int i=0; i <N; i++){
        cost[i]=0; cam_max[i]=999;
    }
     // Percorre todos os vertices adjacentes do vertice
    int max = 0;
  list<int>::iterator i; 
  for (int a = 0; a < N ; a++){
    int v = ordely[a];
        for (i = adj[v].begin(); i != adj[v].end(); ++i){
          int viz = *i;
          if (cost[viz]<cost[v]+1){
                cost[viz] = cost[v]+1;
                if(cost[viz]>max) max = cost[viz];
        }
      }
    }
  cout << "\nCusto maximo " << max;
}

I need to convert this C++ program to a python program... However, I'm struggling to understand what this adj[v].begin() inside the for loop means. Can anyone explain it to me, please?

`.begin()` and `.end()` are member functions on STL containers (in your case a list container). As for what they *are*, they are pointers to the beginning and the end + 1 of your list, respectively. The `list::iterator` is an abstraction for performing pointer arithmetic given to you by the STL. Does that answer your question? — Gianni Crivello, Nov 19 '22 at 15:20
@GianniCrivello in some way, it does. But what is that [v] index before .begin() ? I've never seen this — BLNFR, Nov 19 '22 at 15:37
@BLNFR despite the limited context of how `adj` is defined, It seems that you are indexing into `adj` and accessing the `.begin()` member function of the indexed element. Think a `list` of `list`. — Gianni Crivello, Nov 19 '22 at 15:43
@GianniCrivello its defined as list *adj, then in the constructor adj = new list[V]. But it seems to be a list of list really. — BLNFR, Nov 19 '22 at 15:56
@BLNFR what is V? Your question lacks context and needs to at least provide a [minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example) for any of us to help you. Also, I would highly recommend [how to diagnose your problem using a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Gianni Crivello, Nov 19 '22 at 16:00

score 0 · Accepted Answer · answered Nov 19 '22 at 16:02

begin and end are iterators (specfically, pointers), which are used to iterate over a container.

You could imagine begin as 0 and end as the size of an array. So it is like for (i = 0; i < size; ++i).

However, the thing about pointers is that they're addresses, so in C++, i < end (where i started as begin) is more like 0xF550 < 0xF556 (example) which has the same effect of iterating 6 times assuming i increases each iteration.

In fact, that's actually how for-each loops work behind the scenes in many languages.
In python, just use a normal for-loop.

I don't know much about python or your Graph class but I guess this could get you started:

def max_path(self) :
for i in range(N) :
    self.cost[i] = 0
    self.cam_max[i] = 999
    max = 0
    for a in range(N) :
        v = self.ordely[a]
        for i in self.adj[v] :
            viz = i
            if self.cost[viz] < self.cost[v] + 1 :
                self.cost[viz] = self.cost[v] + 1
                if self.cost[viz] > max :
                    max = self.cost[viz]
                    print("\nCusto maximo ", max)

Notice how iterators weren't needed in the python version cause you used a normal for-loop.

By the way, in C++, you could use for/for-each too, the code you posted is unnecessarily complicated and unoptimized. For example, the first 2 loops in your code could be merged into 1 loop cause they both had the exact same range thus I optimized them into 1.

It's not possible for `std::list` to use pointers as iterators. Only a contiguous container *could* use them, such as `vector` or `array`. — HolyBlackCat, Nov 19 '22 at 16:11
@HolyBlackCat Oh I totally forgot that the standard type `list` exists, I thought it was some kind of custom library that behaved similarly to `vector` (contiguous in memory) which is why I talked only about iterators being addresses in this case. — Beyondo, Nov 19 '22 at 16:22

trouble understanding list.begin() | list.end() | list::iterator i

1 Answers1