There is hardly a container that would provide efficient access to data in two indexes. But instead of std::map you can use anything, for example, balanced trees, the more code will be written in C. the Main idea of my proposal is to post the indexes and the data itself. Then the cost of the search slots, insert slots, and updates the indexes, you can try to minimize.
Displacement, too, is fairly simple: at index access time, we find the slot with the minimum value of access time (oldest) and replace it in all fields. Of course, you will have to update both indexes.
Index updates can be done via the delete index entries and add new ones.