Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 880
kal Avatar asked Mar 25 '10 18:03

kal


People also ask

What is difference between set and HashSet?

A Set is a generic set of values with no duplicate elements. A TreeSet is a set where the elements are sorted. A HashSet is a set where the elements are not sorted or ordered.

What is set in STL?

Sets are the containers in C++ STL for storing elements in a given order. The elements of a set must be unique.

Is C++ set a HashSet?

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.

Which is faster set or unordered set?

unordered_set time was better than set (15494846) : 93<155. Only with adding this line: s.


1 Answers

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.

like image 183
Mark Ransom Avatar answered Oct 12 '22 13:10

Mark Ransom