C++-STL详解.ppt

ACM/ICPC程序设计程序设计C+标准模板库C+Standard Template Libarary计算机学院 万波主要内容主要内容STL概述：组件、容器、迭代器（iterator）、算法STL容器：常用容器：vector、deque、list、map/multimap、set特殊容器：stack、queue，priority_queue其他容器：hashtableSTL算法：搜寻、排序、拷贝、数值运算STL概述概述STL是C+标准程序库的核心，深刻影响了标准程序库的整体结构STL是泛型（generic）程序库，利用先进、高效的算法来管理数据STL由一些可适应不同需求的集合类（collection class），以及在这些数据集合上操作的算法（algorithm）构成STL内的所有组件都由模板（template）构成，其元素可以是任意类型STL是所有C+编译器和所有操作系统平台都支持的一种库STL概述概述/普通普通C+代码代码#include int main(void)double a=1,2,3,4,5;std:coutmean(a,5);std:coutstd:endl;return 0;/使用了使用了STL的代码的代码#include#include int main()std:vector a;a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(4);a.push_back(5);for(int i=0;i a.size();+i)std:coutaistd:endl;return 0;STL概述概述/使用了使用了STL的代码的代码#include#include int main()std:vector q;q.push_back(10);q.push_back(11);q.push_back(12);std:vector v;for(int i=0;i5;+i)v.push_back(i);std:vector:iterator it=v.begin()+1;it=v.insert(it,33);v.insert(it,q.begin(),q.end();it=v.begin()+3;v.insert(it,3,-1);it=v.begin()+4;v.erase(it);it=v.begin()+1;v.erase(it,it+4);v.clear();return 0;STL概述概述模板（template）函数模板针对一个或多个尚未明确的类型所撰写的针对一个或多个尚未明确的类型所撰写的函数函数或或类类#include#includeusing namespace std;/定义函数模板templateT MAX(T a,T b)return(ab)?a:b;int main()int x=2,y=6;double x1=9.123,y1=12.6543;coutMAX(x,y)endl;coutMAX(x1,y1)endl;STL概述概述模板（template）类模板针对一个或多个尚未明确的类型所撰写的针对一个或多个尚未明确的类型所撰写的函数函数或或类类#includeusing namespace std;/定义名为ex_class的类模板template class ex_class T value;public:ex_class(T v)value=v;void set_value(T v)value=v;T get_value(void)return value;int main()/测试char类型数据 ex_class ch(A);coutch.value:ch.get_value()endl;ch.set_value(a);coutch.value:ch.get_value()endl;/测试double类型数据 ex_class d(5.5);cout“d.value:d.get_value()endl;x.set_value(7.5);cout“d.value:x.get_value()endl;STL概述概述STL组件容器（Container）管理某类对象的集合迭代器（Iterator）在对象集合上进行遍历算法（Algorithm）处理集合内的元素容器适配器（container adaptor）函数对象(functor)容器Container容器Container容器Container算法Algorithm迭代器迭代器Iterator迭代器迭代器Iterator迭代器迭代器IteratorSTL组件之间的协作STL概述概述STL容器类别序列式容器排列次序取决于插入时机和位置关联式容器排列顺序取决于特定准则listdequevector序列式容器mapset关联式容器STL概述概述STL容器的共通能力所有容器中存放的都是值而非引用，即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本，容器元素只能是指针。所有元素都形成一个次序（order），可以按相同的次序一次或多次遍历每个元素各项操作并非绝对安全，调用者必须确保传给操作函数的参数符合需求，否则会导致未定义的行为STL概述概述STL容器元素的条件必须能够通过拷贝构造函数进行复制必须可以通过赋值运算符完成赋值操作必须可以通过析构函数完称销毁动作序列式容器元素的默认构造函数必须可用某些动作必须定义operator=，例如搜寻操作关联式容器必须定义出排序准则，默认情况是重载operator 对于基本数据类型（对于基本数据类型（int,long,char,double,int,long,char,double,）而言，以上条件总）而言，以上条件总是满足是满足STL概述概述STL容器的共通操作初始化（initialization）产生一个空容器以另一个容器元素为初值完成初始化以数组元素为初值完成初始化std:list l;std:vector c(l.begin(),l.end();int array=2,4,6,1345;std:set c(array,array+sizeof(array)/sizeof(array0);std:list l;STL概述概述STL容器的共通操作与大小相关的操作（size operator）size()返回当前容器的元素数量empty()判断容器是否为空max_size()返回容器能容纳的最大元素数量比较（comparison）=,!=,=比较操作两端的容器必须属于同一类型如果两个容器内的所有元素按序相等，那么这两个容器相等采用字典式顺序判断某个容器是否小于另一个容器STL概述概述STL容器的共通操作赋值（assignment）和交换（swap）swap用于提高赋值操作效率与迭代器（iterator）相关的操作begin()返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素之后STL概述概述容器的共通操作元素操作insert(pos,e)将元素e的拷贝安插于迭代器pos所指的位置erase(beg,end)移除beg，end区间内的所有元素clear()移除所有元素STL概述概述迭代器（iterator）（示例:iterator）可遍历STL容器内全部或部分元素的对象指出容器中的一个特定位置迭代器的基本操作操作操作效果效果*返回当前位置上的元素值。如果该元素有成员，可以通返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以过迭代器以operator-取用取用+将迭代器前进至下一元素将迭代器前进至下一元素=和和!=判断两个迭代器是否指向同一位置判断两个迭代器是否指向同一位置=为迭代器赋值（将所指元素的位置赋值过去）为迭代器赋值（将所指元素的位置赋值过去）STL概述概述迭代器（iterator）所有容器都提供获得迭代器的函数操作操作效果效果begin()返回一个迭代器，指向第一个元素返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后返回一个迭代器，指向最后一个元素之后begin()end()半开区间半开区间beg,end)的好处：的好处：1.为遍历元素时循环的结束时机提供了简单的判断依据（为遍历元素时循环的结束时机提供了简单的判断依据（只要未到只要未到达达end()，循环就可以继续，循环就可以继续）2.不必对空区间采取特殊处理（不必对空区间采取特殊处理（空区间的空区间的begin()就等于就等于end()）STL概述概述迭代器（iterator）所有容器都提供两种迭代器container:iterator以“读/写”模式遍历元素container:const_iterator以“只读”模式遍历元素迭代器示例：iteratorbegin()end()+posSTL概述概述迭代器（iterator）迭代器分类双向迭代器可以双向行进,以递增运算前进或以递减运算后退、可以用=和!=比较。list、set和map提供双向迭代器随机存取迭代器除了具备双向迭代器的所有属性，还具备随机访问能力。可以对迭代器增加或减少一个偏移量、处理迭代器之间的距离或者使用之类的关系运算符比较两个迭代器。vector、deque和string提供随机存取迭代器vector v;for(pos=v.begin();posv.end();+pos list l;for(pos=l.begin();pos!=l.end();+pos STL容器容器vectorvector模拟动态数组vector的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）必须包含的头文件#include vector支持随机存取vector的大小（size）和容量（capacity）size返回实际元素个数，capacity返回vector能容纳的元素最大数量。如果插入元素时，元素个数超过capacity，需要重新配置内部存储器。STL容器容器vector构造、拷贝和析构操作操作效果效果vector c产生空的产生空的vectorvector c1(c2)产生同类型的产生同类型的c1，并将复制，并将复制c2的所有元的所有元素素vector c(n)利用类型利用类型T的默认构造函数和拷贝构造函的默认构造函数和拷贝构造函数生成一个大小为数生成一个大小为n的的vectorvector c(n,e)产生一个大小为产生一个大小为n的的vector，每个元素都，每个元素都是是evector c(beg,end)产生一个产生一个vector，以区间，以区间beg,end为元为元素初值素初值vector()销毁所有元素并释放内存。销毁所有元素并释放内存。STL容器容器vector非变动操作操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量（固定值）返回元素最大可能数量（固定值）c.capacity()返回重新分配空间前可容纳的最大元素数量返回重新分配空间前可容纳的最大元素数量c.reserve(n)扩大容量为扩大容量为nc1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2STL容器容器vector赋值操作 std:list l;std:vector v;v.assign(l.begin(),l.end();所有的赋值操作都有所有的赋值操作都有可能调用元素类型的可能调用元素类型的默认构造函数，拷贝默认构造函数，拷贝构造函数，赋值操作构造函数，赋值操作符和析构函数符和析构函数操作操作效果效果c1=c2将将c2的全部元素赋值给的全部元素赋值给c1c.assign(n,e)将元素将元素e的的n个拷贝赋值给个拷贝赋值给cc.assign(beg,end)将区间将区间beg;end的元素赋值给的元素赋值给cc1.swap(c2)将将c1和和c2元素互换元素互换swap(c1,c2)同上，全局函数同上，全局函数STL容器容器vector元素存取 std:vector v;/empty v5=t;/runtime error std:cout v.front();/runtime error操作操作效果效果at(idx)返回索引返回索引idx所标识的元素的引用，进行越界检查所标识的元素的引用，进行越界检查operator(idx)返回索引返回索引idx所标识的元素的引用，不进行越界检查所标识的元素的引用，不进行越界检查front()返回第一个元素的引用，不检查元素是否存在返回第一个元素的引用，不检查元素是否存在back()返回最后一个元素的引用，不检查元素是否存在返回最后一个元素的引用，不检查元素是否存在STL容器容器vector迭代器相关函数 迭代器持续有效，除非发生以下两种情况：迭代器持续有效，除非发生以下两种情况：（1）删除或插入元素）删除或插入元素（2）容量变化而引起内存重新分配）容量变化而引起内存重新分配操作操作效果效果begin()返回一个迭代器，指向第一个元素返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素STL容器容器vector安插（insert）元素操作操作效果效果c.insert(pos,e)在在pos位置插入元素位置插入元素e的副本，并返回新元的副本，并返回新元素位置素位置c.insert(pos,n,e)在在pos位置插入位置插入n个元素个元素e的副本的副本c.insert(pos,beg,end)在在pos位置插入区间位置插入区间beg;end内所有元素内所有元素的副本的副本c.push_back(e)在尾部添加一个元素在尾部添加一个元素e的副本的副本STL容器容器vector移除（remove）元素操作操作效果效果c.pop_back()移除最后一个元素但不返回最后一个元素移除最后一个元素但不返回最后一个元素c.erase(pos)删除删除pos位置的元素，返回下一个元素的位置位置的元素，返回下一个元素的位置c.erase(beg,end)删除区间删除区间beg;end内所有元素，返回下一个内所有元素，返回下一个元素的位置元素的位置c.clear()移除所有元素，清空容器移除所有元素，清空容器c.resize(num)将元素数量改为将元素数量改为num（增加的元素用（增加的元素用defalut构构造函数产生，多余的元素被删除）造函数产生，多余的元素被删除）c.resize(num,e)将元素数量改为将元素数量改为num（增加的元素是（增加的元素是e的副本）的副本）STL容器容器vectorvector应用实例：vectorSTL容器容器dequedeque模拟动态数组deque的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）必须包含的头文件#include deque支持随机存取deque支持在头部和尾部存储数据deque不支持capacity和reserve操作STL容器容器deque构造、拷贝和析构操作操作效果效果decque c产生空的产生空的dequedecque c1(c2)产生同类型的产生同类型的c1，并将复制，并将复制c2的所有元的所有元素素decque c(n)利用类型利用类型T的默认构造函数和拷贝构造函的默认构造函数和拷贝构造函数生成一个大小为数生成一个大小为n的的dequedecque c(n,e)产生一个大小为产生一个大小为n的的deque，每个元素都，每个元素都是是edecque c(beg,end)产生一个产生一个deque，以区间，以区间beg,end为为元素初值元素初值decque()销毁所有元素并释放内存。销毁所有元素并释放内存。STL容器容器deque非变动操作操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量（固定值）返回元素最大可能数量（固定值）c1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2STL容器容器deque赋值操作 std:list l;std:deque v;v.assign(l.begin(),l.end();所有的赋值操作都有所有的赋值操作都有可能调用元素类型的可能调用元素类型的默认构造函数，拷贝默认构造函数，拷贝构造函数，赋值操作构造函数，赋值操作符和析构函数符和析构函数操作操作效果效果c1=c2将将c2的全部元素赋值给的全部元素赋值给c1c.assign(n,e)将元素将元素e的的n个拷贝赋值给个拷贝赋值给cc.assign(beg,end)将区间将区间beg;end的元素赋值给的元素赋值给cc1.swap(c2)将将c1和和c2元素互换元素互换swap(c1,c2)同上，全局函数同上，全局函数STL容器容器deque元素存取 std:deque dq;/empty dq5=t;/runtime error std:cout dq.front();/runtime error操作操作效果效果at(idx)返回索引返回索引idx所标识的元素的引用，进行越界检查所标识的元素的引用，进行越界检查operator(idx)返回索引返回索引idx所标识的元素的引用，不进行越界检查所标识的元素的引用，不进行越界检查front()返回第一个元素的引用，不检查元素是否存在返回第一个元素的引用，不检查元素是否存在back()返回最后一个元素的引用，不检查元素是否存在返回最后一个元素的引用，不检查元素是否存在STL容器容器deque迭代器相关函数 迭代器持续有效，除非发生以下两种情况：迭代器持续有效，除非发生以下两种情况：（1）删除或插入元素）删除或插入元素（2）容量变化而引起内存重新分配）容量变化而引起内存重新分配操作操作效果效果begin()返回一个迭代器，指向第一个元素返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素STL容器容器deque安插（insert）元素操作操作效果效果c.insert(pos,e)在在pos位置插入元素位置插入元素e的副本，并返回新元的副本，并返回新元素位置素位置c.insert(pos,n,e)在在pos位置插入位置插入n个元素个元素e的副本的副本c.insert(pos,beg,end)在在pos位置插入区间位置插入区间beg;end内所有元素内所有元素的副本的副本c.push_back(e)在尾部添加一个元素在尾部添加一个元素e的副本的副本c.push_front(e)在头部添加一个元素在头部添加一个元素e的副本的副本STL容器容器deque移除（remove）元素操作操作效果效果c.pop_back()移除最后一个元素但不返回最后一个元素移除最后一个元素但不返回最后一个元素c.pop_front()移除第一个元素但不返回第一个元素移除第一个元素但不返回第一个元素c.erase(pos)删除删除pos位置的元素，返回下一个元素的位置位置的元素，返回下一个元素的位置c.erase(beg,end)删除区间删除区间beg;end内所有元素，返回下一个内所有元素，返回下一个元素的位置元素的位置c.clear()移除所有元素，清空容器移除所有元素，清空容器c.resize(num)将元素数量改为将元素数量改为num（增加的元素用（增加的元素用defalut构构造函数产生，多余的元素被删除）造函数产生，多余的元素被删除）c.resize(num,e)将元素数量改为将元素数量改为num（增加的元素是（增加的元素是e的副本）的副本）STL容器容器dequedeque应用实例：dequeSTL容器容器list使用双向链表管理元素list的元素可以是任意类型T，但必须具备赋值和拷贝能力必须包含的头文件#include list不支持随机存取，因此不提供下标操作符在任何位置上执行元素的安插和移除都非常快。安插和删除不会导致指向其他元素的指针、引用、iterator失效。STL容器容器list构造、拷贝和析构操作操作效果效果list c产生空的产生空的listlist c1(c2)产生同类型的产生同类型的c1，并将复制，并将复制c2的所有元素的所有元素list c(n)利用类型利用类型T的默认构造函数和拷贝构造函数生的默认构造函数和拷贝构造函数生成一个大小为成一个大小为n的的listlist c(n,e)产生一个大小为产生一个大小为n的的list，每个元素都是，每个元素都是elist c(beg,end)产生一个产生一个list，以区间，以区间beg,end为元素初值为元素初值list()销毁所有元素并释放内存。销毁所有元素并释放内存。STL容器容器list非变动性操作操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量返回元素最大可能数量c1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2STL容器容器list赋值操作操作效果效果c1=c2将将c2的全部元素赋值给的全部元素赋值给c1c.assign(n,e)将将e的的n个拷贝赋值给个拷贝赋值给cc.assign(beg,end)将区间将区间beg;end的元素赋值给的元素赋值给cc1.swap(c2)将将c1和和c2的元素互换的元素互换swap(c1,c2)同上，全局函数同上，全局函数STL容器容器list元素存取 std:list l;/empty std:cout l.front();/runtime error if(!l.empty()std:coutl.back();/ok 操作操作效果效果front()返回第一个元素的引用，不检查元素是否存在返回第一个元素的引用，不检查元素是否存在back()返回最后一个元素的引用，不检查元素是否存在返回最后一个元素的引用，不检查元素是否存在STL容器容器list迭代器相关函数操作操作效果效果begin()返回一个双向迭代器，指向第一个元素返回一个双向迭代器，指向第一个元素end()返回一个双向迭代器，指向最后一个元素之后返回一个双向迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素STL容器容器list安插（insert）元素操作操作效果效果c.insert(pos,e)在在pos位置插入位置插入e的副本，并返回新元素位的副本，并返回新元素位置置c.insert(pos,n,e)在在pos位置插入位置插入n个个e的副本的副本c.insert(pos,beg,end)在在pos位置插入区间位置插入区间beg;end内所有元素内所有元素的副本的副本c.push_back(e)在尾部添加一个在尾部添加一个e的副本的副本c.push_front(e)在头部添加一个在头部添加一个e的副本的副本STL容器容器list移除（remove）元素操作操作效果效果c.pop_back()移除最后一个元素但不返回移除最后一个元素但不返回c.pop_front()移除第一个元素但不返回移除第一个元素但不返回c.erase(pos)删除删除pos位置的元素，返回下一个元素的位置位置的元素，返回下一个元素的位置c.remove(val)移除所有值为移除所有值为val的元素的元素c.remove_if(op)移除所有移除所有“op(val)=true”的元素的元素c.erase(beg,end)删除区间删除区间beg;end内所有元素，返回下一个元内所有元素，返回下一个元素的位置素的位置c.clear()移除所有元素，清空容器移除所有元素，清空容器c.resize(num)将元素数量改为将元素数量改为num（多出的元素用（多出的元素用defalut构构造函数产生）造函数产生）c.resize(num,e)将元素数量改为将元素数量改为num（多出的元素是（多出的元素是e的副本）的副本）STL容器容器list特殊变动性操作操作操作效果效果c.unique移除重复元素，只留下一个移除重复元素，只留下一个c.unique(op)移除使移除使op()结果为结果为true的重复元素的重复元素c1.splice(pos,c2)将将c2内的所有元素内的所有元素转移转移到到c1的迭代器的迭代器pos之前之前c1.splice(pos,c2,c2pos)将将c2内内c2pos所指元素所指元素转移转移到到c1内的内的pos之前之前c1.splice(pos,c2,c2beg,c2end)将将c2内内c2beg;c2end)区间内所有元素区间内所有元素转移转移到到c2的的pos之前之前STL容器容器list特殊变动性操作（续）操作操作效果效果c.sort()以以operator 为准则对所有元素排序为准则对所有元素排序c.sort(op)以以op为准则对所有元素排序为准则对所有元素排序c1.merge(c2)假设假设c1和和c2都已排序，将都已排序，将c2全部元素转移到全部元素转移到c1并保证合并后并保证合并后list仍为已排序仍为已排序c.reverse()将所有元素反序将所有元素反序STL容器容器listlist应用实例：listSTL容器容器map/multimap使用平衡二叉树管理元素元素包含两部分(key,value)，key和value可以是任意类型必须包含的头文件#include 根据元素的key自动对元素排序，因此根据元素的key进行定位很快，但根据元素的value定位很慢不能直接改变元素的key，可以通过operator 直接存取元素值map中不允许key相同的元素，multimap允许key相同的元素STL容器容器map/multimap内部存储结构749258111361012yyxyqywxzyqzSTL容器容器map/multimap构造、拷贝和析构操作操作效果效果map c产生空的产生空的mapmap c1(c2)产生同类型的产生同类型的c1，并复制，并复制c2的所有元素的所有元素map c(op)以以op为排序准则产生一个空的为排序准则产生一个空的mapmap c(beg,end)以区间以区间beg,end内的元素产生一个内的元素产生一个mapmap c(beg,end,op)以以op为排序准则，以区间为排序准则，以区间beg,end内的元内的元素产生一个素产生一个map map()销毁所有元素并释放内存。销毁所有元素并释放内存。其中map可以是下列形式map一个以less（）为排序准则的map，map一个以op为排序准则的mapSTL容器容器map/multimap非变动性操作操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量返回元素最大可能数量c1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2STL容器容器map/multimap赋值操作操作效果效果c1=c2将将c2的全部元素赋值给的全部元素赋值给c1c1.swap(c2)将将c1和和c2的元素互换的元素互换swap(c1,c2)同上，全局函数同上，全局函数STL容器容器map/multimap特殊搜寻操作操作操作效果效果count(key)返回返回”键值等于键值等于key”的元素个数的元素个数find(key)返回返回”键值等于键值等于key”的第一个元素，找不到返的第一个元素，找不到返回回endlower_bound(key)返回返回”键值大于等于键值大于等于key”的第一个元素的第一个元素upper_bound(key)返回返回”键值大于键值大于key”的第一个元素的第一个元素equal_range(key)返回返回”键值等于键值等于key”的元素区间的元素区间STL容器容器map/multimap迭代器相关函数操作操作效果效果begin()返回一个双向迭代器，指向第一个元素返回一个双向迭代器，指向第一个元素end()返回一个双向迭代器，指向最后一个元素之后返回一个双向迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素STL容器容器map/multimap安插（insert）元素操作操作效果效果c.insert(pos,e)在在pos位置为起点插入位置为起点插入e的副本，并返回新的副本，并返回新元素位置（插入速度取决于元素位置（插入速度取决于pos）c.insert(e)插入插入e的副本，并返回新元素位置的副本，并返回新元素位置c.insert(beg,end)将区间将区间beg;end内所有元素的副本插入到内所有元素的副本插入到c中中STL容器容器map/multimap移除（remove）元素操作操作效果效果c.erase(pos)删除迭代器删除迭代器pos所指位置的元素，无返回值所指位置的元素，无返回值c.erase(val)移除所有值为移除所有值为val的元素，返回移除元素个数的元素，返回移除元素个数c.erase(beg,end)删除区间删除区间beg;end内所有元素，无返回值内所有元素，无返回值c.clear()移除所有元素，清空容器移除所有元素，清空容器STL容器容器map/multimapmap应用实例：mapSTL容器容器stack（实例：stack）后进先出（LIFO）#include 核心接口push(value)将元素压栈top()返回栈顶元素的引用，但不移除pop()从栈中移除栈顶元素，但不返回实例：stackstacktop()pop()push()STL容器容器queue（实例：queue）先进先出（FIFO）#include 核心接口push(e)将元素置入队列front()返回队列头部元素的引用，但不移除back()返回队列尾部元素的引用，但不移除pop()从队列中移除元素，但不返回实例：queuequeuefront()pop()push()back()STL容器容器priority_queue（实例：priority_queue）以某种排序准则（默认为less）管理队列中的元素#include 核心接口push(e)根据元素的优先级将元素置入队列top()返回优先队列头部最大的元素的引用，但不移除pop()从栈中移除最大元素，但不返回empty()队列是否为空STL算法算法STL提供了一些标准算法来处理容器内的元素搜寻、排序、拷贝、数值运算STL的算法是全局函数明确划分数据和操作泛型函数式编程模式所有算法可以对所有容器适用，甚至可以操作不同类型容器的元素算法头文件#include#include STL算法实例：algorithmSTL算法算法区间（range）所有算法都用来处理一个或多个区间内的元素。区间可以但不一定涵盖容器内所有元素为了操作元素的某个子集必须将区间的首尾（iterator）当作两个参数传递给算法调用时必须确保区间有效性从起点出发，逐一前进，能够到达终点。区间首尾两个迭代器必须属于同一容器，且前后放置正确无效区间可能会引起无限循环或者内存非法访问所有算法处理的都是半开区间begin,end)STL算法算法STL算法分类非变动性算法（nonmodifying algorithms）变动性算法（modifying algorithms）移除性算法（removing algorithms）变序性算法（mutating algorithms）排序性算法（sorting algorithms）已序区间算法（sorted range algorithms）数值算法（numeric algorithms）STL算法算法for_each()算法for_each(InputIterator beg,InputIterator end,UnaryProc op)对区间beg,end)中的每一个元素调用op(elem)返回op之后的容器副本op可以改变元素op的返回值被忽略复杂度：O(n)示例:foreachSTL算法算法非变动性算法既不改变元素次序也不改变元素值名称名称作用作用count()返回元素个数返回元素个数count_if()返回满足某一条件的元素个数返回满足某一条件的元素个数min_element()返回最小元素（以迭代器表示）返回最小元素（以迭代器表示）max_element()返回最大元素（以迭代器表示）返回最大元素（以迭代器表示）find()搜寻等于某值的第一个元素搜寻等于某值的第一个元素find_if()搜寻满足某个准则的第一个元素搜寻满足某个准则的第一个元素search_n()搜寻具有某种特性的第一段搜寻具有某种特性的第一段“n个连续元素个连续元素”search()搜寻某个区间第一次出现的位置搜寻某个区间第一次出现的位置STL算法算法非变动性算法元素计数count(InputIterator beg,InputIterator end,const T&value)计算区间中值等于value的元素个数count(InputIterator beg,InputIterator end,Predicate op)计算区间中使判断式op结果为true的元素个数op接受单个参数，返回值为bool型复杂度：O(n)示例:countSTL算法算法非变动性算法最小值和最大值min_element(InputIterator beg,InputIterator end)min_element(InputIterator beg,InputIterator end,CompFunc op)max_element(InputIterator beg,InputIterator end)max_element(InputIterator beg,InputIterator end,CompFunc op)返回区间中最大或最小元素的位置（迭代器）无op参数的版本以（“小于”运算符）进行比较op用来比较两个元素：bool op(elem1,elem2)，如果elem1“小于”elem2返回true否则返回false复杂度：O(n)示例:minmaxSTL算法算法非变动性算法搜寻元素find(InputIterator beg,InputIterator end,const T&valu