If you're gonna have a huge density of entities, you're probably better off considering a sparse mapping structure for your entities (a map/dictionary). I don't have a lot of entities per map currently, so for me a simple list works just fine
So, maps/dictionaries. Each key-value pair has a key that identifies the tile (a tuple/pair of its coordinates), and the value is a pointer to the entity. Since you brought up the issue of per-tile vectors, you want multiple values with the same key (many entities at the same tile), a multi-map/dictionary. Dictionaries are easy in python, though to turn one into a multi-dictionary you need a tiny class (see here
, it's pretty cool!). In C++, if I'm not mistaken, the STL already has a multi-map class, so you're set
This way you can iterate all entities if you want to (to update them or something), or just find the ones in specific tiles. Using STL's multi-map it should be relatively painless to move one entity from a tile to another by just changing its key. Using this python multi-map, you have to remove it from the list at one key and append it to the list at another key.