在C ++中等效的LinkedHashmap？

Question

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

我试图使用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>>>地图，以便通过键快速查找项目来实现：

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

Answer 2

可以使用用于log（n）性能的平衡树来实现密钥迭代的插入顺序契约。这比维护列表中的键更好，因为项目删除需要n个查找时间。我的口头禅从来没有把你在列表中查找的内容。如果不必排序，请使用哈希。如果应该排序，请使用平衡树。如果您要做的就是迭代，那么列表就可以了。在c ++中，这将是std::map，其中键是项目引用，值是插入顺序，键是使用红黑树排序的。见：Is there a sorted container in STL

Answer 3

无序映射或C ++中内置的任何其他STL方法都不能提供与LinkedHashMap相同的顺序，尽管您可以维护插入的顺序并访问unordered_map使用维护的顺序。

下面的图片只是为了展示unordered_map的行为方式。它没有订单。

Map是RB树，如果使用了迭代器，它会给出一个排序顺序。

因此，没有具体的解决方案。