map与unordered_map区别

map

头文件 #include<map>
内部基于红黑树实现

红黑树

红黑树是一种自平衡的二叉查找树

性质:
1.每个节点要么是黑色，要么是红色
2.根节点黑色
3.每个叶子节点是黑色
4.每个红色节点是黑色
5.任意一节点到每个叶子节点的路径都包含数量相同的黑节点

自平衡：
1.左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
2.右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
3.变色：结点的颜色由红变黑或由黑变红。

查找
与二叉查找树相同

插入：

删除：

红黑树部分参考文章

unordered_map

头文件 #include<unordered_map>
内部基于哈希表实现

哈希表

通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)

对比

map:

优势：
1.有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
2.红黑树，内部实现一个红黑书使得map的很多操作在logn的时间复杂度下就可以实现，因此效率非常的高

劣势：
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

unordered_map：

优势：
因为内部实现了哈希表，因此其查找速度非常的快

劣势：
哈希表的建立比较耗费时间

对于有顺序要求的问题，使用map；
对于查找问题，使用unordered_map。

对比参考文章

map排序

key值排序

上文说到map本身是有序的，默认是less，即按照key值从小到大

如果对map排序，按照key值从大到小，使用greater，定义时直接指定

map<string,int,greater<type> >

value值排序

STL中本身有sort函数进行排序，但是sort只能对线性容器进行排序（vector, list, deque）, 因此采用将map键值对转移给线性容器再进行排序

首先重写cmp函数
注意加入static
按照需求，从大到小写>，从小到大写<

static int cmp(const pair<string, int>& x, const pair<string, int>& y)  
{  
    return x.second > y.second;  
}  

然后写按值排序函数

void sortMapByValue(map<string, int>& tMap,vector<pair<string, int> >& tVector)  
{  
    for (map<string, int>::iterator curr = tMap.begin(); curr != tMap.end(); curr++)   
        tVector.push_back(make_pair(curr->first, curr->second));    
   
    sort(tVector.begin(), tVector.end(), cmp);  
}

最后要注意的一点是，排序后的结果存储在tVector内，从tVector访问结果，而不是map
排序部分参考