This forum is a read-only archive of the Gammon Software forum (2000–2026). No new posts can be made. Search the archive.

list for loops

Posted by Greven on Fri 18 Feb 2005 01:31 AM — 26 posts, 113,242 views.

Greven Canada #0
In our conversion to C++ and using STL, we have been able to do alot of good things. However, there is a crash that occurs sometimes in stl_lists.h. The BT is virtually unusable since it ends there. It seems to happen whenever we use this macro
#define FOR_EACH_LIST(type,list,VARIABLE) for( type::iterator i_ ## VARIABLE = (list).begin(); \
        i_ ## VARIABLE != (list).end() && ((VARIABLE) = (*i_ ## VARIABLE )); \
        ++i_ ## VARIABLE)
Doesn't mean it is the macro nessecarily, but we use this to traverse any lists that we have. If anyone has any suggestions or can see something inately wrong with that macro it would be much appreciated.
David Haley USA #1
Well, my first remark is that you seem to be going through an awful lot of trouble to iterate over lists... why not just type it out? :P

The main thing is that with STL iterators, you are not supposed to use ++it - I believe that is non-standard and the standard way of doing it is it++.

What kind of container are you iterating over?

Why not turn on full debug and have it expand the macro, so that you can have a more useful debug trace?

Or, can you run it through GDB, and set a breakpoint just before running the macro?
Greven Canada #2
Meh, its just to short hand it, works everywhere else.

So I switched it to it++ rather than ++it, made no difference. I'm going through a list of objects defined as BODY_DATA(celestial bodies), a custom class. I've expanded it with -gdb and -g3, but it still won't expand the macro, maybe I'm missing something. However, the macro itself works in 45 other places and never has an issue. Infact, this specific piece of code is called repeatedly, and only fails in one circumstance.

Here is my gdb bt info
Program received signal SIGSEGV, Segmentation fault.
0x0808a8df in std::list<BODY_DATA*, std::allocator<BODY_DATA*> >::end (this=0x28) at stl_list.h:583
583         end() { return _M_node; }
(gdb) bt
#0  0x0808a8df in std::list<BODY_DATA*, std::allocator<BODY_DATA*> >::end (this=0x28) at stl_list.h:583
#1  0x081de310 in move_ships () at space.c:312
#2  0x0822fdf6 in update_handler () at update.c:3158
#3  0x0810d5d7 in game_loop () at comm.c:865
#4  0x0810c5f0 in main (argc=2, argv=0xbffffd04) at comm.c:353
(gdb) frame 0
#0  0x0808a8df in std::list<BODY_DATA*, std::allocator<BODY_DATA*> >::end (this=0x28) at stl_list.h:583
583         end() { return _M_node; }
(gdb) print _M_node
Cannot access memory at address 0x28
The corresponding valgrind info
==15987== Invalid read of size 4
==15987==    at 0x81716B6: move_ships() (stl_list.h:155)
==15987==    by 0x81AF84E: update_handler() (update.c:3158)
==15987==    by 0x80D06E1: game_loop() (comm.c:865)
==15987==    by 0x80CFC3B: main (comm.c:353)
==15987==  Address 0x28 is not stack'd, malloc'd or (recently) free'd
==15987== TRANSLATE: 0x1BA6EEA0 redirected to 0x1B8FEC0F
And the code itself
line 312--->    FOR_EACH_LIST(BODY_LIST, ship->starsystem->bodies, body)
                {
                        int       distance = 0;

                        if (ship->currspeed <= 0)
                                continue;
                        distance = body->distance(ship);

                        if ((distance < body->gravity() / 10)
                            && body->type() == STAR_BODY && distance > 0)
                        {
                                echo_to_cockpit(AT_BLOOD + AT_BLINK, ship,
                                                "You fly directly into the sun.");
                                snprintf(buf, MSL,
                                         "%s flys directly into %s!",
                                         ship->name, body->name());
                                echo_to_system(AT_ORANGE, ship, buf, NULL);
                                destroy_ship(ship, NULL);
                                continue;
                        }

                        if (distance < body->gravity()
                            && (body->type() == PLANET_BODY
                                || body->type() == MOON_BODY))
                        {
                                snprintf(buf, MSL, "You begin orbitting %s.",
                                         body->name());
                                echo_to_cockpit(AT_YELLOW, ship, buf);
                                snprintf(buf, MSL, "%s begins orbiting %s.",
                                         ship->name, body->name());
                                echo_to_system(AT_ORANGE, ship, buf, NULL);
                                ship->currspeed = 0;
                                continue;
                        }
                }
