Is there a linked hash set in C++?
c++, set
Solution
If you can use it, then a Boost.MultiIndex with `sequenced` and `hashed_unique` indexes is the same data structure as `LinkedHashSet`.
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:
- 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.
Problem
Java has a LinkedHashSet, which is a set with a predictable iteration order. What is the closest available data structure in C++? 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.