I was writing the first lines of code for a game prototype while listening to this. I looked at the code I was writing, and promptly put it aside -- I was coming up with a nice advanced, performance implementation of dynamic octrees to represent the voxels my world is based on ... but why do I need that, before anything runs at all? Sure, I will need it in the future (although not the super, super optimized version until well into the future), but I should have this running before moving forward. I'm glad I watched this, and saved myself some pain initially.
I made an iPhone game (tower defense) where everything used std:vectors until I ran into performance problems. And lo and behold they could all be solved with using data structures for which the necessary operations where less expensive. The changes were quite easy to make since the containers use a common interface.
The real gotcha is that the vast majority of containers are still vectors, since the operations on them didn't show up in profiling. So I guess yeah create some gameplay and optimize your bottlenecks not your lack of Data structure fun.
In the most important case it was sets.
There was a collision detection routine that took up too much time because checking membership for vectors is not constant time. The sets/vectors were very small though, low double digits, but once you do stuff 30 times per second for a couple a hundred objects it can get slow. (only on the iPhone though, in the simulator everything was good)
For the general world representation I used a static grid, as the object size was very homogenous, so a quad tree would have been overkill.
