equivalent LinkedHashmap in C++?

c++ unordered-map linkedhashmap
emadalamoudi picture emadalamoudi · Feb 6, 2017 · Viewed 9k times · Source

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

Sergey Kalinichenko picture Sergey Kalinichenko · Feb 6, 2017

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

Related questions

C++ unordered_map using a custom class type as the key

I am trying to use a custom class as key for an unordered_map, like the following: #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; class node; class Solution; class Node { public: …

Read More
Is there any advantage of using map over unordered_map in case of trivial keys?

A recent talk about unordered_map in C++ made me realize that I should use unordered_map for most cases where I used map before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ). Most times I …

Read More
Choosing between std::map and std::unordered_map

Now that std has a real hash map in unordered_map, why (or when) would I still want to use the good old map over unordered_map on systems where it actually exists? Are there any obvious situations that I …

Read More