Just use std::map directly.

when I get a data, I want to get its id from it, not from some book-keeping; thus I'd like to avoid a std::map

Inside std::map, it store the key and value as a std::pair, so you do not need any book-keeping to get both key and value.

Further reading: more information about std::map