It only happens after the ship has gone through the section with destroy_ship, so I'm assuming something in there is killing ships, but I can make repeated calls to it outside of this loop with no problems at all at, no leaks with it anywhere.

Maybe someone can see something I can't, cause this is really bugging me.
Amended on Fri 18 Feb 2005 06:33 AM by Greven
Greven Canada #3
NEEEEEEEEEEEEEEEEEEEEEEVER mind. After much bug placement and return statements and continious passing down, I determined that it was a fundamental problem with the code, I changed the continue to break, works great. Basically, after destroying the ship, the ships is pulled from the starsystem, so we no longer need to check if its going to be destroyed, and ship->starsystem->bodies, while still valid, is no longer applicable to the ship as ship->starsystem is now not applicable. Thanks for the help.
David Haley USA #4
Here's another thing that you should keep in mind. For many containers, if you remove an element, then any iterators on that element become invalid. So, if in any way your loop affects the list it's looping over, you're in for trouble because you might invalidate your iterators.

For instance, IIRC, this won't work:
list<string> strList;
// fill up strList
list<string>::iterator it;
for ( it = strList.begin(); it != strList.end(); it++ )
{
    strList.erase(it);
}

(I might have gotten a few details wrong.)
Basically, you're supposed to avoid removing things from a container that you are iterating over.

Your break command will fix this problem, by simply stopping the iteration - so you won't try to advance the iterator after you have removed its element from the container.
Greven Canada #5
See, thats what confused me, it never affected the body list at all, infact it had nothing to do with it. The list itself was valid, as we could print the entirety of it in gdb. Very confusing.

Heh, still, I see your point. Thats what .clear() is for :)
Amended on Fri 18 Feb 2005 07:06 AM by Greven
David Haley USA #6
As I understand it, it's not an issue of the list being valid (the list is always valid, well, almost :P), it's an issue of the iterator being valid. I know for a fact that when I've wanted to iterate over a list removing things, I've had to make a separate list of what I wanted to remove, and then iterate over the second list, removing elements from the first list. Or something like that.

I know for sure, though, that it's really a bad idea to keep iterators lying around (e.g. in a struct somewhere) because they get invalidated at most operations.

I have an excellent STL book lying around here somewhere; once I get some more time I'll go looking through it and find the relevant section again. But as you can see from my failure to deliver the hashed-strings on time, I've been a wee bit busy. :P
Samson USA #7
So if I do something like this:


   for( ich = charlist.begin(); ich != charlist.end(); )
   {
      ch = (*ich);
      ich++;

      if( ch->char_died() )
         continue;


And somewhere after the char_died check I remove one from the list, will my iterators still be jacked or are they ok because I incremented before removal?
David Haley USA #8
I'm not 100% sure about this, but if you remove the element that the iterator refers to, you are in trouble. If you remove the one that the iterator used to point to (before you advanced it) you should be fine. In short, I think (but am not 100% sure) that for linked lists, as long as your iterator refers to something actually in the list, you should be fine.

At least, for linked lists you will be, I think. With vectors, it's another story, as vector iterators are just array indices in disguise.

As a general note, all this confusion is why I try to avoid removing things from lists as I iterate over them. :-) Generally you don't *need* to remove as you iterate and it's a lot less dangerous as you don't have to remember particulars of each container's iterator safety under container operations.
Raz #9
Quote:
#define FOR_EACH_LIST(type,list,VARIABLE) for( type::iterator i_ ## VARIABLE = (list).begin(); \
i_ ## VARIABLE != (list).end() && ((VARIABLE) = (*i_ ## VARIABLE )); \
++i_ ## VARIABLE)


Ugly. Anyway, you keep reassigning the VARIABLE part each pass. Was this what you intended? Take a closer look:

