Would it make sense to define a bimap like this: boost::bimap< boost::bimaps::set_ofstd::string, boost::bimaps::vector_ofstd::string> mymap; And then make the right view (vector_of) more amenable to lookups by performing a sort followed by a binary search on it? Thanks.