van Emde Boas trees need quite a few tricks in order for an implementation to be truly competitive, but then they can be really quick: "Engineering a Sorted Lis

van Emde Boas trees need quite a few tricks in order for an implementation to be truly competitive, but then they can be really quick: "Engineering a Sorted List Data Structure for 32 Bit Keys", Roman Dementiev, Lutz Kettner, Jens Mehnert, Peter Sanders. http://algo2.iti.kit.edu/dementiev/files/veb.pdf http://algo2.iti.kit.edu/dementiev/files/veb.pdf - code: http://people.mpi-inf.mpg.de/~kettner/proj/veb/ http://people.mpi-inf.mpg.de/~kettner/proj/veb/