Is there a related hash in C ++?

Question

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

I am currently duplicating my data using both a set and a vector. I insert my data into a set. If the data is inserted successfully (this means that the data has not yet been present in the set), I click on the vector. When I repeat the data, I use a vector.

Answer 1

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

If this fails, save the unordered_set (or hash_set , if that is what your implementation provides) of some type, in the node list, and handle the sequential order yourself using this node list.

Problems with what you are doing now ( set and vector ):

• Two copies of the data (it can be a problem when the data type is large, and this means that your two different iterations return references to different objects, albeit with the same values. It would be a problem if someone wrote code that compared the addresses " of the same "elements obtained in two different ways, expecting that the addresses will be equal, or if your objects have members of mutable data that are ignored by comparing the order, and someone writes code that expects to mutate by searching and viewing the changes when repeated in sequentially sti).
• Unlike LinkedHashSet , there is no quick way to delete an element in the middle of a sequence. And if you want to delete by value, and not by position, you need to look for a vector for the value to be deleted.
• set has different performance characteristics from a set of hashes.

If you don't care about any of these things, then what you have is probably fine. If duplication is the only problem, you might consider moving the vector of pointers to elements in the set instead of the duplicate vector.

Answer 2

To copy a LinkedHashSet from JAVA to C ++, I think you will need two vanilla std::map (note that instead you get a LinkedTreeSet instead of a real LinkedHashSet, which will get O (log n) for insertion and deletion) for this to work .

• The actual value as the key and the insertion order (usually int or long int) are used as the value.
• Others are inverse, the insertion order is used as the value and value as the value.

When you are going to embed, you use std::map::find in the first std::map to make sure that it does not have an identical object.

• If it already exists, ignore the new one.
• If this is not the case, you map this object to the incremental insertion order on both std::map mentioned earlier.

When you are going to iterate over the insertion order, you repeat the second std::map , since it will be sorted by the insertion order (everything that falls into std::map or std::set will be sorted automatically).

When you are about to remove an element from it, use std::map::find to get the insertion order. Using this insertion order, remove the element from the second std::map and remove the object from the first.

Please note that this solution is not ideal, if you plan to use it on a long-term basis , you will need to “shrink” the insertion order after a certain number of paragraphs, since you will end the insertion order (indexes 2 ^ 32 for unsigned int or 2 ^ 64 indexes for unsigned long long int). To do this, you will need to put all the “value” objects in the vector, clear all the values ​​from both cards, and then reinsert the values ​​from the vector back into both cards. This procedure takes O (nlogn) time.

If you use C ++ 11, you can replace the first std::map with std::unordered_map to increase efficiency, however you cannot replace it with the second. The reason is that the std::unordered map uses a hash code for indexing so that the index cannot be reliably sorted in this situation.

Answer 3

You might know that std :: map does not give you any kind (log n), as in the "zero" search time. And using std :: tr1 :: unordered is a risky business because it destroys any ordering to get a constant search time.

Try a bash container with multiple indexes for easier access to it.

Answer 4

As you described, your combination of std::set and std::vector sounds the way you should do, except using std::unordered_set (equivalent to Java HashSet) and std::list (doubly linked list). You can also use std::unordered_map to store the key (for searching) along with an iterator in a list where you can find the actual objects that you store (if the keys are different from the objects (or only part of them)).

The acceleration library provides several of these types of combinations of containers and search indexes. For example, this bidirectional list with a quick search example .