LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 12-02-2005, 08:09 AM   #1
clinux_rulz
Member
 
Registered: Nov 2005
Distribution: Gentoo
Posts: 51

Rep: Reputation: 16
What's difference between the two small blocks of c++ code


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.
 
Old 12-02-2005, 08:28 AM   #2
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 164
Blog Entries: 1

Rep: Reputation: 19
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.

Last edited by dogpatch; 12-02-2005 at 08:34 AM.
 
Old 12-02-2005, 08:33 AM   #3
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
i++ problem - maybe?

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.
 
Old 12-02-2005, 09:44 AM   #4
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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++;
}

Last edited by dmail; 12-02-2005 at 10:02 AM.
 
Old 12-02-2005, 01:24 PM   #5
thanhvn
Member
 
Registered: Mar 2005
Location: CA
Distribution: RHEL3, FC4
Posts: 46

Rep: Reputation: 15
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.

Last edited by thanhvn; 12-02-2005 at 01:25 PM.
 
Old 12-02-2005, 09:04 PM   #6
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
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

Last edited by ta0kira; 12-02-2005 at 09:25 PM.
 
Old 12-02-2005, 09:44 PM   #7
clinux_rulz
Member
 
Registered: Nov 2005
Distribution: Gentoo
Posts: 51

Original Poster
Rep: Reputation: 16
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"?
 
Old 12-02-2005, 09:57 PM   #8
clinux_rulz
Member
 
Registered: Nov 2005
Distribution: Gentoo
Posts: 51

Original Poster
Rep: Reputation: 16
/**
* @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
 . . .

Last edited by clinux_rulz; 12-02-2005 at 10:03 PM.
 
Old 12-03-2005, 04:30 PM   #9
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
continue is not what you want

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.
 
Old 12-04-2005, 08:39 AM   #10
clinux_rulz
Member
 
Registered: Nov 2005
Distribution: Gentoo
Posts: 51

Original Poster
Rep: Reputation: 16
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!!!
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
small syntax problem with C code (implemented in Code Composer Studio) illiniguy3043 Programming 6 01-07-2008 02:14 AM
Small difference when compiled with gcc and g++ drigz Programming 5 06-15-2006 04:09 PM
Smilies in Code Blocks Matir LQ Suggestions & Feedback 6 08-19-2005 04:49 AM
what's wrong with this small code ? indian Programming 2 08-18-2004 11:12 AM
graphic smilies in [CODE] blocks? fd0u1440 LQ Suggestions & Feedback 1 07-01-2004 11:01 PM


All times are GMT -5. The time now is 03:42 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration