What's difference between the two small blocks of c++ code

clinux_rulz · 12-02-2005, 08:09 AM

Hi I have been programming in c/c++ for just about all my life, and then suddenly something completely supprices me, something I had not noticed before.

Can anyone PLEASE (with cheries on top) tell me the difference between the two blocks of code. Or mainly why one works and the other one does not.

Code:

list<Cluster>::iterator i;
for (i = clusters.begin(); i != clusters.end(); ++i) {
    if (i->isTooSmall()) {
        list<Cluster>::iterator j = i; ++j;
        clusters.erase(i);
        i = j;
        continue;
    }
}
#ifndef NDEBUG
for (i = clusters.begin(); i != clusters.end(); ++i) {
    assert(!i->isTooSmall());
}
#endif

Code:

list<Cluster>::iterator i;
for (i = clusters.begin(); i != clusters.end(); ) {
    list<Cluster>::iterator j = i; ++j;
    if (i->isTooSmall()) {
        clusters.erase(i);
    }
    i = j;
}
#ifndef NDEBUG
for (i = clusters.begin(); i != clusters.end(); ++i) {
    assert(!i->isTooSmall());
}
#endif

Both blocks of code should remove all the clusters that are too small, but for the life of me I can not figure out why the bottom code block works, while the top one fails. That is the top one gives the assert error, while the bottom one does not.

So why does the bottom one work and the top one does not. I can not see how the two different block of code can be doing anything different from one another.

PLEASE can any person tell me WHY??? Cause I REALLY can not figure it out. And I have been trying to for 5 days now.

dogpatch · 12-02-2005, 08:28 AM

The first example doesn't make sense to me. i is incremented even before the first test. Then, if the test condition is true, it's incremented again by the i = j assignment. Therefore, some instrances of i will be skipped, and the for loop could even continue past the end condition (i != clusters.end()). I assume this is the code that doesn't work; how could it?

Walk thru the for loop, and watch how the value of i is double-incremented when the condition (i->isTooSmall()) is true.

Quote:

An age of darkness is characterized by widespread and willing ignorance, especially of the darkness.

graemef · 12-02-2005, 08:33 AM

I'm not certain but I don't think that your increment is correct.

In the first code if you do not enter the conditional statement then i is increment by one.

However if you do enter the conditional statement then j is set to the value of i, it is then incremented. After the erase i is set to the value of j, so i now looks at the next value. But then from the loop i is increment again. So in this case I believe i is incremented twice. The continue doesn't achieve any thing because the iterate-expr is evaluated before testing the condition, see continue .

You may want to remove the increment expression into an else and see if that works for you?

graeme.

dmail · 12-02-2005, 09:44 AM

This may well not be the answer, but im just curious.'

Im not fimilar with the std::list implementation as I normally just use my own, what is the underlining structure it uses?

i know that the std::map has a feature that if you delete an item via the iterator then you do not effect any other iteratores in the structure, is it the same for lists?

<edit>
dont know if it is effected but the erase func returns the next iter anyway
iter2 = lst.erase(iter); V
Removes element at iter, returns position of next.

so i would probably write it like

Code:

list<Cluster>::iterator i;
for (i = clusters.begin(); i != clusters.end(); ) 
{
    if (i->isTooSmall()) i = clusters.erase(i);
    else i++;
}

thanhvn · 12-02-2005, 01:24 PM

I think dogpatch and graemef are right: i is double-incremented every time the test condition is true. Thus, if there are two consecutive small clusters, only the first one is removed, hence the failed assertion.

ta0kira · 12-02-2005, 09:04 PM

Although I didn't test them, both appear to be incorrect, and both appear to have at least one flaw other than logic; AFAIK std::list does not guarantee that iterators will stay the same when the list size changes; when you call list::erase, i might not be an iterator to a list element anymore. The i != statement may freeze the program as a result, if you don't get a segfault first (Linux would segfault first, but I think Windows would let it slide and freeze up.)

As far as the first block of code, I agree that you double increment when the element matches. Not only that, YOU INCREMENT when the element is erased, however the erasure results in a yet-to-be-analyzed element moved to i, so going +2 skips 2 elements every time one is removed. The second block skips over 1 element every time one is removed (as shown below.)

In the second block of code, all of the fancy j/i = equates to

Code:

for (i = clusters.begin(); i != clusters.end(); ++i)
if (i->isTooSmall()) clusters.erase(i);

Why? This conversion can be made:

Code:

list<Cluster>::iterator j = i; ++j;

//-->

list<Cluster>::iterator j = i + 1;

