If you''re going to try to "find" before "insert", don''t use find--use lower_bound.
map::lower_bound (key) will give you an iterator pointing to where the record should be. If it isn''t there (if it->first != key), then you need to insert it. Insert using the iterator overload:
map::insert (it, map::value_type (key, type));
The difference is this: if you try find (key), and the key''s not there, it just searched through the entire map but you only have an iterator pointing to map::end (). Seeing this, you insert the same key, causing the exact same search you just performed. That''s two identical searches.
map::lower_bound (key) will find the iterater that either points to the record you want, or points to where your new record should go. When you insert and give it the iterator, insertions happen in constant time (instead of lgN).
