【STL容器学习笔记】-顺序容器

怼烎@ 2022-08-04 05:07 144阅读 0赞

STL提供了三个顺序容器：vector、list和deque。Vector和deque都是用数组来实现的，list是用链表来实现的。关于三者的实现原理和各自应用的场景我们做一下分析。  
1.vector就是动态数组，它是在堆中分配内存，如果vector中元素个数大于当前大小时，就会再分配内存。它拥有一段连续的内存空间，并且起始地址不变，因此它能很好地支持随机访问元素，即\[ \]操作符。vector对末尾元素进行操作（添加或者删除元素）最快，因为不用移动内存。但如果是在中间位置插入或者删除元素，因为要移动内存的缘故，效率会很低。  
2.deque是一种支持向两端高效地插入数据的容器，元素数据采用分块的线性结构进行存储。容器中的元素分段存放在一个个大小固定的数组中，此外容器还需要维护一个存放这些数组首地址的索引数组。因此，在deque两端进行插入操作都很高，但是，在内部进行插入和删除操作，效率还是会很低。  
3.list是用链表来实现，适用于需要频繁在容器中进行插入和删除操作的应用。  
关于开销方面，vector的额外开销最小，deque稍高，list最高。  
顺序容器中的共同函数：  
assign(n,elem) : 将制定元素的n份拷贝加入到容器中  
assign(beg,end): 赋值从迭代器beg到end之间的元素  
push\_back(elem): 将元素附加到容器中  
pop\_back(): 删除容器尾元素  
front(): 返回容器首元素  
back(): 返回容器尾元素  
insert(position,elem): 将元素插入到容器指定位置  
vector特有的函数：  
vector(n,element): 构造一个向量，填入指定元素的n份拷贝  
vector(beg,end): 构造一个向量，用迭代器beg至end之间的元素进行初始化  
vector(size): 构造一个指定规模的向量  
at(index): dataType 返回指定位置的元素  
deque特有的函数：  
deque(n,element): 构造一个双端队列，填入给定元素的n份拷贝  
deque(beg,end): 构造一个双端队列，用迭代器beg至end之间的元素进行初始化  
deque(size): 构造一个指定规模的双端队列  
at(index): dataType 返回指定位置的元素  
push\_front(element): 将元素插入到队首  
pop\_front(): 删除队首元素  
list特有的函数：  
list(n,element): 构造一个列表，填入给定元素的n份拷贝  
list(beg,end): 构造一个列表，用迭代器beg到end之间的元素进行初始化  
list(size): 构造一个指定大小的列表  
push\_front(element): 将元素插入到列表头  
pop\_front(): 删除列表头元素  
remove(element): 删除列表中所有与指定元素相等的元素  
splice(pos1,list2,beg,end): 将list2中从beg至end之间的元素移到本列表pos1之前，调用此函数后，list2变空  
sort(): 将列表按照升序排序  
merge(list2): 假定本列表和list2都已排序，将list2合并至本列表，list2变空  
reverse(): 反序本列表