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.

No, you don't have it. it's an ugly data structure to begin with, no wonder no one ever suggested to standardize it — David Haim, Feb 06 '17 at 16:04
@DavidHaim hmmm. So, how can I create a hashmap with predictable iteration order? — emadalamoudi, Feb 06 '17 at 16:07
You need to ask yourself why would the insertion order in a hashmap matter in the first place.. — David Haim, Feb 06 '17 at 16:08
Do you need "global" insertion order or "local" only for duplicate keys ? multi-value hash map. — ibre5041, Feb 06 '17 at 16:10
I have to agree with @DavidHaim. It would take you less time, search to keep a secondary structure if order is so imperative. But I have not found the need for order in a map myself — efekctive, Feb 06 '17 at 16:10
@ibre5041 not for duplicating element for sure. I think it has been used to maintain the global insertion order. — emadalamoudi, Feb 06 '17 at 16:15
I commonly use LinkedHashMap as an LRUCache because its removeEldest() method easily supports size-and-time-bounded caches. Others looking for the same thing might follow this question instead https://stackoverflow.com/questions/2504178/lru-cache-design — Wheezil, Apr 01 '20 at 19:36

score 31 · Accepted Answer · answered Feb 06 '17 at 16:16

31

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

answered Feb 06 '17 at 16:16

Sergey Kalinichenko

697,062
78
1,055
1,465

Thanks, I think this is what I need to do. It will add more complexity but at least it will still mantaining the order. Thanks again – emadalamoudi Feb 06 '17 at 16:23
5

Since this is the accepted answer, I still find it necessary to point out that this is worse than a LinkedHashMap: 1) Additional indirection when looking up by key 2) Hash-lookup required for erase-by-iterator. An integrated solution where the entry contains pointers for two linked list (insertion order and hash bucket) has neither of these drawbacks. Does it matter? Hard to say/depends. Is the proposed solution *strictly* inferior to such a LinkedHashMap? Yes. – misberner Jun 16 '17 at 22:05
What happen if I need to sort the `std::list>`? – Kok How Teh Nov 02 '20 at 12:39
@KokHowTeh You never need to sort the list explicitly. It's there to maintain the order of iteration, and to keep the values. If you need to iterate map on keys, use `std::map`, it's going to do it automatically. If you need to iterate in sorted order once, copy the data into a vector and sort once; it's going to be faster. – Sergey Kalinichenko Nov 02 '20 at 12:45
This is a valid use case. For example, I need to sort when I add a batch of items into the list and maintain the order according to an ordering criteria. – Kok How Teh Nov 02 '20 at 12:48
@KokHowTeh This isn't what Java's `LinkedHashMap` does. If it's a use case you need to support, you need a different data structure. – Sergey Kalinichenko Nov 02 '20 at 12:51

score 2 · Answer 2 · answered Mar 20 '18 at 22:20

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

Removing keys from a LinkedHashMap is constant-time, not linear. To make this work, the hashmap entries have to maintain a reference to the corresponding linked list entry. — divegeek, Jun 06 '19 at 15:49

Kok How Teh · Answer 3 · 2020-11-03T06:42:32.323

This is how I do it:

    map<TKey, set<MyClass<K1,K2>, greater<MyClass<K1, K2>>>> _objects; // set ordered by timestamp. Does not guarantee uniqueness based on K1 and K2.
    map<TKey, map<K2, typename set<MyClass<K1, K2>, greater<MyClass<K1, K2>>>::iterator>> _objectsMap; // Used to locate object in _objects

To add object id:

    if (_objectsMap[userId].find(id) == _objectsMap[userId].end())
       _objectsMap[userId][id] = _objects[userId].emplace(userId, id).first;

To erase an object id:

   if (_objectsMap[userId].find(id) != _objectsMap[userId].end()) {
       _objects[userId].erase(_objectsMap[userId][id]);
       _objectsMap[userId].erase(id);
   }

To retrieve, say the most recent size objects from the list starting from a specific object id:

    vector<K2> result;
    if (_objectsMap[userId].find(id) != _objectsMap[userId].end() && _objectsMap[userId][id] != _objects[userId].begin()) {
        set<MyClass<K2, K2>, greater<MyClass<K1, K2>>>::iterator start = _objects[userId].begin(), end = _objectsMap[userId][id];
        size_t counts = distance(_objects[userId].begin(), _objectsMap[userId][id]);
        if (counts > size)
            advance(start, counts - size);        
        transform(start,
            end,
            back_inserter(result),
            [](const MyClass<K1, K2>& obj) { return obj.ID(); });
    }
    return result;

equivalent LinkedHashmap in C++?

3 Answers3

Linked