There are a lot of games that can generally be viewed as a bunch of objects spread out through space, and a very common operation is to pick all objects in a sub-area. The typical example would be a game with tons of units across a large map, and an explosion that affects units in a certain radius. This requires picking every unit in the radius in order to apply the effects of the explosion.
Now, there are several ways to store objects that allows efficiently picking a sub-area. The easiest method is probably to divide the map into a grid; picking units in an area would involve selecting only the parts of the grid that is affected, and do a fine-grained coordinate check grid tiles that aren't 100% inside the area.
What I don't like about this approach is answering "How large should the grid tiles be?" Too large, and efficiency may become a real problem. Too small, and the grid takes up tons of memory if the game world is large enough (and can become ridiculous if the game is 3d). There may not even be a suitable golden mean.
The obvious solution to the above is to make a large grid with some kind of intelligent subdivision, like a pseudo tree-structure. And it is at this point I know for sure I am far into premature optimization. (Then there are proper dynamic quad/octrees, but that's even more complex to code and I'm not even confident it will perform any better.)
So my question is: Is there a standard solution to the above problem? Something, in the lines of an STL container, that can just store any object with a coordinate, and retreive a list of objects within a certain area? It doesn't have to be different than what I described above, as long as it's something that has been thought out and deemed "good enough" for a start.
Bonus points if there is an implementation of the algorithm in Python, but C would also do.
I don't know anything about games programming, but I would imagine (based on intuition and what I've read in the past) that a complete grid will get very inefficient for large spaces; you'll lose out in both storage, and also in time, because you'll melt the cache.
STL containers are fundamentally one-dimensional.  Yes, things like set and map allow you to define arbitrary sort relationships, but it's still ordered in only one dimension.  If you want to do better, you'll probably need to use a quad-tree, a kd-tree, or something like that.
A container for accessing contents by 2d/3d coordinates