C++ map和unordered_map的区别

C++ map和unordered_map的区别

映射和无序映射之间存在巨大差异。只有我们清楚知道两者的内部工作原理,才能决定如何选择适合的那一个使用。

不同之处 :

比较项 map unordered_map
排序 递增顺序(默认) 无排序
执行 自平衡BST(类似红黑树) Hash Table
搜索时间 log(n) O(1) -> 平均, O(n) -> 最坏情况
插入时间 log(n) + 重新平衡 与搜索时间相同
删除时间 log(n) + 重新平衡 与搜索时间相同

使用 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
                << " : "\n                << i->second << 'n';
    }
}

运行结果:

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

使用 std::unordered_map

有以下情况时,可以考虑使用 std::unordered_map

  • 需要保留一些数据的计数(示例 – 字符串)并且不需要排序。
  • 需要单元素访问,即没有遍历。
// 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
                << " : "\n                << i->second << 'n';
    }
}

运行结果:

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程