Vector和List的差别

Bertha 。 2023-01-18 12:25 50阅读 0赞

![在这里插入图片描述][20210506145332298.png]

### Vector/List ###

*  目录:
 *   *  一.底层结构
     *  二.随机访问
     *  三.插入/删除
     *  四.空间利用率
     *  五.迭代器
     *  六.迭代器失效
     *  七.使用场景

# 目录: #

## 一.底层结构 ##

Vector :

> 是一段连续的空间,是一个 **动态的顺序表**

List :

> 是带有头结点的 **双向循环链表**

## 二.随机访问 ##

Vector :

> 支持随机访问,在访问某个元素的时候,元素的效率为 **O(1)**

List :

> 不支持随机访问,访问某个元素的效率是 **O(n)**

## 三.插入/删除 ##

Vector :

> 1.任意位置插入和删除效率比较低,需要搬移元素,时间复杂度为 **O(n)**  
> 2.插入时有可能需要增容: 开辟新的空间,拷贝元素,释放旧的空间,导致效率比较低.

List :

> 1.任意位置插入和删除效率高,不需要搬移元素,直接改变内部的节点就可以了.时间复杂度为 **O(1)**

## 四.空间利用率 ##

Vector :

> 底层为连续的空间,不容易造成内存碎片,空间利用率高,缓存利用率高

List :

> 底层的节点开辟空间,小的节点容易会造成内存碎片,空间的利用率比较低,缓存利用率低

## 五.迭代器 ##

Vector :

> 原生态指针

List :

> 对原生态指针(节点指针)进行封装

## 六.迭代器失效 ##

Vector :

> 在插入元素的时候,要给所有的迭代器进行重新赋值

**因为插入元素会造成有可能重新扩容,致使原来的迭代器失效,删除的时候当前的迭代器需要重新赋值,不然就会失效**

List :

> 插入元素的时候不会导致迭代器失效,但是在删除元素的时候会导致当前的迭代器失效,其他的迭代器不受到影响

## 七.使用场景 ##

Vector :

> 需要高效的存储,支持随机访问,不关心插入删除效率

List :

> 大量插入和删除的操作,不关系随机访问

我们可以结合代码来进行实现,大家可以从代码来加深对差别的理解.

[20210506145332298.png]: /images/20221021/80e35a29bcc948a7a5a9835dea141789.png

发表评论取消回复

表情：

评论列表（有 0 条评论，50人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】vector 和 list 的对比

<table> <thead> <tr> <th></th> <th>vector</th> <th>list</th> </tr>

迷南。/ 2023年07月15日 15:24/ 0 赞/ 14 阅读

相关通过List和Vector来实现栈和队列

![在这里插入图片描述][2021050622042239.png] 栈/队列目录: 一.实现栈(stack) 1.Vec

「爱情、让人受尽委屈。」/ 2023年01月18日 14:28/ 0 赞/ 14 阅读

相关 Vector和List的差别

![在这里插入图片描述][20210506145332298.png] Vector/List 目录: 一.底层结构二.随机访问

Bertha 。/ 2023年01月18日 12:25/ 0 赞/ 51 阅读

相关 STL模板总结归纳（vector，deque和list）

好久没有更博呀都快一个月了呢~最近AC出现问题最多的就是数据结构了。然后正好在学C++，应我小伙伴wyp的要求，我整理了STL模板的使用，供大家参考。 1. vector

- 日理万妓/ 2022年09月29日 12:55/ 0 赞/ 117 阅读

相关 C++ vector和list的区别

[C++ vector和list的区别][C_ vector_list] 1.vector数据结构 vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。

谁借莪１个温暖的怀抱￠/ 2022年06月10日 04:26/ 0 赞/ 210 阅读

相关温习C/C++笔记(3)——Vector和List的区别

1.Vector容器 vector 是一种顺序容器，它的元素被存储在一段连续空间中。vector是作为一种动态数组实现的，和普通的数组一样，它的元素被存储在一段连续的

梦里梦外;/ 2022年06月06日 02:44/ 0 赞/ 199 阅读

相关 Vector、ArrayList和List的异同

线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本文试图通过简单的描述，

一时失言乱红尘/ 2022年06月04日 00:20/ 0 赞/ 185 阅读

相关 list.reverse(),list.sort()和reversed(),sorted()的用法及差别

f = [1,3,2,4,5,68] f1 = reversed(f) f2 = sorted(f) print(f1, f2) pri

╰半橙微兮°/ 2022年05月30日 07:09/ 0 赞/ 216 阅读

相关 List与Vector区别

List比较熟悉，Vector相对陌生。线程安全的集合：喂，SHE 第一个就是Vector 它跟list一样都是动态数组组成的，如何使用 Vector<Stri

r囧r小猫/ 2022年03月16日 07:26/ 0 赞/ 212 阅读

相关 Map、Set、List集合差别及联系

Map、Set、List集合差别及联系一、数组Array和集合的区别 1. 数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型） 2.

阳光穿透心脏的1/2处/ 2021年09月22日 20:02/ 0 赞/ 316 阅读