David162795 David162795 - 1 year ago 55
C++ Question

Looking for std container between map and list

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.

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download