CODEWITHSUNDEEP
c++for-loop
Kyle Calica-St
Kyle Calica-St

Reputation: 2963

Shouldn't there be an error in this for loop?

I am reading my data structures book and see some code that doesn't sit well with me. I think my idea of for loops is wrong. Can someone help? 

void percolateDown(int hole){

    int child;
    Comparable tmp = array[hole];
     // my problem is that child is not initialized to a value until inside for loop how is hole = child possible! 
    for(; hole * 2 <= currentSize; hole = child){
          child = hole * 2;  
         //code that does percolate up
    }

    array[hole] = tmp; 
}

This code is right I only removed the unnecessary code inside. You probably guessed it but it is a method for percolating down in a heap.

My problem is that child is not given a value until inside the for loop so how is it the for loop can state hole = child in it?

My assumption is that everything in the for loop is ran before or at the first iteration.

Upvotes: 0

Views: 79

Answers (4)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145429

C++11 §6.5.3/1 in [stmt.for]:

” The for statement

        for ( for-init-statement conditionopt; expressionopt ) statement

is equivalent to

        {
        for-init-statement
        while ( condition ) {
                statement
                expression ;
                }
        }

except that names declared in the for-init-statement are in the same declarative-region as those declared in the condition, and except that a continue in statement (not enclosed in another iteration statement) will execute expression before re-evaluating condition.

I.e., the hole = child update is not executed until after the for loop body.

And yes, it's a pain-in-the-ass formatting this in Stack Overflow markdown. Evidently it was so also for the editor of the standard (I think that's written in LaTeX or something like that), because at the end statement, expression and condition lacks italics. I added that in the quote.

Upvotes: 2

Javier
Javier

Reputation: 62651

Any for loop of the form:

for (A; B; C) {
    ....
}

is equivalent of a while loop of the form:

{
    A;
    while (B) {
        ....
        C;
    };
}

so, you can see the body of the loop is executed before the 'increment' part (C in this example).

Upvotes: -3

Jonathan Leffler
Jonathan Leffler

Reputation: 754920

The hole = child assignment is executed after the body of the loop is executed, so by the time it is executed, child has been assigned a value.

To a first approximation, the loop is equivalent to:

int child;
while (hole * 2 <= currentSize)
{
    child = hole * 2;
    hole = child;
}

(It's a first approximation because the behaviour of break and continue are not capturable with the transliteration shown — but your code doesn't have those anyway.)

You could avoid child by simply using hole *= 2; as the body of the loop.

Upvotes: 3

ApplePie
ApplePie

Reputation: 8942

The last part of a for loop is only executed after the loop has done its first iteration. Thus, it first sets child and then assigns hole to child.

Upvotes: 3

Related Questions