What is the time complexity of search, insert, and delete operations in std::unordered_map?

In std::unordered_map, search, insert, and delete operations have an amortized time complexity of O(1) on average. This is achieved by using a hash table, where access to elements occurs via the hash of the key.

However, in the worst case, when there are many collisions (for example, all keys hash to the same bucket), the time complexity can degrade to O(n), where n is the number of elements in the container.

Thus:

• Search: amortized O(1), worst case O(n)
• Insert: amortized O(1), worst case O(n)
• Delete: amortized O(1), worst case O(n)

To maintain high performance, it is important to choose a good hash function and, if necessary, increase the size of the hash table (rehashing).