equivalent LinkedHashmap in C++?

Question

I have a Java program that I want to convert it to C++. So, there is a Linkedhashmap data structure used in the Java code and I want to convert it to C++. Is there an equivalent datatype for LinkedHashmap in C++?

I tried to use std::unordered_map, however, it does not maintain the order of the insertion.

Answer 1

C++ does not offer a collection template with the behavior that would mimic Java's LinkedHashMap<K,V>, so you would need to maintain the order separately from the mapping.

This can be achieved by keeping the data in a std::list<std::pair<K,V>>, and keeping a separate std::unordered_map<k,std::list::iterator<std::pair<K,V>>> map for quick look-up of the item by key:

• On adding an item, add the corresponding key/value pair to the end of the list, and map the key to the iterator std::prev(list.end()).
• On removing an item by key, look up its iterator, remove it from the list, and then remove the mapping.
• On replacing an item, look up list iterator from the unordered map first, and then replace its content with a new key-value pair.
• On iterating the values, simply iterate std::list<std::pair<K,V>>.