> What's wrong with red-black trees for an ordered map?
I was wondering that too, except without the "n ordered" part. The claim that trees are competitive with hash tables in the average case rests on the claim that comparison is much faster than hashing, because you only have to hash once in the average case, whereas you have to compare something like 1.5 lg N times in the average case, which might be between 4 and 22 in common cases. I just ran this microbenchmark to compare hashing integers with comparing them, and hashing seems to be actually slightly faster than comparing on my CPU; this implies that hash tables should be dramatically faster than red-black trees.
In theory, this forces an unpleasant dilemma on code that aspires to be real-time but wants to do a lookup in a finite map: use hash tables with their awful worst-case performance (typically O(N), although you can improve this by hanging trees off your hash buckets, but that would be stupid), or use trees with their awful average-case performance?
In practice, I've never written real-time code, so I don't know if this dilemma is real.
It won't perform allocations, but since the structure has been built from multiple disjoint allocations, you're likely to get worse spatial coherence. (I.e. more cache misses)
And yes, for an ordered map RBL is not a bad choice. "I object to std::map being ordered" would probably have been the better wording.
What's wrong with red-black trees for an ordered map?
> IRC, both hash_map and std::map don't support a reserve call. Which means you pay for quite a few allocations.
This is absolutely an issue for insert performance, but I was only benchmarking lookup performance, which should not perform any allocations.