1 vector
vector和数组类似,拥有一段连续的内存空间,并且起始地址不变;因此能高效的进行随机存取,时间复杂度为o(1);但因为内存空间是连续的,所以在进行插入和删除操作时,会造成内存块的拷贝,时间复杂度为o(n);另外,当数组中内存空间不够时,会重新申请一块内存空间并进行内存拷贝。
2 list
list是由双向链表实现的,因此内存空间是不连续的。只能通过指针访问数据,所以list的随机存取非常没有效率,时间复杂度为o(n);但由于链表的特点,能高效地进行插入和删除。
3 区别
1. vector内存是连续的,list链表内存不连续;
2. vector会预分配内存,capacity为vector实际内存大小,list内存分配为实际数据大小;
3. vector内存达到capacity容量时将vector数组全部拷贝到新的capacity大小的内存区域,会比list多进行内存拷贝;
4. vector实现对应C语言数组,因此可以直接下标访问vector[i],而list链表内存不连续因此无法下标访问;
5. vector插入删除中间元素时数组会整体移动,而list插入删除直接修改链表指针,因此高效插入删除时还是list好些;
6. vector实现对应C语言数组,可以下标访问因此数据涉及大量的随机访问则最好使用vector,因为list需要整体遍历才能确定所需数据。
原文链接: https://www.cnblogs.com/JCpeng/p/15191646.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/213223
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!