Setting an iterator to "end"

[Mybowlcut]

Hey guys.

I've got this code where I set an iterator to point to the end of a vector so that a loop will end. I debugged it and it sets the iterator to the end because it points to 0xcdcdcdcd, but the for loop check doesn't seem to notice that the iterator points to the end because it tries to increment it and I get an error:
http://i50.photobucket.com/albums/f344/mybowlcut/untitled-33.png
void Tile_Palette::Update(const SDL_Event* event_)
{
if(!event_) return;

if(event_->type == SDL_MOUSEBUTTONUP)
{
const SDL_Rect mouse = {event_->motion.x, event_->motion.y};
ptile_it it = camera_tiles.begin();
for(; it != camera_tiles.end(); ++it)
{
if(SDL_Tools::mouse_over_rect(mouse, (*it)->Get_Position()))
{ // Changed tile pen.
tile_pen = *(*it);
it = camera_tiles.end();
}
}
}
}

I can't see anything wrong with my code, but maybe someone else can... :thumb:

Oh, and camera_tiles looks like this:std::vector<XTile*> camera_tiles;
Cheers.

[ZuK]

I do nor see the problem with your code but you do not have to set the iterator to end, just break the loop
for(; it != camera_tiles.end(); ++it)
{
if(SDL_Tools::mouse_over_rect(mouse, (*it)->Get_Position()))
{ // Changed tile pen.
tile_pen = *(*it);
break;
}
}
Kurt

[Mybowlcut]

I do nor see the problem with your code but you do not have to set the iterator to end, just break the loop
for(; it != camera_tiles.end(); ++it)
{
if(SDL_Tools::mouse_over_rect(mouse, (*it)->Get_Position()))
{ // Changed tile pen.
tile_pen = *(*it);
break;
}
}
KurtGenerally I do use break, but sometimes I try and make use of the loop condition. If I can't resolve this then I'll just use break but I'm interested to know why this is happening.

[potatoCode]

Hello mybowlcut,

change your logical operator to
for(; it < camera_tiles.end(); ++it)

i think this should work without breaking the loop

[Paul McKenzie]

Hello mybowlcut,

change your logical operator to
for(; it < camera_tiles.end(); ++it)No.

The correction is this:
for(; it != camera_tiles.end(); ++it)
The end() of a sequence can be any value that the implementor of the container class has created. The only guarantee is that when you increment past the end of the valid items in a container, the iterator is equal to end().

The real correction to MyBowlCut's code is to not mess around with (in other words change) the controlling loop iterator in the middle of the loop. Any code that I see doing that is always susceptible to some sort of bug.

Regards,

Pauil McKenzie

[Paul McKenzie]

Generally I do use break, but sometimes I try and make use of the loop condition. If I can't resolve this then I'll just use break but I'm interested to know why this is happening.Simple explanation.

You set the iterator to the end, then the for loop increments the iterator you set (the ++it in the for loop). One past the end(), and boom, your dead.

As stated to potatoCode, if you have a for loop(), and your controlling iterator is part and parcel of the for loop itself, do not change the value of the controlling iterator within the loop. Any code that does that is by its very nature suspicious. This is regardless of whether it is an iterator or a simple int variable controlling the loop:

for (int i = 0; i < some_condition; ++i)
{
///...
i = some_value;
//...
}

If it were up to me in a code review, I would reject any code that does this.

The proper loop construct if you want to change things around like this is a while loop, or at least a for loop that has some sort of terminating condition:

bool okToContinue = true;
for (int i = 0; i < somevalue && okToContinue; ++i)
{
// if ( whatever )
{
okToContinue = false;
}
}

Then the loop terminates automatically since the okToContine is false.

Regards,

Paul McKenzie

[Mybowlcut]

Simple explanation.

You set the iterator to the end, then the for loop increments the iterator you set (the ++it in the for loop). One past the end(), and boom, your dead.

As stated to potatoCode, if you have a for loop(), and your controlling iterator is part and parcel of the for loop itself, do not change the value of the controlling iterator within the loop. Any code that does that is by its very nature suspicious. This is regardless of whether it is an iterator or a simple int variable controlling the loop:

