3 ms·
These containers are problematically slow for most use cases but it is not really their fault. An internal design that will give good performance is hugely depe
by jandrewrogers 12y ago
These containers are problematically slow for most use cases but it is not really their fault. An internal design that will give good performance is hugely dependent on the use case and the C++ STL offers little ability to specify the nature of the use case so that appropriate internals can be constructed. Consequently, the default implementation will always be pathologically poor for some significant subset of use cases.
A similar problem exists for other types of STL containers but it is particularly acute for the map and set containers. Some programmers end up building their own library of map implementations, each implementation optimized for a different use case, to get around this problem. The number of template parameters you would need to generalize std::map would be ridiculous, so it is easier to just have a lot of specialized implementations.
For high-performance code, std::map and friends are usually the wrong choice. Personally, I always write usage optimized maps as needed these days; the first couple times seem tedious but it quickly turns into a simple idiom you can implement in your sleep.