[Home] [Downloads] [Search] [Help/forum]

Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to "verify" your details, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ Programming ➜ STL ➜ list for loops
list for loops

It is now over 60 days since the last post. This thread is closed.     Refresh page

Pages: 1 2  

Posted by Greven   Canada  (835 posts)  Bio
Date Fri 18 Feb 2005 01:31 AM (UTC)
Message
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.
Nobody ever expects the spanish inquisition!

darkwarriors.net:4848
http://darkwarriors.net
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #1 on Fri 18 Feb 2005 03:02 AM (UTC)
Message
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?
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Greven   Canada  (835 posts)  Bio
Date Reply #2 on Fri 18 Feb 2005 05:33 AM (UTC)

Amended on Fri 18 Feb 2005 06:33 AM (UTC) by Greven

Message
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.
Nobody ever expects the spanish inquisition!

darkwarriors.net:4848
http://darkwarriors.net
Top
Posted by Greven   Canada  (835 posts)  Bio
Date Reply #3 on Fri 18 Feb 2005 06:36 AM (UTC)
Message
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.
Nobody ever expects the spanish inquisition!

darkwarriors.net:4848
http://darkwarriors.net
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #4 on Fri 18 Feb 2005 06:50 AM (UTC)
Message
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.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Greven   Canada  (835 posts)  Bio
Date Reply #5 on Fri 18 Feb 2005 06:57 AM (UTC)

Amended on Fri 18 Feb 2005 07:06 AM (UTC) by Greven

Message
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 :)
Nobody ever expects the spanish inquisition!

darkwarriors.net:4848
http://darkwarriors.net
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #6 on Fri 18 Feb 2005 03:39 PM (UTC)
Message
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
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Samson   USA  (683 posts)  Bio
Date Reply #7 on Fri 18 Feb 2005 07:43 PM (UTC)
Message
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?
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #8 on Fri 18 Feb 2005 08:06 PM (UTC)
Message
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.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Raz   (32 posts)  Bio
Date Reply #9 on Fri 18 Feb 2005 09:11 PM (UTC)
Message
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
C++ Wiki: http://danday.homelinux.org/dan/cppwiki/index.php
Top
Posted by Raz   (32 posts)  Bio
Date Reply #10 on Fri 18 Feb 2005 09:21 PM (UTC)
Message
Quote:
So if I do something like this:


*snip*

Yes. std::list::erase only invalides the iterators that it erased.
-Raz
C++ Wiki: http://danday.homelinux.org/dan/cppwiki/index.php
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #11 on Fri 18 Feb 2005 10:52 PM (UTC)
Message
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.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Greven   Canada  (835 posts)  Bio
Date Reply #12 on Sat 19 Feb 2005 01:16 AM (UTC)

Amended on Sat 19 Feb 2005 01:19 AM (UTC) by Greven

Message
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.
Nobody ever expects the spanish inquisition!

darkwarriors.net:4848
http://darkwarriors.net
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #13 on Sat 19 Feb 2005 01:38 AM (UTC)
Message
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.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Greven   Canada  (835 posts)  Bio
Date Reply #14 on Sat 19 Feb 2005 01:59 AM (UTC)

Amended on Sat 19 Feb 2005 02:13 AM (UTC) by Greven

Message
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.
Nobody ever expects the spanish inquisition!

darkwarriors.net:4848
http://darkwarriors.net
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

79,736 views.

This is page 1, subject is 2 pages long: 1 2  [Next page]

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]