The _bound() and equal_range() generic algorithms take linear time when
using non-random iterators. Map iterators are non-random (they're
bidirectional), which gives these generic algorithms linear behavior on maps.
It seems wasteful to have linear searching behavior on an ordered sequence, so maps (and the other sorted associative containers) re-implement these generic algorithms to exploit the internal tree representation (which is not accessible to generic algorithms), skipping the bidirectional iterators and getting the expected O(log n) behavior.
This page last modified on 12 March 2004.