算法设计与分析课件 02 STL常用容器

算法设计与分析本节要点CONTENTSSTL常用容器vector/stack/queue/list第2页STL常用函数和容器STL（StandardTemplateLibrary，标准模板库）是一个高效的C++程序库，包含了计算机科学领域中很多常用的基本数据结构和基本算法。在算法竞赛中通常不需要手写链表、栈、队列、排序等，直接调用STL中的函数即可。STL提供了一些常用容器，如vector、stack、queue、list等。第3页STL常用函数和容器vector是一个封装了动态数组的顺序容器（SequenceContainer）。顺序容器中的元素按照严格的线性顺序排序，可以通过元素在序列中的位置访问对应的元素，支持数组表示法和随机访问。vector使用一个内存分配器动态处理存储需求，在无法确定数组大小时可使用vector。使用vector时需要引入头文件#include<vector>。第4页STL常用函数和容器（1）创建。向量能够存储各种类型的对象，如标准数据类型、结构体类型等。vector<int>a;//创建一个空的向量a，数据类型为int，数组名为avector<int>a(100);//创建一个向量a，元素个数为100，初始值都为0vector<int>a(10,666);//创建一个向量a，元素个数为10，初始值都为666vector<int>b(a);//b是a的复制vector<int>b(a.begin()+3,a.end()-3);//复制向量a[a.begin()+3,a.end()-3)区间内的元素到b中vector<int>a[5];//创建二维向量a，相当于5个一维向量第5页STL常用函数和容器（2）插入。向vector中插入元素时，既可以在尾部插入，也可以在中间插入。在中间插入元素时，插入位置之后的所有元素需要后移，时间复杂度为O(n)，效率较低。a.push_back(5);//在向量a尾部插入一个元素5a.insert(a.begin()+1,10);//在a.begin()+1位置前插入一个10a.insert(a.begin()+1,5,10);//在a.begin()+1位置前插入5个10a.insert(a.begin()+1,b.begin(),b.begin()+3);//在a.begin()+1位置前插入b向量的前三个元素第6页STL常用函数和容器（3）删除。既可以删除尾部元素及指定位置的元素、区间，也可以清空整个向量。a.pop_back();//删除向量a中的最后一个元素a.erase(a.begin()+1);//删除a.begin()+1位置的元素a.erase(a.begin()+3,a.end()-3);//删除[a.begin()+3,a.end()-3)区间的元素a.clear();//清空整个向量第7页STL常用函数和容器（4）遍历。可以用数组表示法，也可以用迭代器访问。for(inti=0;i<a.size();i++)//用数组表示法遍历

cout<<a[i]<<"\t";for(vector<int>::iteratorit=a.begin();it<a.end();it++)

//用迭代器遍历

cout<<*it<<"\t";（5）改变向量的大小。resize()可以改变向量的大小，若其参数比向量大，则填充默认值0；若其参数比向量小，则舍弃向量后面部分。a.resize(5);//设置向量a的大小为5，若在向量a中有8个元素，则舍弃后面3个元素第8页STL常用函数和容器

stack是一个栈，只能在栈顶操作，不支持数组表示法和随机访问。成员函数：push(x)：x入栈；pop()：出栈；top()：返回栈顶元素；size()：返回栈中元素个数。empty()：判栈空，若为空返回true。第9页STL常用函数和容器

queue是一个队列，只能在队尾入队，队头出队，不支持数组表示法和随机访问。成员函数：push(x)：x入队；pop()：出队；front()：返回队头元素；size()：返回队中元素个数；empty()：判队空，若为空返回true。第10页STL常用函数和容器list是一个双向链表，可以在固定的时间插入删除，不支持数组表示法和随机访问。专用成员函数：merge(b):将链表b与调用链表合并，合并前两个链表必须已经排序，合并后经过排序的链表保存在调用链表中，b为空；remove(val)：从链表中删除val的所有元素；sort()：对链表进行排序；splice(pos,b)：将链表b的内容插入到pos的前面，b为空；unique()：将连续的相同元素压缩为单个元素。第11页STL常用函数和容器push_front(x)/push_back(x)：x从链表头或尾入。pop_fr