首页 / C++ / C++ STL容器间的区别与选用标准
C++ STL容器间的区别与选用标准
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++ STL容器间的区别与选用标准,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1564字,纯文字阅读大概需要3分钟。
内容图文
STL容器有vector、list、deque、map、multimap、unordered_map、set、multiset和unodered_map,他们之间有什么不同,各自的优缺点是什么,如何选用时适当的容器,这些问题需要去了解。
vector
序列容器,类似于C语言中的数组,它维护一段连续的内存空间,具有固定的起始地址,可以在任何位置插入新元素,有随机访问功能,即提供[]操作符,并可以和标准C兼容。在效率方面,任意元素的读取、修改具有常数时间复杂度,在序列尾部进行插入、删除是常数时间复杂度,但在序列的头部插入、删除的时间复杂度是O(n)。此外,当被插入的内存空间不够时,需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是,vector每次扩容为原来的两倍,对小对象来说执行效率高,但如果遇到大对象,执行效率就低了。
list
序列容器,类似于C语言中的双向链表,它通过指针来进行数据的访问,因此维护的内存空间可以不连续,这有利于数据的随机存取,没有提供 [] 操作符重载。效率方面,任意元素的访问、修改时间复杂度是O(n),插入、删除操作是常数时间复杂度。
deque
序列容器,类似于C语言中的双向队列,即两端都可以插入或者删除的队列,它维护一段连续的内存空间。queue支持 [] 操作符,也就是支持随机存取,而且跟vector的效率相差无几,并且在序列的头部插入和删除操作是常数时间复杂度。
map
关联容器,按照{键,值}方式组成集合,其中键不允许重复,查找的时间复杂度O(logN)。map内部自建一棵红黑树,会对数据自行排序,所以map内部的数据都是有序的。
multimap
关联容器,multimap和map的区别在与一个键可以对应多个值,也就是说键允许重复。
unordered_map
关联容器,和map的区别在于内部实现是hash表,因此其查找速度非常的快。
set
关联容器,set类似于数学里面的集合,不过set的集合中不包含重复的元素,这是和vector的第一个区别,第二个区别是set内部用平衡二叉树实现,所以会对数据进行排序,且便于元素查找,查找的时间复杂度是O(logN),而vector是使用连续内存存储,便于随机存取。set不支持下标访问。
multiset
multiset类似于数学里面的集合,和set最大的区别在于集合中可以包含重复的元素。
unordered_set
关联容器,和set的区别在于内部实现基于hash表。需要注意的是,每当unordered_set内部进行一次扩容或者缩容,都需要对表中的数据重新计算,也就是说,扩容或者缩容的时间复杂度至少为O(N)。小结
在实际使用过程中,到底选择这几种容器中的哪一个,应该根据遵循以下原则:
1、如果需要高效的随机存取,不在乎插入和删除的效率,使用vector;
2、如果需要大量的插入和删除元素,不关心随机存取的效率,使用list;
3、如果需要随机存取,并且关心两端数据的插入和删除效率,使用deque;
4、如果打算存储数据字典,并且要求方便地根据key找到value,一对一的情况使用map,一对多的情况使用multimap;
5、如果打算查找一个元素是否存在于某集合中,唯一存在的情况使用set,不唯一存在的情况使用multiset。
6、如果要求很快的查找速度,根据情况选择使用unordered_map或unordered_set。
参考博客:https://blog.csdn.net/Abelia/article/details/91995914
原文:https://www.cnblogs.com/honernan/p/12408868.html
内容总结
以上是互联网集市为您收集整理的C++ STL容器间的区别与选用标准全部内容,希望文章能够帮你解决C++ STL容器间的区别与选用标准所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。