文章目录
- 1 map与unordered_map区别及使用
- 2 set与unordered_set区别(与map类似):
- 3 vector和list的区别(随机存取、插入删除)
勐腊网站制作公司哪家好,找
创新互联!从网页设计、网站建设、微信开发、APP开发、
自适应网站建设等网站项目制作,到程序开发,运营维护。
创新互联于2013年创立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选
创新互联。
1 map与unordered_map区别及使用
需要引入的头文件不同:
- map:
#include
- unordered_map:
#include
内部实现机理不同:
map:
- map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树)
- 红黑树具有自动排序的功能,因此map内部的所有元素都是有序的
- map中的元素是按照二叉搜索树(又名二叉查找树、二叉排序树,特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来。
unordered_map:
- unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到
O(1)
,其在海量数据处理中有着广泛应用)。 - 因此,其元素的排列顺序是无序的。
优缺点以及适用处:
map:
- 优点:有序性,这是map结构大的优点,其元素的有序性在很多应用中都会简化很多的操作,内部实现一个红黑树使得map的很多操作在
log(n)
的时间复杂度下就可以实现,因此效率非常的高 - 缺点: 空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间
- 适用处:对于那些有顺序要求的问题,用map会更高效一些
unordered_map:
- 优点: 因为内部实现了哈希表,因此其查找速度非常的快
- 缺点: 哈希表的建立比较耗费时间
- 适用处:对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map
总结:
- 内存占有率的问题就转化成
红黑树 VS hash表
, 还是unordered_map占用的内存要高。但是unordered_map执行效率要比map高很多 - 对于unordered_map或unordered_set容器,其遍历顺序与创建该容器时输入的顺序不一定相同,因为遍历是按照哈希表从前往后依次遍历的
2 set与unordered_set区别(与map类似):
- set:基于红黑树实现,红黑树具有自动排序的功能,因此set内部所有的数据,在任何时候,都是有序的。
- unordered_set:
- 基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存,无自动排序功能。
- 底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数,来对key进行映射到不同区域进行保存。
3 vector和list的区别(随机存取、插入删除)
vector
拥有一段连续的内存空间,因此支持随机存取,如果需要高效的随机存取,而不在乎插入和删除的效率,使用vector。list
拥有一段不连续的内存空间,因此不支持随机存取,如果需要大量的插入和删除,而不关心随机存取,则应使用list。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站栏目:【C++零散】unordered-创新互联
文章起源:
http://cdxtjz.cn/article/decsie.html