While working on a 2D particle physics terrain system (which was never actually completed), I needed a way to speed up the whole system in general. The answer to this was to implement a quadtree for the particles.
I could have simply written a specialized quadtree for the particles which would have worked fine. However, using the knowledge of templates I gained while working on Versus the Internet, I decided to write a reusable C++ template quadtree.
The quadtree template holds a structure for each object, containing a pointer to the object itself and an included rectangle class for the outer bounds of the object for sorting it in the quadtree.
Other than that it works like any standard quadtree with elements being retrieved based on a rectangle of the area to retrieve from.
Using this implementation increased performance for insertion and removal in my terrain system around 20,000%. That is not an exaggeration, framerate increased from 0.1 fps using an STL Vector to hold the particles in the terrain to 2000+ fps using my quadtree.
This project is open source and available on github here.