   std::map serial access
  Is serial access too slow with std::map?_AnimationMap is std::map <string, Animation> (Animation is a "container" of Sprite objects)Is the code below slow?bool AnimatedSprite::Collision(const AnimatedSprite &spr1, const AnimatedSprite &spr2){registry_type::const_iterator it1 = spr1._AnimationMap.begin();registry_type::const_iterator it2 = spr2._AnimationMap.begin();registry_type::const_iterator end1 = spr1._AnimationMap.end();registry_type::const_iterator end2 = spr2._AnimationMap.end();for(; it1 != end1; std::advance(it1, 1) ){for(; it2 != end2; std::advance(it2, 1) ){const Sprite spr1 = *it1->second->_ImgVec[it1->second->_current];const Sprite spr2 = *it2->second->_ImgVec[it2->second->_current];if( Sprite::Collision(spr1, spr2) ) return true;}}return false;}
  I don't know, is it slow? Did you test? I don't see why it would be... What do you mean by "slow"?However, I'd probably just say that you don't really need to use std::advance since you can just use ++it (std::advance(it, n) is the same as executing ++it n times)   ;  Yes, it is "slow".First, there is algorithmic "slowness". The code performs n^2 comparisons, when only n(n-1)/2 are needed.Next, is the implementation "slowness".Quote:const Sprite spr1This creates a copy of sprite. That is 2*n^2 new copies, when exactly 0 are needed. At minimum, do const Sprite & spr1Maps are also highly unsuitable for iteration, since they do not allocate memory continuously. The way the std::map usually lays out memory you are almost guaranteed a cache miss on each access. Using vector to store the elements however would improve on all of the above by a considerable factor.   ;Quote:Original post by AntheusFirst, there is algorithmic "slowness". The code performs n^2 comparisons, when only n(n-1)/2 are needed.Actually, I just read the code (heh) and it doesn't actually do n2 comparisons, but that's only because there's a bug: it2 is not reset at the beginning of the outer loop. If you set it2 = it1 at the beginning of the outer loop, then you'll be doing the correct number of comparisons (which you can't really get away from for collisions without some kind of spacial partitioning, like a quadtree/octree)   ;Quote:Original post by CodekaActually, I just read the code (heh) and it doesn't actually do n2 comparisons, but that's only because there's a bug: it2 is not reset at the beginning of the outer loop. If you set it2 = it1 at the beginning of the outer loop, then you'll be doing the correct number of comparisons (which you can't really get away from for collisions without some kind of spacial partitioning, like a quadtree/octree)I was too quick skimming over what looked like a typical collision test, which the above code isn't. It compares all possible pairs between two sets, and is therefore m*n.But despite that, I always wrote "slow", since there exists a better way to implement inner loop, but it doesn't mean that current version (provided it worked correctly) would be a problem.   ;Quote:Original post by sheep19Is serial access too slow with std::map?_AnimationMap is std::map <string, Animation> (Animation is a "container" of Sprite objects)Is the code below slow?*** Source Snippet Removed ***Its main problem is not that it's slow: It's just wrong. You never set it2 back to the beginning of the container, so you are only testing if the first object in spr1 collides with any objects in spr2. From that point on the inner loop is never entered, since it2 is at end2. If you declare and initialize local variables in the first place where they are used, you won't make this type of mistakes.You cannot use the identifiers _AnimationMap and _ImgVec because they start with an underscore followed by a capital letter. See for instance this if you don't know why.Why are you using `std::advance(it1, 1)' instead of simply `++it1'?As it was pointed out, instead of `const Sprint spr1 = ...' you probably meant something like `Sprint const & spr1 = ...'.Minor issue: The function should probably be called simply `Collision' instead of `AnimatedSprite::Collision'. I guess it's a static member function, but a free function makes more sense.There's a lot to fix here before you have to care about the performance of serial access to std::map (which, by the way, is not slow at all).   ;  It might even be incredibly slow, but it's of no concern to you whatsoever until you can prove it's taking a significant amount of time in your program.  You'd prove that by profiling it.  Even if the function can be made to run 100 times faster, if your program only spends 0.1% of its time in it, that's at most a 0.1% speed increase.It is most important to write code that is correct and clear.  After that, measure its performance with a profiler, then worry about what is slow.   ;  I fixed it:bool AnimatedSprite::Collision(AnimatedSprite &spr1, AnimatedSprite &spr2){registry_type::const_iterator it1;registry_type::const_iterator it2;registry_type::const_iterator end1 = spr1._AnimationMap.end();registry_type::const_iterator end2 = spr2._AnimationMap.end();for(it1 = spr1._AnimationMap.begin(); it1 != end1; ++it1 ){for(it2 = spr2._AnimationMap.begin(); it2 != end2; ++it2 ){Sprite &s1 = (*it1->second->_ImgVec[it1->second->_current]);Sprite &s2 = (*it2->second->_ImgVec[it2->second->_current]);s1.SetPos(spr1.x(), spr1.y());s2.SetPos(spr2.x(), spr2.y());if( Sprite::Collision(s1, s2) ) return true;}}return false;}I don't need to iterator through all Sprites in every Animation, because I want to test the current frame (current Sprite).   ;Quote:Original post by sheep19I fixed it:*** Source Snippet Removed ***I don't need to iterator through all Sprites in every Animation, because I want to test the current frame (current Sprite).Then you don't need two loops.   