Boost, loki, and I'm sure others have a "flat" map which is just an array backed ordered map. Slower insertions than the red-black map but because of the cache locality it's much faster overall.