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

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.