关于C++中map的使用

map简介

map是一种以键值对的形式来存储元素的结构，并且也提供相应的成员函数来协助高效的插入，查询和删除键值对，除了map之外，还有一个名为unordered_map的结构，这两者有什么样的区别呢？

引用的头文件

map : #include<map>
unordered_map : #include<unordered_map>

存储结构

map是将元素存储在一个平衡二叉树中，因此元素是有序存储的
unordered_map是将元素存储在一个哈希表中，正如其名字一样，他并不是有序存储的

内存使用

因为需要额外的内存来存储哈希表，因此unordered_map比map更占用内存

优缺点以及适用处

map
优点：
有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作树，内部实现一个树使得map的很多操作在logn的时间复杂度下就可以实现，因此效率非常的高
缺点：
空间占用率高，因为map内部实现了树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，使得每一个节点都占用大量的空间
适用处：
对于那些有顺序要求的问题，用map会更高效一些
unordered_map
优点：
因为内部实现了哈希表，因此其查找速度非常的快
缺点：
哈希表的建立比较耗费时间
适用处：
对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

但以上的内容并不是绝对的，下面通过一道leetcode上的题来解释：

13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:
Input: "III"
Output: 3

Example 2:
Input: "IV"
Output: 4

Example 3:
Input: "IX"
Output: 9

Example 4:
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

这道题我们就可以借助map来进行实现，具体代码实现如下：

class Solution {
public:
    int romanToInt(string s) {
 
        map<char, int> romanumber;
        romanumber['I'] = 1;
        romanumber['V'] = 5;
        romanumber['X'] = 10;
        romanumber['L'] = 50;
        romanumber['C'] = 100;
        romanumber['D'] = 500;
        romanumber['M'] = 1000;
        int rlt = romanumber[s[s.size() - 1]];
        for (int i = s.size() - 2; i >= 0; i--)
        {
            if(romanumber[s[i]] >= romanumber[s[i+1]])
            {
                rlt += romanumber[s[i]];
            }
            else
            {
                rlt -= romanumber[s[i]];
            }
        }

        return rlt;
    }
};

在这里我们使用的是map来进行存储的，之后我们发现运行的效率为

使用map运行的结果效率

我们可以将map改成unordered_map再进行一次运行，其余代码是不用进行改动的，结果如图所示：

使用unordered_map运行的结果效率

因此在选用的时候还是要考虑清楚的啊！