The problem with a [quad][1]/[octree][2] in nearest-neighbor searches is that the closest object may be sitting right across the division between nodes. For collisions, this is okay, because if it's not in the node, we don't care about it. But consider this 2D example with a quadtree:

![Quadtree example][3]

Here, even though the black item and green item are in the same node, the black item is closest to the blue item. [ultifinitus' answer][4] can only guarantee the nearest-neighbor only every item in your tree is placed in the smallest possible node that could contain it, or in a unique node - this leads to more inefficient quadtrees. (Note that there are many different ways to implement a structure which could be called a quad/octree - more strict implementations may work better in this application.)

A better option would be a [kd-tree][5]. Kd-trees have a very efficient [nearest-neighbor search][6] algorithm you can implement, and can contain any number of dimensions (hence "k" dimensions.)

A great and informative animation from Wikipedia:
![kd-tree nearest-neighbor search][7]

The biggest problem with using kd-trees, if I recall correctly, is that they are more difficult to insert/remove items from while maintaining balance. Therefore, I would recommend using one kd-tree for static objects such as houses and trees which is highly balanced, and another which contains players and vehicles, which needs balancing regularly. Find the nearest static object and the nearest mobile object, and compare those two.

Lastly, kd-trees are relatively simple to implement, and I'm sure you can find a multitude of C++ libraries with them. From what I remember, R-trees are much more complicated, and probably overkill if all you need is a simple nearest-neighbor search.


 [1]: http://en.wikipedia.org/wiki/Quadtree
 [2]: http://en.wikipedia.org/wiki/Octree
 [3]: https://i.sstatic.net/JkQCY.png
 [4]: http://gamedev.stackexchange.com/q/14373/7881
 [5]: http://en.wikipedia.org/wiki/Kd-tree
 [6]: http://en.wikipedia.org/wiki/Kd-tree#Nearest_neighbour_search
 [7]: https://i.sstatic.net/OWDEX.gif