Is there a data structure that works like a map but also allows the sequence of values to be used independently of the keys?

Often I have a map for which the keys are only used for importing, exporting and setup. During the performance critical stage, the values are of importance, not the keys.

I would like to use a data structure that acts like a map but gives me the option to just use a simple vector of mapped values when the keys are irrelevant.

The implementation seems reasonably simple. Just use a pair of equally sized vectors in which to store the key and value respectively, sorted with respect to the key vector. Insertions and deletions will be less efficient than in boost::flat_map, but that is a compromise I'm willing to make in order to get instant access to the vector of key unencumbered values.

Is this a terrible idea? If not, is there an existing implementation I can use?

via Chebli Mohamed