c++中map与unordered_map

2022-03-16 本文已影响0人九楼记

map与unordered_map

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