CODEWITHSUNDEEP
c++containersstd
David162795
David162795

Reputation: 1866

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.

Upvotes: 1

Views: 103

Answers (1)

eerorika
eerorika

Reputation: 238471

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.

Upvotes: 4

Related Questions