The implementation isn't guarenteed.
stl_map is a part of the standard template library, which can be implemeted in any number of different ways. For example, gcc ships with one version of the library, but can also compile with stlport (a different version).
What is defined is that the insertion and lookup routines will take a length of time proportional to the logarithm of the number of elements in the list. In other words, it's guarenteed to be fast.
But it could also be implemented by several other forms of binary search tree, or even (I think) an open-bucket hashmap.
The implementation isn't defined in the standard for the perfectly good reason that if someone finds a better method, it can be re-implemented without having to change the standard.
Hope that helps,
— Robert J. Lee
|