And also this can be done as a result:

Code:

i = j;

//-->

i = i + 1;

Giving us a standard loop statement written half-manually. When an element is removed, another takes it's place, therefore i should stay the same for another iteration. If 9 is to be removed, this loop increments to 10 for the next iteration, whereas the element at 10 has moved to 9. If you want this one to work (although I have a feeling this is the one that worked, only because you didn't have 2 consecutive elements that needed removing), get rid of j (as I did above) and make this replacement:

Code:

if (i->isTooSmall()) clusters.erase(i);

//-->

if (i->isTooSmall()) clusters.erase(i--);

It would be much safer to do the following, however, because of the iterator problem when erasing:

Code:

int i = 0;
while (i++ < clusters.size())
if (clusters[i].isTooSmall()) clusters.erase( clusters.begin() + i-- );

ta0kira

clinux_rulz · 12-02-2005, 09:44 PM

I would like to note that in my book "Object-Orientated Programming in C++ (PRENTICE HALL 2nd Ed)" it said that onces an iterator for a list is erased it becomes unusable, the iterator before the current iterator (i) has already been tested and so unlike a std::vector for a std::list i would need to erase "i" and then move "i" to its next element without using "i" and that is where "j" comes in. "j" takes the value of "i" and then moves to the next element. Then went "i" is erased, then "i" beomes "j" and the loop is continued.

The "continue" statement should make the code jump to the top of the loop and do the comparison "i != clusters.end" without incrementing "i".

I know that the second block of code works because I tested it very carefully. But the first block fails.

Could it be that I miss-interpreted the meaning of "continue"?

clinux_rulz · 12-02-2005, 09:57 PM

/**
* @brief Remove element at given position.
* @param position Iterator pointing to element to be erased.
* @return An iterator pointing to the next element (or end()).
*
* This function will erase the element at the given position and thus
* shorten the %list by one.
*
* Due to the nature of a %list this operation can be done in constant
* time, and only invalidates iterators/references to the element being
* removed.
* The user is also cautioned that
* this function only erases the element, and that if the element is itself * a pointer, the pointed-to memory is not touched in any way. Managing
* the pointer is the user's responsibilty.
*/
iterator
erase(iterator __position);

-------------------------------------------------------------------------------------------------------------

I don't know why I did not notice it before. But the erase() function returns an iterator to the next element.

Thanks dmail, the parts of my code that deals with this should be alot simplier from now on.

The following block of code works fine.

Code:

list<Cluster>::iterator i;
for (i = cluster.begin(); i != clusters.end(); ++i) {
    if (i->isTooSmall()) {
        i = clusters.erase(i);
        continue;
    }
}

But I don't know why the following fails.

Code:

#include <algorithm>
#include <iostream>
using namespace std;
 . . .
class IsTooSmall {
    public:
        bool operator()(Cluster const& c) {
            return c.isTooSmall();
        }
};
 . . .
remove_if(clusters.begin(), clusters.end(), IsTooSmall());
#ifndef NDEBUG
for (i = clusters.begin(); i != clusters.end(); ++i) {
    assert(!i->isTooSmall());
}
#endif
 . . .

While the following code works

Code:

#include <algorithm>
#include <iostream>
using namespace std;
 . . .
class IsTooSmall {
    public:
        bool operator()(Cluster const& c) {
            return c.isTooSmall();
        }
};
 . . .
remove_if(clusters.begin(), clusters.end(), IsTooSmall());
remove_if(clusters.rbegin(), clusters.rend(), IsTooSmall());
#ifndef NDEBUG
for (i = clusters.begin(); i != clusters.end(); ++i) {
    assert(!i->isTooSmall());
}
#endif
 . . .

graemef · 12-03-2005, 04:30 PM

Remember that in a for loop the continue will still increment the loop counter. So you want to change your code as follows:

Code:

list<Cluster>::iterator i;
for (i = cluster.begin(); i != clusters.end();) {
    if (i->isTooSmall()) {
        i = clusters.erase(i);
    }
    else
       i++
}

The original code doesn't remove adjacent clusters.

Changing the code above may fix you other problem.

graeme.

clinux_rulz · 12-04-2005, 08:39 AM

Thank you graemef,

I always thought that the "continue" statement jumped to the top of the for loop and retested the condition, but I looked it up and I was wrong, the "continue" statment actually jumps to the very bottom of the for loop but still inside it.

Thank You very much for clearing this up for me. If you had not had cleared this up for me now, then I would still be making that same mistake in the future, and still wondering why it wont work. Thank You!!!