list iterator problem

This topic is 4427 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

heya, I got a std::list with gameobjects and i want to iterate through the list comparing 2 objects with eachother without comparing the same objects twice. With an array i would do it like this:
for(int i = 0; i < length - 1; i++) {
for(int j = i + 1; j < length; j++) {
//dostuff with array and array[j]
}
}

But I can't figure out how to do the same algorithm with iterators and a std::list. Any advice appreciated! thanks, benderB

Share on other sites
thanks for the quick reply.

so is it legal to do something like this:

for(std::vector<IObject*>::iterator iter1 = nodes.begin(); iter1 != nodes.end() - 1; iter1++) {  for(std::vector<IObject*>::iterator iter2 = iter1 + 1; iter2 != nodes.end(); iter2++) {    (*iter2)->dostuff(*iter1);    }}

Share on other sites
You don't need the iterator, you can use regular indexing. You may want to check you loop indices though so they don't exceed .size().

Share on other sites
Yes it is legal to perform arithmetic on iterators, but if it isn't a random access iterator (which only std::vector and maybe std::deque support) then you can only increment and decrement them (and then it depends whether they are bidirectional or not [grin]).
If you are using a std::vector or std::deque it is simpler and faster to use random access (i.e. with [ and ]) instead of iterators.

Share on other sites
You can do it just fine with an std::list. The example you gave does not require a random access iterator, so the suggestion to use an std::vector is premature.

What are you using this data structure for? Will you need to access elements often and at widely varying places? If so, then an std::vector is a good suggestion. If you are more worried about insertion and deletion times, then an std::list might be a better option.

So anyway, to go back you your original question, you can do it like the following:

for( std::list< int >::iterator it = l.begin(); it != l.end(); ++it )  for( std::list< int >::iterator it2 = it; it2 != l.end(); ++it2 )    if( it != it2 )      *it < *it2; //comparison goes here
There's probably a better way, since you are doing one extra iteration per loop compared to what you were looking for.

jfl.

Share on other sites
thanks for the replies!

As for what I'm using the container:
At the moment it's a placeholder for collision checks between game object until I implement a more perfomant version.

A scenenode can register itself to be collision checked via:

void CSceneManager::registerNodeForCollision(ICollideable* node) {	collisionNodes.push_back(node);}

and in the update methode the registered nodes are checked for collision with each other with the discussed loop.
So basically i only push_back nodes into the container and test them against each other.
Is a vector better suited for this?

thanks again,
benderB

Share on other sites
Quote:
 Original post by benderBIs a vector better suited for this?

Most likely, as iterating through a list is slower than a random-access iteration through a vector (although you may not notice this untill your list/vector contains quite a few items).

Share on other sites
There are a number of methods of speeding up collision tests. If you find that comparing each item to every other item becomes too slow (because there are a lot of items) then let us know and we'll tell you about some of the more advanced methods of collision detection, using spatial partitioning of some kind.

Share on other sites
again thanks for the help!

Quote:
 Original post by iMalcThere are a number of methods of speeding up collision tests. If you find that comparing each item to every other item becomes too slow (because there are a lot of items) then let us know and we'll tell you about some of the more advanced methods of collision detection, using spatial partitioning of some kind.

i've already got some ideas but i'm sure i'll need your help anyway :)