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

Unordered Map or any other STL method inbuilt in C++ cannot give same order as LinkedHashMap although you can maintain the order of insert and access the unordered_map use the maintained order.

Below is the image just to show how unordered_map behaves. It has No Order.

Map is RB tree and it gives a sorted order if an iterator is used.

Hence no specific solution for this question.

Answer 2

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>>.

Answer 3

The insertion order contract on key iteration can be achieved with a balanced tree for log(n) performance. This is better than maintaining keys in a list as item removal requires n lookup time. My mantra is never put something you look up in a list. If it doesn't have to be sorted, use a hash. If it should be sorted, use a balanced tree. If all you're going to do is iterate, then a list is fine. In c++ this would be std::map where the key is the item reference and the value is the insertion order, the keys are sorted using red-black trees. See: Is there a sorted container in STL