I was at a loss as to what to call this thread, but I hope the title works.

Ok, I've got a bug that I cannot reproduce 100% of the time, but through several hours of tests I have managed to tie it very probably to a set of things.

Here is all of the information that I think is relevant:

I'm working on a game. There is a vector of NPCs, and a vector of shots (fired by npcs, the player, etc.) Every frame, the game loops through all of the shots and moves them, then moves the NPCs, etc. When a shot detects a collision with an NPC, that NPC's death code is run, and then the shot enters an "animate and then vanish" state.

Today I added a boss. His special death code includes one extra thing: an explosion is created upon his death. This explosion is just another shot that cannot move or hurt anything, and just animates and then vanishes. I believe this is where the problem lies.

I noticed that sometimes, when I kill the boss with one of my shots, the boss will die and leave an explosion (as expected), but the shot that killed him will keep moving as if nothing happened. This only happens sometimes, though. I finally found that it happens much more consistently if I restart the whole program and immediately go to the boss's level and kill him. If I die, leave the level and come back, etc., it almost never happens again. But as soon as I restart the whole program it will usually (still not always, ugh) happen again the first time I kill that boss.

I believe I have fixed the problem, as I have tested it extensively (for a couple hours, just killing over and over and restarting) with and without my "fix," and this has never once happened with my fix applied.
Without the fix, it just does a push_back() on the shots vector inside of the npc death code. To fix it, I instead had it add the shot to a temporary vector, and the shot is only added to the real shots vector at the end of the logic code, after looping through everything.

I was reading over the explanation of vector::push_back on cplusplus.com, and it says that if the vector's size equals its capacity before the push_back, all of the vector's internal allocated storage is reallocated.
Is it possible that what was happening was
1) Begin looping through shots vector
2) Hey! This shot has hit a dude, call his death function.
3) He dies, and an explosion shot is added to the shots vector. Uh oh! Not enough capacity in the shots vector, reallocate!
4) His death function returns, and we go back to... the wrong shot, because of the reallocation.

Yeah, I believe that you shouldn't remove or add elements from a vector while you are iterating over it.

Thanks for the reply! I've done some further testing. I assumed that my above theory is correct: The problem is due to adding a shot to the shots vector inside of the "iterate through the shots" loop, which causes a reallocation of memory during the iteration through the vector.

I came up with a theory explaining the semi-randomness of the bug: I think it only occurs if the creation of the "explosion" shot causes a reallocation of the vector. This would only happen if the vector was just at capacity beforehand. There are other shots flying about (from other NPCs, etc.), which might cause the reallocation upon their (safe, outside of the iteration) creation. This would also explain why restarting the whole program usually allows the bug to occur again. I clear the shots vector whenever the player dies or changes levels, but I'm betting that only changes the vector's size, not its capacity. So after quite a few shots flying about, and the vector being cleared upon level change, it would then take a long time before the vector hit capacity again.

To test my theory, I disabled all AI, so no shots were created except for my own, and the "explosion" shot when the boss dies (I actually made the explosion occur for all NPCs' deaths for the test). After quite a few tests, I can reliably state that every single time, the first NPC, and ONLY the first NPC, exhibited the bug. This fits my theory, as the vector is reallocated for the creation of the second shot (the explosion shot) and the bug is caused.

To further test the theory, I added
vector_shots.reserve(100);
to the beginning of the logic loop, so the shots vector would always be big enough to hold 100 shots. This worked as expected, and the big did not show itself.

Sorry if I'm being really wordy, I'm just trying to understand this issue. And if someone in the future has a similar issue/question, hopefully this will help.

Can anyone verify that this is all true in C++? Unlike most of the bugs I create, I've had to get all scientific and statistical about testing this one.

Regarding containers and iterator invalidation -- sometimes a std::deque offers a good choice in-between std::vector and std::list (depending on the insertion/deletion-location profile in your application):
http://www.outofcore.com/2011/04/c-container-iterator-invalidation/

Hmm, never really used iterators for deletion of elements in a vector, i just access it with the [] operator. Don't know why i'd use the iterator if i can just use it like an array, honestly.

For deletion of elements, as long as the order of the elements in the vector doesn't matter, you could use std::swap to swap the element you want to delete with the last element in the vector, and then just call pop_back on the vector. Because if you delete an element from the middle of the vector, it needs to move all elements behind the one you deleted one slot forward.

You can add elements if you are looping over a vector without using iterators (accessing it as if it was an array) as reallocations won't matter then.

Actually, I think this is the exact opposite of what happens. Iterators to vectors are essentially pointers, and a reallocation will probably mess them up. The documentation for push_back says: "Reallocations invalidate all previously obtained iterators, references and pointers."

However, if you access elements by index, reallocations won't break anything.