在C++中等价的LinkedHashmap是什么？

Question

我有一个Java程序，想将其转换为C++。因此，在Java代码中使用了Linkedhashmap数据结构，我想将其转换为C++。在C++中是否有与LinkedHashmap相当的数据类型？

我尝试使用std::unordered_map，但它不会保持插入顺序。

- emadalamoudi

---

你需要问自己为什么哈希映射中的插入顺序首先很重要。 - David Haim

您需要针对重复的键使用“全局”插入顺序还是仅“本地”？多值哈希映射。 - ibre5041

我必须同意@DavidHaim的观点。如果顺序很重要，那么保持第二结构将节省您更少的时间和搜索。但是我个人在映射中没有发现有序的需要。 - efekctive

@ibre5041 肯定不是为了复制元素。我认为它被用来维护全局插入顺序。 - emadalamoudi

我通常使用LinkedHashMap作为LRUCache，因为它的removeEldest()方法很容易支持大小和时间有限制的缓存。其他寻找相同功能的人可以查看这个问题：https://dev59.com/LXE95IYBdhLWcg3wApBU - Wheezil

Answer 1

C++没有提供一个集合模板，其行为类似于Java的LinkedHashMap<K,V>，因此需要将顺序与映射分开维护。

这可以通过将数据保留在std::list<std::pair<K,V>>中，并保持单独的std::unordered_map<K,std::list<std::pair<K,V>>::iterator>映射以便通过键快速查找项目来实现：

• 添加项目时，将相应的键/值对添加到列表末尾，并将键映射到迭代器std::prev(list.end())。
• 按键删除项目时，查找其迭代器，从列表中删除它，然后删除映射。
• 替换项时，首先从无序映射中查找列表迭代器，然后替换其内容为新的键-值对。
• 迭代值时，只需迭代std::list<std::pair<K,V>>。

- Sergey Kalinichenko

---

谢谢，我认为这就是我需要做的。它会增加更多的复杂性，但至少它仍然保持着顺序。再次感谢。 - emadalamoudi

既然这是接受的答案，我仍然认为有必要指出，这比LinkedHashMap更糟糕：1）按键查找时需要额外的间接方式；2）使用迭代器删除需要哈希查找。一个集成的解决方案，在条目中包含两个链接列表的指针（插入顺序和哈希桶），没有这些缺点。这重要吗？很难说/取决于情况。所提出的解决方案是否严格劣于这样的LinkedHashMap？是的。 - misberner

如果我需要对 std::list<std::pair<K,V>> 进行排序，会发生什么？ - Kok How Teh

@KokHowTeh 这不是Java的LinkedHashMap所做的。如果这是您需要支持的用例，则需要使用不同的数据结构。 - Sergey Kalinichenko

如果我写std::list::iterator<std::pair<K,V>>，编译器会抱怨'list'不是一个类、命名空间或枚举。但如果我写std::list<std::pair<K,V>>::iterator，编译器就不会抱怨，然而后者似乎不起作用... - Adeesh Lemonickous

Answer 2

在键迭代的插入顺序中，可以使用平衡树来实现log（n）性能的契约。这比维护列表中的键更好，因为删除项需要n查找时间。我的口头禅是不要把你查找的东西放在列表中。如果它不必排序，请使用哈希。如果应该排序，请使用平衡树。如果你要做的全部工作就是迭代，那么列表就可以了。 在c ++中，这将是std :: map ，其中键是项目引用，值是插入顺序，使用红黑树对键进行排序。请参阅：STL中是否有排序的容器

- zettix

---

从LinkedHashMap中删除键是常数时间，而不是线性时间。为了使其工作，哈希映射条目必须维护对应的链接列表条目的引用。 - divegeek

Answer 3

这是我的做法：

    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

添加对象 id：

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

要删除一个对象的 id：

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

要从特定对象id开始检索最近的size个对象：

    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;

- Kok How Teh