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:

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...

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;
      }
    }

Kurt

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.

[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 McKenzie

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?

[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 McKenzie

Even 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 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