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.

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

Sergey Kalinichenko · Accepted Answer · 2023-05-23T16:45:13.760

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<std::pair<K,V>>::iterator> 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>>.

edited May 23 '23 at 16:45

answered Feb 06 '17 at 16:16

Sergey Kalinichenko

714,442
84
1,110
1,523

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
If I write `std::list::iterator>` the compiler complains 'list' is not a class, namespace, or enumeration. But doesn't complain if I do `std::list>::iterator`, however, the latter doesn't seem to work... – Adeesh Lemonickous May 23 '23 at 16:28
@AdeeshLemonickous You are correct on the syntax, I put `::iterator` in the wrong place. The code logic should work, though. – Sergey Kalinichenko May 23 '23 at 16:48

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