ファクトリにvector？　逐次探索使ってるんか？
それに比べたらmapのほうが高速だと思うが。
それともハッシュと組み合わせたらvecto

mapが遅いのはおそらく同様の

mapは内部構造が二分木だから遅いんじゃなかったっけ？
ハッシュ二分木のhash_mapってのがSTLに追加されたと思う。
そちらを使ってみては。