等价于 C++ 中的 LinkedHashmap？

Question

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

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

Answer 1

C++ 不提供具有模仿 Java 的 LinkedHashMap<K,V> 行为的集合模板，因此您需要从映射中单独维护顺序。

这可以通过将数据保存在 std::list<std::pair<K,V>> 中并保存一个单独的 std::unordered_map<k,std::list::iterator<std::pair<K,V>>> 映射来实现，以便通过按键快速 look-up 项目：

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

Answer 2

密钥迭代的插入顺序契约可以通过平衡树实现 log(n) 性能。这比在列表中维护键要好，因为删除项需要 n 次查找时间。我的口头禅是永远不要把你查找的东西放在列表中。如果不需要排序，请使用哈希。如果应该排序，请使用平衡树。如果您要做的只是迭代，那么列表就可以了。在 C++ 中，这将是 std::map，其中键是项目引用，值是插入顺序，键使用 red-black 树排序。参见：Is there a sorted container in STL

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;

等价于 C++ 中的 LinkedHashmap？

equivalent LinkedHashmap in C++?

c++

unordered-map

linkedhashmap