Most memory managers worth their salt tend to cache commonly used sizes, that's why tree accesses aren't on the fast path.

I have now looked at Hoard. It does use std::map which is indeed a red-black tree.