Looking for a container, that stores elements under custom key (like a map), allows searching under the key in better complexity, then O(n) (like a map), but also remembers the order in which pairs (key and value) were inserted, allowing for push_front and pop_back functionality, like in the list
edit: Solved simply using both containers. Map for storing pairs and list for storing the indexes in order. Will leave this question open if someone comes with more elegant solution.
There is no such data structure in the standard library.
A "trivial" way to implement such structure would be to use two separate structures internally. A map for lookup, and a list (or a vector, or a deque) for iterating in insertion order. One of the data structures should store the objects, and the other can store pointers to the objects.
There is a generalization of this kind of multi-index container in the Boost library collection.