Is std :: unordered_set continuous (e.g. std :: vector)?

Question

I store pointers in std :: unordered_set because I do not want to duplicate (I delete pointers in the collection, so if there is duplicate, I will try to delete the already deleted pointer). I am obsessed with these sets, and since I know that std :: vector is the fastest container for a loop (continuous memory), I wondered if std :: unordered_set does the same.

If it is not, will use std :: vector and check if the pointer was deleted faster?

Answer 1

Is std::unordered_set contiguous?

The exact implementation of containers is not described in detail by the standard ... however, the standard prescribes a series of actions that limit the actual presentation.

For example, std::unordered_set requires stable memory: the link to the / address of the element is valid even when adding / removing other elements.

The only way to achieve this is to select elements more or less independently. This cannot be achieved with a continuous distribution of memory, since such a distribution will necessarily be limited and, thus, can be outgrown without the possibility of redistributing elements in a larger fragment.

Answer 2

No, this is not continuous memory, but it is still very fast thanks to the hash map.

Edit: fast for random access, if you are mostly looping, you should think of a different container, I think.

Edit2: And you need a profile to know whether to think about another container. (Maybe you should optimize somewhere else ... maybe).

Answer 3

The fact that the following member functions are offered by std::unordered_map suggests that it is based on a hash table, possibly a separate chain with linked lists .

 bucket_count, hash_function, load_factor, max_load_count, rehash 

Whether the elements are adjacent or not depends on the distributor. The defaults for unordered_map and list do not allocate items in contiguous memory. The memory for each item is allocated during its insertion.

However, you can provide a custom allocator (such as a pool manager ) that can allocate items from a pre-allocated memory pool. Still, logically adjacent elements in the data structure may not be physically close to the memory.

Thus, if going through all the elements is the most common operation, then unordered_map might not be the best solution. Performing dominant use cases through the profiler for all competing solutions will show the best solution.

In addition to this, unordered_map not the best choice for a loop for another reason. Pay attention to the word " unordered " in the name, it conveys this value - unlike list , vector or map - the order of the elements . For example, a member of the rehash function can change the relative order of elements. In fact, rehashes is automatically performed by the container when its load factor exceeds max_load_factor during any operation.

Answer 4

std :: unordered_set is considered a hash map container, so we can assume that it has a slight performance limit when compared to std :: vector.

But I think you should check the actual profiling result if access to unordered_set is a real access point.

If the STL implementation that you use is reasonable, it should provide a vector similar to the one for the pointer key or int type. If true, an unordered_set specialized for a pointer type will behave just like an auto-growing / shrinking vector, and the performance difference will not be noticeable.