内部实现机理

map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。
unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

leetcode提交代码效率对比

map实现

int romanToInt(string s) {
    map<char, int> map;
    map['I'] = 1;
    map['V'] = 5;
    map['X'] = 10;
    map['L'] = 50;
    map['C'] = 100;
    map['D'] = 500;
    map['M'] = 1000;

    int sum = 0;
    for(size_t i = 0; i < s.size(); ++i){
        if (map[s[i]] < map[s[i+1]]){
            sum = sum + map[s[i+1]] - map[s[i]];
            ++i;
        }
        else{
            sum += map[s[i]];
        }
    }

    map.clear();
    return sum;
}

评估

1 2	Runtime: 40 ms, faster than 98.36% of C++ online submissions for Roman to Integer. Memory Usage: 11.4 MB, less than 97.68% of C++ online submissions for Roman to Integer.

unorder_map实现

代码

static std::unordered_map<char,int> umap = {
    {'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}
};

class Solution {
public:
    int romanToInt(string s) {
        int sum = 0;
        for(size_t i = 0; i < s.size(); ++i){
            if (umap[s[i]] < umap[s[i+1]]){
                sum = sum + umap[s[i+1]] - umap[s[i]];
                ++i;
            }
            else{
                sum += umap[s[i]];
            }
        }
        return sum;
    }
};

评估

1 2	Runtime: 28 ms, faster than 100.00% of C++ online submissions for Roman to Integer. Memory Usage: 8.7 MB, less than 98.55% of C++ online submissions for Roman to Integer.

总结优缺点以及适用处

map

优点：

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

内部实现机理

leetcode提交代码效率对比

map实现

评估

unorder_map实现

代码

评估

总结优缺点以及适用处

map

优点：

缺点：

unordered_map

优点：

缺点：