【C++】STL各容器的实现,时间复杂度,适用情况分析

2021/11/22 9:10:33

本文主要是介绍【C++】STL各容器的实现,时间复杂度,适用情况分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

转自:https://blog.csdn.net/qq_39382769/article/details/102441699

 

一.vector

1.概述

动态数组,在内存中具有连续的储存空间,在堆上分配内存,支持快速随机访问,在中间插入和删除慢,但在末尾插入和删除快

2.特点

1)拥有一段连续的内存空间,并且起始地址不变,因此能非常好的支持随机存取,但由于其内存空间是连续的,所以在中间插入和删除会造成内存块的拷贝,另外,当该数组的内存空间不够时,需要重新申请一块足够大的内存并进行内存拷贝,这些都大大的影响了vector的效率

2)对头部和中间的元素进行插入删除需要移动内存,如果元素是结构体或者类,那么移动时还会进行析构和构造操作,所以性能不高

3)对末尾的元素的操作最快,此时一般不需要移动内存,只有剩余内存不够时才需要

3.时间复杂度分析:

头部插入删除:O(N)

尾部插入删除:O(1)

中间插入删除:O(N)

查找:O(N)

4.优缺点及适用场景

优点:支持随机储存,查询效率高

缺点:在头部和中间插入删除元素效率低,需要移动内存

适用场景:适用于元素结构简单,变化小,并且频繁随机访问的场景

5.结论

vector常用来保存需要经常进行随机访问的内容,并且不需要对中间元素进行添加和删除操作

 

二.双向队列deque

1.概述

deque是double ended queue的缩写,是一个动态数组,可以向两端发展(双向开口的连续线性空间),因此无论在头部或者尾部安插元素都十分迅速,在中间按插元素则比较费时,因为必须移动其他元素

双端队列的元素被表示为一个分段数组,容器中的元素分段存放在一个个大小固定的数组中,此外,容器还需要维护一个存放这些数组首地址的索引数组,如下图所示

由于分段数组的大小是固定的,并且他们的首地址被连续存放在索引数组中,因此可以对其进行随机访问,但是效率比vector低很多

向两端加入新元素时,如果这一端的分段数组未满,则可以直接加入,如果这一端的分段数组已满,只需要创建新的分段数组,并把该分段数组的地址加入到索引数组中即可,这样就不需要对已有的元素进行移动,因此在双端队列的两端加入新的元素都具有较高的效率

当双端队列删除首尾元素时,也不需要移动,所以效率也比较高

双端队列中间插入元素时,需要将插入点到某一端之间的所有元素向容器的这一端移动,因此向中间插入元素的效率较低,而且往往插入的位置越靠近中间,效率越低,删除队列中元素时,情况也类似

2.特点

1)按照页或者块来分配存储器,每页包含固定数目的元素

2)支持随机储存

3)头尾删除插入元素效率高

3.时间复杂度分析

头部尾部插入删除:O(1)

中间插入删除:O(N)

查找:O(N)

4.优缺点及适用场景

优点:头部尾部插入删除快

缺点:不适合中间插入删除操作,占用内存多

适用场景:适用于既要频繁随机储存,又要关心两端数据的插入与删除操作,并且不需要频繁对中间元素进行插入删除的场景

 

三.双向链表list

1.概述

list由双向链表实现,元素存放在堆中,每个元素都是存放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据访问,这个特点使得它的随机储存变得非常的没有效率,但是由于链表的特点,它可以很有效率的支持任意地方的插入和删除操作

2.特点

1)没有预留空间的习惯,所以每分配一个元素都会从内存中分配,每释放一个元素都会释放其占用的内存

2)任何地方插入删除的效率都很高,不需要移动内存,也就不需要在移动过程中对每个元素进行构造和析构,常用来做随机插入和删除的容器

3)访问首尾元素最快

3.时间复杂度分析

任何位置的插入删除:O(1)(假设告诉了你插入删除的位置,不需要你线查找再删除)

头尾查询:O(1)

其他位置查询:O(N)

4.优缺点及适用场景

优点:内存不连续,动态操作,在任意位置插入和删除的效率都高

缺点:不支持随机访问,相比于vector占用内存多

适用场景:适用于经常进行插入和删除并且不经常随机访问的场景

关于vector,deque,list的总结:

vector

特点:快速的随机储存,快速的在最后插入删除元素

适用:需要高效随机储存,需要高效的在末尾插入删除元素,不需要高效的在其他地方插入和删除元素

deque

特点:比较快速的随机存储(比vector的慢),快速的在头尾插入删除元素

适用:需要随机储存,需要高效的在头尾插入删除元素的场景

list

特点:快速在任意位置插入删除元素,快速访问头尾元素

适用:需要大量插入删除操作,不关心随机储存的场景

deque可以看作是vector和list的折中方案

 

四.set

1.概述

set由红黑树实现,其内部元素依照其值自动排序,每个元素只出现一次,不允许重复(红黑树是平衡二叉树的一种)

2.特点

1)元素有序

2)无重复元素

3)插入删除操作的效率比序列容器高,因为对于关联容器来说,不需要做内存的拷贝和内存的移动

3.时间复杂度分析

增删改查近似:O(log N)

4.优缺点及适用场景

优点:使用平衡二叉树实现,便于元素查找,而且保持了元素的唯一性,支持自动排序

缺点:每次插入元素,都需要调整红黑树,效率有一定的影响

适用场景:适用与经常查找一个元素是否在某集群中并且不要排序的场景

 

五.multiset

multiset和set相同,只不过它允许重复元素,也就是说multiset可包括多个数值相同的元素。这里不再做过多介绍。

 

六.map

1.概述

map由红黑树实现,其元素都是键值对,每个元素的键是排序的准则,每个键只能出现一次,不允许重复

2.特点

1)元素为键值对形式,键和值可以是任意类型

2)因为key有序,所以可以通过二分对key进行快速查找

3)增加和删除结点对迭代器的影响很小,除了当前结点是迭代器指向的结点

4)对于迭代器来说,可以修改值,但是不能修改key

3.时间复杂度分析

增删改查基本是O(log N)

4.优缺点和适用场景

优点:适用平衡二叉树实现,便于元素查找,而且可以把值映射到另外一个值,可以创建字典

缺点:每次插入都需要调整红黑树,对效率存在一定的影响

适用场景:适用于需要储存一个字典,并要求方便的根据key找value的场景

 

七.multimap

multimap和map相同,但允许重复元素,也就是说multimap可包含多个键值(key)相同的元素。这里不再做过多介绍。

ps:stack,queue,prioroty_queue都属于容器配接器,是由容器按照特殊的逻辑实现的

 

小结:

1)如果需要高效的随机存取,不在乎插入和删除的效率,使用vector。

2)如果需要大量的插入和删除元素,不关心随机存取的效率,使用list。
3)如果需要随机存取,并且关心两端数据的插入和删除效率,使用deque。
4)如果打算存储数据字典,并且要求方便地根据key找到value,一对一的情况使用map,一对多的情况使用multimap。
5)如果打算查找一个元素是否存在于某集合中,唯一存在的情况使用set,不唯一存在的情况使用multiset。



这篇关于【C++】STL各容器的实现,时间复杂度,适用情况分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程