i_ ## VARIABLE != (list).end() && ((VARIABLE) = (*i_ ## VARIABLE

You reassign VARIABLE each pass. Was this intended? You are missing the third part of the for(;;) statement as well.

Quote:
If anyone has any suggestions or can see something inately wrong with that macro it would be much appreciated.


Yes. Either write it by hand or use algorithms such as std::for_each. Marcos, such as yours, are the wrong solution for trying to save time typing.
Raz #10
Quote:
So if I do something like this:


*snip*

Yes. std::list::erase only invalides the iterators that it erased.
David Haley USA #11
Quote:
You reassign VARIABLE each pass. Was this intended?
Most likely, yes, because VARIABLE is what he's using as the value of the iterator. So it makes sense to assign the value of the iterator to VARIABLE at every pass. He's using it as shorthand for declaring the variable inside the loop, and assigning it himself.
Quote:
You are missing the third part of the for(;;) statement as well.
No, he's not. Look:
#define FOR_EACH_LIST(type,list,VARIABLE)
  for( 
    // first part
    type::iterator i_ ## VARIABLE = (list).begin(); \
    // second part
        i_ ## VARIABLE != (list).end() && ((VARIABLE) = (*i_ ## VARIABLE )); \
    // third part
        ++i_ ## VARIABLE
)

Quote:
Either write it by hand or use algorithms such as std::for_each
Using for_each is major a pain in the behind because every time you use it, you need to create an external function - and if you want to use local variables, you have to make a functor, and pass it all kinds of variables in the constructor - basically, you have an awful lot of overhead. IMHO for_each is not a good solution for specific applications; it's a very good solution if you want to provide a generic way of mapping over the elements of a container.

My recommendation would be to simply write it out by hand, since the macro is complex enough to type that it's really not saving you very much.
Greven Canada #12
We're reassigning the variable each pass through intentionally. Consider the standard SMAUG double linked list usage of a for loop
for ( ch = first_char ; ch ; ch = ch->next)
This reassigns the variable each pass through, as does mine. Writing out as the macro is really meant as an easier to use for_each, since encountering all the problems that Ksilyan outlined above while keeping the code looking clean.

To remove something from a list, I generally won't iterate over it, I'll use
this->_areas.erase(find(this->_areas.begin(), this->_areas.end(), area));
Not asuming this is the right way to do it, but haven't encountered issues so far.
Amended on Sat 19 Feb 2005 01:19 AM by Greven
David Haley USA #13
Quote:
this->_areas.erase(find(this->_areas.begin(), this->_areas.end(), area));

I think that you can just use the erase method on the value not the iterator, which avoids the somewhat clunky syntax of calling find inside the erase.
Greven Canada #14
I think you can do that for maps, but I tried to compile this->_areas.erase(area) and it gave me a conversion error. If there's a syntax you have to make this simpler, I would certainly appreciate it :)

