Is unordered_map slower than map?

Let’s talk about the conclusion first: unordered_map does not maintain the order of keys, so elements cannot be accessed in order. Therefore, if you need to traverse the table, if you choose unordered_map, it will definitely be slower than map.

1. Data structure and underlying implementation

unordered_map:based onHash tableaccomplish.
- Advantages: On average, the time complexity of insertion, search, and deletion operations is O(1)O(1)O(1).
- Disadvantages: In the worst case, the time complexity may degenerate to O(n)O(n)O(n) (when hash collisions are severe).
- Unordered storage, cannot be sorted by key.
map:based onRed-black tree (self-balancing binary search tree)accomplish.
- Advantages: The time complexity of insertion, search and delete operations is always O(log⁡n)O(\log n)O(logn).
- Disadvantages: The constant factor is large due to the need to maintain the balance of the tree.
- Sort by key and support ordered traversal.

2. Insertion and search performance

unordered_mapAdvantages: In most cases,unordered_mapInsertion and lookup performance is better thanmap, because its average time complexity is O(1)O(1)O(1).
mapDisadvantages：mapThe insertion and search performance are slightly slower, with a time complexity of O(log⁡n)O(\log n)O(logn).

Exceptions：

Hash collision is serious:ifunordered_mapIf the hash function is poorly designed or the data distribution is extreme (such as a large number of identical hash values), the performance may degrade to O(n)O(n)O(n).
small data: For cases where the data size is small,mapperformance may be better thanunordered_map, because the red-black tree implementation has less overhead.

3. Memory usage

unordered_mapshortcoming: Since hash tables require additional storage space (such as empty slots and linked list nodes),unordered_mapusually thanmapTake up more memory.
mapAdvantages：mapIt is a tree-based implementation and takes up relatively little memory.

4. Sequential access

unordered_mapshortcoming：unordered_mapThe order of keys is not maintained, so elements cannot be accessed sequentially.
mapAdvantages：mapAutomatic key ascending order (or specified comparison function) maintains element order and supports ordered traversal.

5. Impact on iterators during insertion and deletion

unordered_map: When a rehash operation of the hash table occurs, all iterators will be invalidated.
map: Inserting and deleting elements will only affect the iterator at the relevant position, and other iterators will not be invalidated.

6. Applicable scenarios

scene	It is recommended to use containers	reason
Quick find/insert operations	`unordered_map`	The average time complexity is O(1)O(1)O(1).
Data needs to be sorted by key	`map`	Supports ordered traversal.
Data size is small	`map`	The red-black tree constant factor is small.
Limited memory	`map`	`unordered_map`It takes up a lot of memory.
Poor hash function performance or poor data distribution	`map`	`unordered_map`Performance degradation is obvious.

7.Examples

B. Gorilla and the Exam
Code:


 #include 
 #include 
 #include 
 using namespace std;

 int main() {
     int t;
     scanf("%d", &t);
     while (t--) {
         int n, k;
         scanf("%d %d", &n, &k);

         // Count frequency
         map times;
         for (int i = 0; i < n; i++) {
             int c;
             scanf("%d", &c);
             times[c]++;
         }

         //Extract frequencies and sort them
         vector freq;
         for (auto it : times) {
             freq.push_back();
         }
         sort((), ());

         // Calculate the remaining categories after removing the smallest k times
         int m = ();
         for (int i = 0; i < m; i++) {
             if (freq[i] > k) {
                 printf("%d\n", m - i);
                 goto next_case;
             }
             k -= freq[i];
         }
         printf("1\n");
     next_case:;
     }
     return 0;
 }

If this code is changed to unordered_map, it will time out. Interested students can submit it and try it!

Summarize

If you need fast insertion, deletion, and lookup operations and don't care about order,Preferenceunordered_map。
If you need to sort by key or may encounter hash collision issues, selectmap。
If memory usage is sensitive, choosemap。