在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.

推荐答案

如果你可以使用它， http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html\"> Boost.MultiIndex 与排序和 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.

您当前正在做的问题（设置和向量）是：

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

• 可能是一个问题，当数据类型是大的，这意味着你的两个不同的迭代返回引用不同的对象，虽然有相同的值。这将是一个问题，如果有人写了一些代码比较以两种不同的方式获得的相同元素的地址，期望地址相等，或者如果您的对象具有可变数据成员被顺序比较忽略，并且有人编写代码，希望通过查找发生变化，并在按顺序迭代时查看更改）。


• 与 LinkedHashSet 不同，快速的方法来删除序列中间的元素。如果要按值而不是按位置删除，则必须在向量中搜索要删除的值。


• 设置具有与哈希集不同的性能特征。

• 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屋！