[EDIT] Were you refering to this->_areas.remove(area)? You can pass a specific value to that.
Amended on Sat 19 Feb 2005 02:13 AM by Greven
David Haley USA #15
Ah yes, it's remove, not erase. Erase is for erasing given iterator(s) and remove is for values.
Samson USA #16 

   for( ich = ch->in_room->people.begin(); ich != ch->in_room->people.end(); )
   {
      rch = (*ich);
      ich++;


I've been noticing a pattern in crashes I'm weeding out when using std::list and figured I'd share what I've found so far.

It seems that iterating over a list like this is fine - so long as there's soemthing in it. Seems that every one of my crashes relating to lists dies in the for loop statement for them. So my guess is that while the list still has a valid iterator, the contents of the member are not. I'm not sure how else to go about making sure this doesn't happen since I was under the impression that if you did list.remove( member ) it took the member out of the list.

All of the ones I've found so far could potentially be empty lists, so I suppose I need to know: Do you have to verify the list is not empty before walking it ( with a list.empty() check ) ?
David Haley USA #17
No, when the list is empty, list.begin() == list.end() so the loop should not get past the condition part of the for(;;) statement.

Where are you calling remove?
Samson USA #18
In this particular case, it would be when the target dies in combat. Although they aren't technically removed until clean_char_queue takes them out. And I moved clean_char_queue down past all of the update handlers in update.c, so if checking the list to be sure it's empty first isn't going to be helpful, I've got a much nastier problem lurking. :(
Nick Gammon Australia Forum Administrator #19
You can certainly iterate over empty lists, the design specifically allows for that, which is why begin () points to the the start of a list, and end () points to one past the end of a list, so that the condition begin () == end () is true for empty lists (or maps or anything else).


However you need to be cautious about removing things from a list you are iterating through. The safe way is to increment the iterator before doing the remove. There is an example in the forum here, here it is again:



  for (people_map::iterator j = people.begin (); j != people.end (); )
    {
    if (j->second.GetAge () == 100)
      people.erase (j++); // iterator is advanced before the erase occurs
    else
      ++j;                  // advance the iterator
    } // end of erase loop


Notice that the way it is written, things will work correctly here. :)
Samson USA #20
So what are the consequences of doing something like so then:


   for( ich = ch->in_room->people.begin(); ich != ch->in_room->people.end(); )
   {
      rch = (*ich);
      ich++;

      ch->in_room->people.remove( rch );

      ...rest of function...


It appears to me that as long as the iterator is advanced to a valid location before calling for removal that it should work. What's the advantage of using erase() ? And suppose when the erase() call is needed you don't know what the current position of the iterator is in the list?
Greven Canada #21
If you don't know the iterator for the list, you can use find to retreive it, so that no iteration is required at all.
Raz #22
Quote:
Most likely, yes, because VARIABLE is what he's using as the value of the iterator. So it makes sense to assign the value of the iterator to VARIABLE at every pass.


I said that because such tricks are usually error prone to the hidden logic of C++. It really doesn't make sense to assign it in the conditional, but I would guess that he would have no other way to assign the variable and get the form he wants. (I don't know if that made complete sense.)

Quote:
Using for_each is major a pain in the behind because every time you use it, you need to create an external function - and if you want to use local variables, you have to make a functor, and pass it all kinds of variables in the constructor - basically, you have an awful lot of overhead.


You're assuming inlining a function guarantees better performance, which is not true. It is better to leave it up to the compiler via a function object than it is to write code in explicitly by hand. The compiler is almost always a much better chooser of how to optimize the code than the programmer.

Quote:
IMHO for_each is not a good solution for specific applications; it's a very good solution if you want to provide a generic way of mapping over the elements of a container.


If you want a specific solution, a different std:: algorithm would be better than std::for_each, of course. std::for_each is just the most general way when there isn't a more specific solution available.
Raz #23
Quote:
It appears to me that as long as the iterator is advanced to a valid location before calling for removal that it should work.


As long as the iterator is not referencing that element you should be ok. It is probably best to use erase() when you are using iterators and remove() when you are dealing just with values.

Quote:
What's the advantage of using erase() ?


erase() is probably a constant-time operation (I'm 99% sure, but I don't have my standard with me). remove(), OTOH, is linear and erases all the elements that compare equal to the value passed.

Quote:
And suppose when the erase() call is needed you don't know what the current position of the iterator is in the list?


Right.
David Haley USA #24
Quote:
You're assuming inlining a function guarantees better performance, which is not true. It is better to leave it up to the compiler via a function object than it is to write code in explicitly by hand. The compiler is almost always a much better chooser of how to optimize the code than the programmer.
You didn't understand my point. I'm not talking about optimization, I'm talking about a pain for the programmer to have to leave little functors lying around every time s/he wants to iterate over a list.
Quote:
It really doesn't make sense to assign it in the conditional, but I would guess that he would have no other way to assign the variable and get the form he wants.
I guess that it doesn't make sense if you think about the conditional as a test for continuing, but it certainly works. I wouldn't do it that way, but as far as I can tell it's the only way for him to use the macro the way he wants to.
Quote:
If you don't know the iterator for the list, you can use find to retreive it, so that no iteration is required at all.
Except for the iteration to find it. :P
Greven Canada #25
Heh, the macro isn't exactly important, just handy for our purposes, as it does its job in fairly clean code. As for my use of iteration, I meant it as the verb, not the noun :)