STL源码剖析：map、multimap和unordered_map、unordered_multimap

map和multimap是由RB-tree构成的&＃xff0c;unordered_map和unordered_multimap是由Hashtable构成的

• 相同&＃xff1a;两者都是键-值对的集合&＃xff0c;关联容器的一种。两者中的元素都是pair&＃xff0c;同时拥有实值和键值。两者都不允许有两个相同的键值&＃xff08;实值可以相同&＃xff09;。两个的外部接口调用基本一致。
• 不同&＃xff1a;内部实现机理不同&＃xff0c;即map内部实现了一个红黑树&＃xff1b;unordered_map内部实现了一个哈希表。&＃xff08;两者的比较成为红黑树与哈希表的比较&＃xff09;。由于内部实现机理不同&＃xff08;底层实现&＃xff09;造成以下不同。
• map的有序性&＃xff1a;红黑树&＃xff08;非严格平衡二叉树&＃xff09;&＃xff0c;该结构具有自动排序的功能&＃xff0c;因此map内部的所有元素都是有序的。
• unordered_map的无序性&＃xff1a;哈希表不会根据key值大小进行排序&＃xff0c;存储时是根据key的hash值判断元素是否相同&＃xff0c;因此unordered_map内部元素是无序的。
• map的运行效率&＃xff1a;红黑树可以在O(log n)时间内做查找&＃xff0c;插入和删除&＃xff0c;这里的n是树中元素的数目。
• unordered_map的运行效率&＃xff1a;哈希表的查找的时间复杂度可达到O(1)
  unordered_map内存占用比map高。