189 8069 5689

【C++零散】unordered-创新互联

文章目录
  • 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

其他资讯