As the title says, I'm toying around with developing a 2D space RTS game. All of my units are spaceships that basically just shoot at one another, but they have to do a variety of other things as well: they have to "discover" (notify, draw, etc) other ships and planets not owned by the owner of this ship and within the arbitrary range of the ship's "scanners" (since they would otherwise be hidden), and if the ship is told to fire on an enemy ship, it needs to find the closest enemy (and fly to it if out of shooting range), and then shoot it obviously.

I've been wondering what would be the most efficient data container for the ships if there is going to be a large number of ships (100s to maybe 1000s)? Also to note, is that ships must be distinguished by their owner (I may go to war with one player, so I obviously do not want my ships to search for ships of other players), where ownership will probably be represented by some integer (1 = player 1, 2 = player 2, etc) or maybe the unique pointer/memory address of a "player" object (0x4ff = player 1, 0x5ea = player 2, etc) or some other simple identifier.

I initially thought about using an array of vectors (C++), with the index of the array representing the player and each vector being the ships belonging to that player; then take all ships belonging to whatever player you are at war with and place them into a priority queue, whose root would be the enemy ship closest to a specific (friendly) ship and decide if its in range or not, but this seemed far too slow and memory-expensive, and didn't really address how to scan for ships/planets.

I then read up a few related posts about quadtrees and this lead me to other such tree data structures, like R-trees, that are also used for optimal spatial queries, but I do not quite understand exactly how they work and whether or not they would be best for me, so here we are.