c++ - C++ 中是否存在链接哈希集？

Question

Java 有一个LinkedHashSet，它是一个具有可预测迭代顺序的集合。C++ 中最接近的可用数据结构是什么？

目前我正在使用集合和向量来复制我的数据。我将我的数据插入到集合中。如果数据插入成功（意味着数据集中不存在），那么我 push_back 进入向量。当我遍历数据时，我使用向量。

Answer 1

如果可以使用它，那么带有和索引的Boost.MultiIndex与.sequencedhashed_uniqueLinkedHashSet

如果做不到这一点，请保留某种类型的unordered_set（或者hash_set，如果这是您的实现所提供的），其中包含一个列表节点，并使用该列表节点自己处理顺序。

您当前正在做的事情（set和vector）的问题是：

• 数据的两个副本（当数据类型很大时可能会出现问题，这意味着您的两个不同的迭代返回对不同对象的引用，尽管具有相同的值。如果有人编写了一些比较以两种不同方式获得的“相同”元素的地址，期望地址相等，或者如果您的对象具有mutable被顺序比较忽略的数据成员，并且有人编写的代码期望通过查找发生变异并看到更改时依次迭代）。
• 与 不同LinkedHashSet的是，没有快速的方法可以删除序列中间的元素。如果要按值而不是按位置删除，则必须在向量中搜索要删除的值。
• set具有与散列集不同的性能特征。

如果您不关心这些事情中的任何一个，那么您所拥有的可能就很好。如果重复是唯一的问题，那么您可以考虑保留指向集合中元素的指针向量，而不是重复向量。

Answer 2

LinkedHashSet要在 C++ 中从 Java复制，我认为您将需要两个 vanilla std::map（请注意，您将得到LinkedTreeSet而不是真正的LinkedHashSet，而不是得到 O(log n) 用于插入和删除）才能工作。

• 一种使用实际值作为键和插入顺序（通常是 int 或 long int）作为值。
• 另一个是相反的，使用插入顺序作为键，实际值作为值。

当您要插入时，您std::map::find首先使用std::map以确保其中不存在相同的对象。

• 如果已经存在，则忽略新的。
• 如果没有，则将此对象与递增的插入顺序映射到std::map我之前提到的两者。

当您要按插入顺序遍历它时，您将遍历第二个std::map，因为它将按插入顺序排序（任何属于std::mapor的std::set内容都会自动排序）。

当您要从中删除一个元素时，您可以使用它std::map::find来获取插入顺序。使用此插入顺序从第二个元素中删除元素std::map并从第一个元素中删除对象。

请注意，此解决方案并不完美，如果您打算长期使用此解决方案，则需要在删除一定数量后“压缩”插入订单，因为您最终会用完插入订单（2 ^32 个索引用于 unsigned int 或 2^64 个索引用于 unsigned long long int）。为此，您需要将所有“值”对象放入向量中，清除两个映射中的所有值，然后将向量中的值重新插入两个映射。此过程需要 O(nlogn) 时间。

如果您使用的是 C++11，则可以将第一个替换为std::map以std::unordered_map提高效率，但您将无法用它替换第二个。原因是std::unordered map使用哈希码进行索引，因此在这种情况下无法可靠地对索引进行排序。

Answer 3

您可能想知道 std::map 不会像“null”查找时间那样为您提供任何类型的 (log n)。并且使用 std::tr1::unordered 是有风险的业务，因为它会破坏任何排序以获得恒定的查找时间。

尝试 bash 一个 boost 多索引容器以更自由地使用它。

Answer 4

除了使用（相当于Java的HashSet）和（双向链表）之外，您描述组合的方式std::set听起来std::vector像您应该做的事情。您还可以使用将键（用于查找）与迭代器一起存储到列表中，以查找您存储的实际对象（如果键与对象不同（或仅其中一部分））。std::unordered_setstd::liststd::unordered_map

boost 库确实提供了许多此类容器和查找索引的组合。例如，这个具有快速查找示例的双向列表。