what is the difference between set and unordered_set in C++?

by

I think you’ve generally answered your own question, however, this:

Not as compact as tree. (for practical purposes load factors is never 1)

is not necessarily true. Each node of a tree (we’ll assume it’s a red-black tree) for a type T utilizes space that is equal to at least 2 * pointer_size + sizeof(T) + sizeof(bool). This may be 3 * pointer size depending on whether the tree contains a parent pointer for each tree node.

Compare this to a hash-map: there will be wasted array space for each hash map due to the fact that load factor < 1 as you’ve said. However, assuming the hash map uses singly linked lists for chaining (and really, there’s no real reason not to), each element inserted take only sizeof(T) + pointer size.

Note that this analysis ignores any overhead which may come from extra space used by alignment.

For any element T which has a small size (so, any basic type), the size of the pointers and other overhead dominates. At a load factor of > 0.5 (for example) the std::unordered_set may indeed use up less memory than the equivalent std::set.

The other big missing point is the fact that iterating through a std::set is guaranteed to produce an ordering from smallest to largest, based on the given comparison function, while iterating through an std::unordered_set will return the values in a “random” order.

More Related Contents:

  1. TMP: how to generalize a Cartesian Product of Vectors?
  2. Why would anyone use set instead of unordered_set?
  3. Program stopped working, when tried to run
  4. How to get the maximum number after erasing n digits from the number [closed]
  5. Sorting zipped (locked) containers in C++ using boost or the STL
  6. LRU cache design
  7. Easiest way of using min priority queue with key update in C++
  8. Order Statistic Tree in C++
  9. C++: Using for loop I need to take infinite values of a point using arrays. How can I take values of point [ ] until 2 points of are equal
  10. Start thread with member function
  11. Is gcc 4.8 or earlier buggy about regular expressions?
  12. C++0x has no semaphores? How to synchronize threads?
  13. How well is Unicode supported in C++11?
  14. Resolving ambiguous overload on function pointer and std::function for a lambda using + (unary plus)
  15. Looking for C++ STL-like vector class but using stack storage
  16. trailing return type using decltype with a variadic template function
  17. regex replace with callback in c++11?
  18. Writing Universal memoization function in C++11
  19. How would you implement your own reader/writer lock in C++11?
  20. How to store extremely large numbers?
  21. Is it possible to determine if a type is a scoped enumeration type?
  22. Is there actually a reason why overloaded && and || don’t short circuit?
  23. The intersection of two sorted arrays
  24. Waiting for multiple futures?
  25. Lambda functions as base classes
  26. ISO C++ standard draft
  27. C++ regex_match not working
  28. std::thread calling method of class [duplicate]
  29. How can I test whether a number is a power of 2?
  30. memcpy/memmove to a union member, does this set the ‘active’ member?

Leave a Comment