Just to fine tune @kerrek sb's very nice answer above, the equality comparison for it->first should be using the collection's key_comp(). It should probably be something more like !m.key_comp()(key, it->first). (given the other answers' guidance around using upper_bound vs. lower_bound, which comparison needs to be done should be tuned accordingly.)