C++中map与unordered_map的对比

当涉及到效率时，地图和无序地图之间存在着巨大的差异。

我们必须了解两者的内部运作，才能决定使用哪一种。

区别:

                  | map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |  

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search

Deletion time   | log(n) + Rebalance  | Same as search

当使用std::map

• 您需要有序的数据。
• 您必须(按顺序)打印/访问数据。
• 您需要元素的前身/继承者。

// CPP program to demonstrate use of std::map
#include <bits/stdc++.h>
 
int main()
{
    // Ordered map
    std::map<int, int> order;
 
    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;
 
    // Iterating the map and
    // printing ordered values
    for (auto i = order.begin(); i
         != order.end(); i++) {
        std::cout << i->first
                  << " : "
                  << i->second << '\n';
    }
}

输出：

1 : 1
3 : 5
5 : 10
20 : 100

使用std:: unordered_map时

• 您需要对一些数据(示例-字符串)进行计数，并且不需要排序。
• 您需要单个元素访问i.e。没有遍历。

// CPP program to demonstrate use of
// std::unordered_map
#include <bits/stdc++.h>
 
int main()
{
    // Unordered map
    std::unordered_map<int, int> order;
 
    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;
 
    // Iterating the map and
    // printing unordered values
    for (auto i = order.begin();
         i != order.end(); i++)
    {
        std::cout << i->first
                  << " : "
                  << i->second << '\n';
    }
}

输出：

1 : 1
20 : 100
5 : 10
3 : 5

让我们用表格的形式来看看它们的区别: