Understanding the Difference Between `set` and `unordered_set` in C++

In C++, two commonly used containers from the Standard Template Library (STL) are `set` and `unordered_set`. Both are used for storing unique elements, but they differ in their internal implementation and properties. This article aims to explore these differences with technical explanations, examples, and comparative analyses.

`set` in C++

`set` is an associative container that maintains a collection of unique elements following a specific order. This ordering allows `set` containers to support log-time (on average) complexity for various operations, such as insertion, deletion, and searching.

Key Characteristics

• Ordered: The elements in a `set` are always sorted according to some sorting criterion, typically in ascending order. This is because `set` uses a balanced binary search tree, commonly a Red-Black Tree, to store its elements.
• Iterators: Iterators provided by `set` are bi-directional, allowing traversal in both forward and backward directions.
• Complexity: Searching, insertion, and deletion operations have a time complexity of $O(\log n)$.

Example

• Unordered: Elements are stored in no particular order. `unordered_set` uses a hash table internally, where the position of each element is determined using a hash function.
• Iterators: Iterators are forward-only, meaning they can only traverse in one direction.
• Complexity: Average time complexity for searching, insertion, and deletion is $O(1)$. However, in the worst case, these operations can degrade to $O(n)$ due to hash collisions.
• Choosing Between `set` and `unordered_set`: The decision to use either `set` or `unordered_set` largely depends on the specific requirements of the application. If you need fast search, insertion, and deletion operations without concern for element order, `unordered_set` is suitable. However, if an ordered set of unique elements is desired, `set` is the preferred option.
• Hash Function: The efficiency of `unordered_set` is highly reliant on the quality of the hash function used. A poor hash function may lead to many collisions, thus degrading performance significantly.
• Customization: Both containers provide mechanisms for customization. For instance, `unordered_set` allows for custom hash functions, and `set` can be parameterized with custom comparators.