What is the asymptotic complexity of operations for the unordered_set and set containers in C++?

Asymptotic operation complexities for std::unordered_set and std::set in C++17:

Operation	std::unordered_set (average case)	std::unordered_set (worst case)	std::set
Insertion (insert)	O(1)	O(n)	O(log n)
Deletion (erase)	O(1)	O(n)	O(log n)
Search (find)	O(1)	O(n)	O(log n)
Access	Not applicable	Not applicable	O(log n) (iterator)

• std::unordered_set is based on a hash table. The average case complexity of O(1) is achieved with a good hash function and no significant collisions. The worst case O(n) occurs with severe collisions (e.g., all elements hash to the same bucket) or inefficient element distribution.
• std::set is based on a balanced binary search tree (usually a red-black tree). The O(log n) complexity is due to the logarithmic height of the tree, where n is the number of elements.

Important notes:

• Worst-case for insertions and deletions in std::unordered_set may involve rehashing, which, if necessary, involves rebuilding the entire table with O(n) complexity.
• Access operation for std::set via iterator also has logarithmic complexity.

#include <unordered_set> // For unordered_set
#include <set>           // For set

// Example usage of std::unordered_set
std::unordered_set<int> uset;
uset.insert(10); // Average O(1), Worst O(n)
uset.find(10);   // Average O(1), Worst O(n)
uset.erase(10);  // Average O(1), Worst O(n)

// Example usage of std::set
std::set<int> s;
s.insert(10); // O(log n)
s.find(10);   // O(log n)
s.erase(10);  // O(log n)