I know hash_set
is non-standard and unordered_set
is standard. However, I am wondering, performance wise, what is the difference between the two? Why do they exist separately?
std::unordered_set is an STL container and its introduced in C++11. It provides a functionality of a Set i.e. it can contains the unique elements only. unordered_set stores the elements internally using a Hash Table.
Set is an ordered sequence of unique keys whereas unordered_set is a set in which key can be stored in any order, so unordered. Set is implemented as a balanced tree structure that is why it is possible to maintain order between the elements (by specific tree traversal).
For a small number of elements, lookups in a set might be faster than lookups in an unordered_set . Even though many operations are faster in the average case for unordered_set , they are often guaranteed to have better worst case complexities for set (for example insert ).
Two unordered_sets are equal if they have the same number of elements and the elements in one container are a permutation of the elements in the other container.
The complexity requirements for the unordered_
-containers set out by the C++ standard essentially don't leave much room for the implementation, which has to be some sort of hash table. The standard was written in full awareness that those data structures had already been deployed by most vendors as an extension.
Compiler vendors would typically call those containers "hash map" or "hash set", which is what you're probably referring to (there is no literal std::hash_set
in the standard, but I think there's one in GCC in a separate namespace, and similarly for other compilers).
When the new standard was written, the authors wanted to avoid possible confusion with existing extension libraries, so they went for a name that reflects the typical C++ mindset: say what it is, not how it's implemented. The unordered containers are, well, unordered. That means you get less from them compared to the ordered containers, but this diminished utility affords you more efficient access.
Implementation-wise, hash_set, Boost-unordered, TR1-unordered and C++11-unordered will be very similar, if not identical.
Regarding the question "are they the same thing" from the subject line: based on my experience of upgrading code from __gnu_cxx::hash_set to std::unordered_set, they are almost, but not exactly, the same thing.
The difference that I ran into is that iterating through __gnu_cxx::hash_set returned the items in what appeared to be the original order of insertion, whereas std::unordered_set would not. So as the name implies, one cannot rely on an iterator to return the items in any particular order when iterating though the entire std::unordered_set.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With