for (int i = 0; i < some_condition; ++i)
{
///...
i = some_value;
//...
}

If it were up to me in a code review, I would reject any code that does this.

The proper loop construct if you want to change things around like this is a while loop, or at least a for loop that has some sort of terminating condition:

bool okToContinue = true;
for (int i = 0; i < somevalue && okToContinue; ++i)
{
// if ( whatever )
{
okToContinue = false;
}
}

Then the loop terminates automatically since the okToContine is false.

Regards,

Paul McKenzieAhh yeah, forgot the order of operations in the loop. Cheers Paul.

One question though, in your code example, what happens if there is code after the if statement that shouldn't be executed if okToContinue is false? In situations like that, would it be better to use a break?

[Hermit]

If it were up to me in a code review, I would reject any code that does this.

The proper loop construct if you want to change things around like this is a while loop, or at least a for loop that has some sort of terminating condition:

bool okToContinue = true;
for (int i = 0; i < somevalue && okToContinue; ++i)
{
// if ( whatever )
{
okToContinue = false;
}
}

Then the loop terminates automatically since the okToContine is false.

Regards,

Paul McKenzieEven this might raise some eyebrows. I prefer Kurt's suggestion as long as there is no practical reason not to use break.

Another option if you're so inclined is to use std::find_if, with a predicate along the lines of:
class Mouse_Over_Tile_Pred
{
public:
Mouse_Over_Tile_Pred(const SDL_Rect & mouse) :
m_mouse(mouse)
{
}
bool operator()(Tile_Pen * /* ? */ tile_pen) const
{
return SDL_Tools::mouse_over_rect(m_mouse, tile_pen->Get_Position());
}
private:
const STL_Rect m_mouse;
};
But that's a bit of overkill for such a simple predicate.

[Speedo]

The real correction to MyBowlCut's code is to not mess around with (in other words change) the controlling loop iterator in the middle of the loop. Any code that I see doing that is always susceptible to some sort of bug.

How then do you deal with a situation where you need to manually control the iterator? Take for example deleting items from a STL list:


list<Foo>::iterator toDel;
for (list<Foo>::iterator it = myList.begin( ); i != myList.end( );)
{
if (it->NeedsDeletion( ))
{
toDel = it;
it++;
myList.erase(toDel);
}
else
{
it->SomeMethod( );
it++;
}
}

[ZuK]

