Per inciso, se punti alle performance ti conviene usare una unordered_map (aggiunta del tr1), che dovrebbe avere performance migliori della normale map e non invalidare gli iteratori agli elementi che non c'entrano nelle operazioni di aggiunta e rimozione. La unordered_map (di fatto una hashtable) ha inoltre tempo di accesso costante agli elementi (nel caso medio), il che dovrebbe andare bene per i tuoi scopi.