C++ 中是否存在链接哈希集? [英] Is there a linked hash set in C++?

问题描述

Java 有一个 LinkedHashSet，它是一个带有可预测的迭代顺序.C++ 中最接近的可用数据结构是什么?

Java has a LinkedHashSet, which is a set with a predictable iteration order. What is the closest available data structure in C++?

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

Currently I'm duplicating my data by using both a set and a vector. I insert my data into the set. If the data inserted successfully (meaning data was not already present in the set), then I push_back into the vector. When I iterate through the data, I use the vector.

推荐答案

如果你能用，那么一个Boost.MultiIndex 与 sequenced 和 hashed_unique 索引是相同的数据结构 LinkedHashSet.

If you can use it, then a Boost.MultiIndex with sequenced and hashed_unique indexes is the same data structure as LinkedHashSet.

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

Failing that, keep an unordered_set (or hash_set, if that's what your implementation provides) of some type with a list node in it, and handle the sequential order yourself using that list node.

您当前正在做的事情(set 和 vector)的问题是:

The problems with what you're currently doing (set and vector) are:

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

• Two copies of the data (might be a problem when the data type is large, and it means that your two different iterations return references to different objects, albeit with the same values. This would be a problem if someone wrote some code that compared the addresses of the "same" elements obtained in the two different ways, expecting the addresses to be equal, or if your objects have mutable data members that are ignored by the order comparison, and someone writes code that expects to mutate via lookup and see changes when iterating in sequence).
• Unlike LinkedHashSet, there is no fast way to remove an element in the middle of the sequence. And if you want to remove by value rather than by position, then you have to search the vector for the value to remove.
• set has different performance characteristics from a hash set.

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

If you don't care about any of those things, then what you have is probably fine. If duplication is the only problem then you could consider keeping a vector of pointers to the elements in the set, instead of a vector of duplicates.

这篇关于C++ 中是否存在链接哈希集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！