std::hash_set vs std::unordered_set, are they the same thing?
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?
Answer
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.