Why would anyone use set instead of unordered_set?

Question

Unordered sets have to pay for their O(1) average access time in a few ways:

• set uses less memory than unordered_set to store the same number of elements.
• 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).
• That set sorts the elements is useful if you want to access them in order.
• You can lexicographically compare different sets with <, <=, > and >=. unordered_sets are not required to support these operations.

When, for someone who wants to iterate over the items of the set, the order matters.

Whenever you prefer a tree to a hash table.

For instance, hash tables are "O(n)" at worst case. O(1) is the average case. Trees are "O(log n)" at worst.

Use set when:

1. We need ordered data(distinct elements).
2. We would have to print/access the data (in sorted order).
3. We need predecessor/successor of elements.

Use unordered_set when:

1. We need to keep a set of distinct elements and no ordering is required.
2. We need single element access i.e. no traversal.

Examples:

set:

Input : 1, 8, 2, 5, 3, 9

Output : 1, 2, 3, 5, 8, 9

Unordered_set:

Input : 1, 8, 2, 5, 3, 9

Output : 9 3 1 8 2 5 (maybe this order, influenced by hash function)

Mainly difference :

Note:(in some case set is more convenient) for example using vector as key

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3 

The reason why vector<int> can be as key in set because vector override operator<.

But if you use unordered_set<vector<int>> you have to create a hash function for vector<int>, because vector does't have a hash function, so you have to define one like:

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

you can see that in some case unordered_set is more complicated.

Mainly cited from: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

g++ 6.4 stdlibc++ ordered vs unordered set benchmark

I benchmarked this dominant Linux C++ implementation to see the difference:

The full benchmark details and analysis have been given at: What is the underlying data structure of a STL set in C++? and I will not repeat them here.

"BST" means "tested with std::set and "hash map" means "tested with std::unordered_set. "Heap" is for std::priority_queue which I analyzed at: Heap vs Binary Search Tree (BST)

As a quick summary:

• the graph clearly shows that under these conditions, hashmap insertion were always a lot faster when there are more than 100k items, and the difference grows as the number of items increases

  The cost of this speed boost is that you are not able to efficiently traverse in order.

• the curves clearly suggest that ordered std::set is BST-based and std::unordered_set is hashmap based. In the reference answer, I further confirmed that by GDB step debugging the code.

Similar question for map vs unordered_map: Is there any advantage of using map over unordered_map in case of trivial keys?

Because std::set is part of Standard C++ and unordered_set isn't. C++0x is NOT a standard, and neither is Boost. For many of us, portability is essential, and that means sticking to the standard.

Consider sweepline algorithms. These algorithms would fail utterly with hash tables, but work beautifully with balanced trees. To give you a concrete example of a sweepline algorithm consider fortune's algorithm. http://en.wikipedia.org/wiki/Fortune%27s_algorithm