erase returns an iterator to the first element after the erase(d) one(s).
So it could be done like that
for (list<Foo>::iterator it = myList.begin( ); i != myList.end( ) ) {
if (it->NeedsDeletion( )) {
it = myList.erase(it);
}
else

kurt

[Speedo]

Does it? I'd completely forgotten.

Edit: According to this (http://www.cplusplus.com/reference/stl/list/erase.html) it actually returns an iterator to the element after the one erased... so you still need to increment manually, or else you'll skip elements when you erase.

[Paul McKenzie]

How then do you deal with a situation where you need to manually control the iterator? Take for example deleting items from a STL list:That is what remove_if() is for. Usage of the remove_if() algorithm makes writing loops as you've written a moot point.

#include <list>
#include <algorithm>

using namespace std;

class Widget
{
public:
bool NeedsToBeRemoved() const;
};

bool RemoveMe(const Widget& w)
{
return w.NeedsToBeRemoved();
}

int main()
{
list<Widget> WidgetList;
WidgetList.erase(remove_if(WidgetList.begin(), WidgetList.end(),
RemoveMe ), WidgetList.end());
}

Questions like "does the function return the next iterator?" or "do I increment it now?" or other questions like that are now no longer an issue.

Edit:

You also have algorithms such as partition() that moves "bad" elements to the end of the sequence. Then you apply erase() to those elements.

Regards,

Paul McKenzie

[Graham]

Ahh yeah, forgot the order of operations in the loop. Cheers Paul.

One question though, in your code example, what happens if there is code after the if statement that shouldn't be executed if okToContinue is false? In situations like that, would it be better to use a break?
break and continue are only marginally less evil than goto. What's wrong with if (!OkToContinue) { ... }? Mind you, in situations like that, I'd start to think about refactoring the loop.

[laserlight]

That is what remove_if() is for. Usage of the remove_if() algorithm makes writing loops as you've written a moot point.
A little off topic here, but do you recommend simply writing the RemoveMe function as in your example, or would you also recommend using std::mem_fun_ref(&Widget::NeedsToBeRemoved) instead?

[Paul McKenzie]

A little off topic here, but do you recommend simply writing the RemoveMe function as in your example, or would you also recommend using std::mem_fun_ref(&Widget::NeedsToBeRemoved) instead?Either way is OK.

The bottom line is that using the algorithms is better than writing loops that I've seen too often than not cause all kinds of problems. Even a good coder could botch writing a loop that erases an item but then doesn't increment the iterator incorrectly, or in the wrong place, or whatever. Usage of the proper algorithm removes these problems.

Regards,

Paul McKenzie

[Speedo]

The bottom line is that using the algorithms is better than writing loops that I've seen too often than not cause all kinds of problems. Even a good coder could botch writing a loop that erases an item but then doesn't increment the iterator incorrectly, or in the wrong place, or whatever. Usage of the proper algorithm removes these problems.

I would say that's true for basic usage, but considering how simple it is to increment correctly, there are so many places where it seems utterly foolish to walk the container twice. After all, the definition of list::remove_if (in MSVC) is merely:


template<class _Pr1>
void remove_if(_Pr1 _Pred)
{ // erase each element satisfying _Pr1
iterator _Last = end();
for (iterator _First = begin(); _First != _Last; )
if (_Pred(*_First))
_First = erase(_First);
else
++_First;
}

[Paul McKenzie]

I would say that's true for basic usage,No, for most usage, and I would state for *all* usage involving sequence containers.

Scott Meyer's "Effective STL" lays out the argument for using algorithms over hand-coded loops quite well.but considering how simple it is to increment correctly, there are so many places where it seems utterly foolish to walk the container twice. After all, the definition of list::remove_if (in MSVC) is merely:My point is that it doesn't matter what the implementation happens to do.

There are other reasons why algorithms are used. The other reasons are (also taken from Scott Meyer's Item 43 in his book) efficiency, maintainability, and correctness.

50 different programmers will write that very same loop 50 different ways. Some of those ways can have bugs, others will increment the iterator differently, etc. This leads to pieces of code written differently that is supposed to accomplish the same thing. Then the maintenance programmer who originally didn't write that code has to figure out exactly what that loop does and if it's doing it correctly. This means more time figuring out what iterator gets invalidated where, etc.

On the other hand, there is only one way to use remove_if() (excepting the way to specify the predicate), and that one way removes all doubts as to what it's supposed to do. The only thing the coder has to check for is if the "true" return value is being used for items that are to be removed. If something needs to be changed (i.e., the correct items are not removed), then the programmer just fixes the predicate. The code to remove_if() remains the same.

Regards,

Paul McKenzie

[Mybowlcut]

break and continue are only marginally less evil than goto. What's wrong with if (!OkToContinue) { ... }? Mind you, in situations like that, I'd start to think about refactoring the loop.Can you please elaborate? I'm starting to get confused about what your opinion of a well structured loop is...

[Paul McKenzie]

Even this might raise some eyebrows.IMO, anything other than goto is preferable than changing the loop control variable within the loop.

Taking the example of using erase(), I think one of the bad usages of erase() is exactly as it is being done in a lot of code. Yes, erase() returns an iterator where you can adjust the loop control variable, and you can find a lot of sample code that shows this. But honestly, this breaks all the design principles that I've been taught with respect to for() loops (regardless of the language being used).

That principle is that the control variable should be controlled only by the for loop "auto-increment" mechanism, and not altered within the body of the loop. Too many bugs I've seen is precisely because of this practice of fooling around with the control loop variable, not only in C++, but various other languages where there is a looping mechanism that has a control variable-like syntax.

MyBowlcut's loop could be done using either break, or another bool that controls whether looping should continue, or using find_if() using a predicate. These to me are all preferable than changing control variables within loops. Heck, that is exactly the reason why this thread started -- a bug occurred because of this practice.

Regards,

Paul McKenzie

[JohnW@Wessex]

break and continue are only marginally less evil than goto.Indeed! I put a paragraph in our coding standards saying exactly the same thing.