数组、链表list、容器vector 、set、stack、queue

willluckysmile 2020-05-03

数组在分配内存的时候是一块连续的空间,并且每个元素的内存是一样的,因此可以用下标快速访问;但正因为如此,在其中插入或者删除的操作就比较麻烦,要移动别的元素的位置,因此需要快速访问存取并且不频繁增删就用数组;

链表list的每个元素使用指针相互链接,分配的空间比较自由,每个元素可以不同类型不同大小,但是访问就必须链式线扫且没有下标,插入删除比较方便,只用替换和删除指针即可,适合频繁增删的操作需求。访问随机元素不如vector快,随机的插入元素比vector快,对每个元素分配空间,所以不存在空间不够,重新分配的情况

容器vector 连续的空间存储,可以使用[]操作符快速的访问随机的元素,快速的在末尾插入元素,但是在序列中间岁间的插入,删除元素要慢,而且如果一开始分配的空间不够的话,有一个重新分配更大空间,然后拷贝的性能开销。

set 内部元素唯一,用一棵平衡树结构来存储,因此遍历的时候就排序了,查找也比较快。 

stack 适配器,必须结合其他的容器使用,stl中默认的内部容器是deque。先进后出,只有一个出口,不允许遍历。 

queue 是受限制的deque,内部容器一般使用list较简单。先进先出,不允许遍历。

相关推荐

whtqsq / 0评论 2019-06-21