La map è un buon compromesso tra la ricerca e la velocità d'accesso all'elemento cercato, però non farti ingannare dall'operator[] che possiede: l'indice della map è univoco, se non stai attento rischi memory leak.
Comunque non hai specificato la frequenza di inserimento/annullamento (quindi di ricerca) dei puntatori interessati, quindi non è possibile darti una risposta specifica, se non all'acqua di rose.