What is the difference between set and hashset in C++ STL?

c++ performance stl set hashset
kal picture kal · Mar 25, 2010 · Viewed 46k times · Source

When should I choose one over the other? Are there any pointers that you would recommend for using the right STL containers?

Answer

Mark Ransom picture Mark Ransom · Mar 25, 2010

hash_set is an extension that is not part of the C++ standard. Lookups should be O(1) rather than O(log n) for set, so it will be faster in most circumstances.

Another difference will be seen when you iterate through the containers. set will deliver the contents in sorted order, while hash_set will be essentially random (Thanks Lou Franco).

Edit: The C++11 update to the C++ standard introduced unordered_set which should be preferred instead of hash_set. The performance will be similar and is guaranteed by the standard. The "unordered" in the name stresses that iterating it will produce results in no particular order.

Related questions

Is std::vector so much slower than plain arrays?

I've always thought it's the general wisdom that std::vector is "implemented as an array," blah blah blah. Today I went down and tested it, and it seems to be not so: Here's some test results: UseArray completed in 2.619 seconds …

Read More
Relative performance of std::vector vs. std::list vs. std::slist?

For a simple linked list in which random access to list elements is not a requirement, are there any significant advantages (performance or otherwise) to using std::list instead of std::vector? If backwards traversal is required, would it be …

Read More
Performance of qsort vs std::sort?

According Scott Meyers, in his Effective STL book - item 46. He claimed that std::sort is about 670% faster than std::qsort due to the fact of inline. I tested myself, and I saw that qsort is faster :( ! Could anyone help …

Read More