equivalent LinkedHashmap in C++?

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

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