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

For std::set (based on a balanced binary search tree):

• Insertion (insert of one element): O(log N)
• Deletion (erase of one element): O(log N)
• Search (find): O(log N)

For std::unordered_set (based on a hash table):

• Average:
  • Insertion (insert of one element): O(1)
  • Deletion (erase of one element): O(1)
  • Search (find): O(1)
• Worst case (with severe hash collisions):
  • Insertion (insert of one element): O(N)
  • Deletion (erase of one element): O(N)
  • Search (find): O(N)

Comparison table:

Operation	std::set	std::unordered_set (average)	std::unordered_set (worst case)
Insert single element	O(log N)	O(1)	O(N)
Remove single element	O(log N)	O(1)	O(N)
Search single element	O(log N)	O(1)	O(N)