《CSTL详解实用实用教案》由会员分享，可在线阅读，更多相关《CSTL详解实用实用教案（89页珍藏版）》请在金锄头文库上搜索。
1、主要(zhyo)内容STL概述(ish)：组件、容器、迭代器（iterator）、算法STL容器：常用容器：vector、deque、list、map/multimap、set特殊容器：stack、queue，priority_queue其他容器：hashtableSTL算法：搜寻、排序、拷贝、数值运算第1页/共88页第一页，共89页。STL概述(ish)STL是C+标准程序库的核心，深刻影响了标准程序库的整体结构STL是泛型（generic）程序库，利用先进(xinjn)、高效的算法来管理数据STL由一些可适应不同需求的集合类（collectionclass），以及在这些数据集合上操作的算法
2、（algorithm）构成STL内的所有组件都由模板（template）构成，其元素可以是任意类型STL是所有C+编译器和所有操作系统平台都支持的一种库第2页/共88页第二页，共89页。STL概述(ish)/普通(ptng)C+代码#include int main(void) double a = 1, 2, 3, 4, 5; std:coutmean(a, 5); std:coutstd:endl; return 0;/使用(shyng)了STL的代码#include #include int main() std:vector a; a.push_back(1); a.push_back
3、(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;第3页/共88页第三页，共89页。STL概述(ish)/使用(shyng)了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)
4、; 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;第4页/共88页第四页，共89页。STL概述(ish)模板(mbn)（template）函数模板(mbn)针对一个或多个尚未明确的类型所撰写(zhun x
5、i)的函数或类#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;第5页/共88页第五页，共89页。STL概述(ish)模板(mbn)（template）类模板(mbn)针对(zhndu)一个或多个尚未明确的类型所撰写的函数或类#includeusing namespace std;/定义名为ex_cla
6、ss的类模板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
7、_value()endl; x.set_value(7.5); cout“d.value:x.get_value()endl;第6页/共88页第六页，共89页。STL概述(ish)STL组件容器（Container）管理某类对象的集合迭代器（Iterator）在对象集合上进行遍历算法(sunf)（Algorithm）处理集合内的元素容器适配器（containeradaptor）函数对象(functor)容器Container容器Container容器Container算法Algorithm迭代器Iterator迭代器Iterator迭代器IteratorSTL组件(z jin)之间的协作第7页
8、/共88页第七页，共89页。STL概述(ish)STL容器类别(libi)序列式容器排列次序取决于插入时机和位置关联式容器排列顺序取决于特定准则listdequevector序列式容器mapset关联式容器第8页/共88页第八页，共89页。STL概述(ish)STL容器的共通(gngtng)能力所有容器中存放的都是值而非引用，即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本，容器元素只能是指针。所有元素都形成一个次序（order），可以按相同的次序一次或多次遍历每个元素各项操作并非绝对安全，调用者必须确保传给操作函数的参数符合需求，否则会导致未
9、定义的行为第9页/共88页第九页，共89页。STL概述(ish)STL容器元素的条件必须能够通过拷贝构造函数(hnsh)进行复制必须可以通过赋值运算符完成赋值操作必须可以通过析构函数(hnsh)完称销毁动作序列式容器元素的默认构造函数(hnsh)必须可用某些动作必须定义operator=，例如搜寻操作关联式容器必须定义出排序准则，默认情况是重载operator对于基本数据类型（对于基本数据类型（int,long,char,double,int,long,char,double,）而言，以上）而言，以上(yshng)(yshng)条条件总是满足件总是满足第10页/共88页第十页，共89页。STL
10、概述(ish)STL容器(rngq)的共通操作初始化（initialization）产生一个空容器(rngq)以另一个容器(rngq)元素为初值完成初始化以数组元素为初值完成初始化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;第11页/共88页第十一页，共89页。STL概述(ish)STL容器的共通操作与大小相关的操作（sizeoperator）size()返回当前容器的元素数量empty()
11、判断容器是否为空max_size()返回容器能容纳的最大元素数量比较（comparison）=,!=,=比较操作两端(lindun)的容器必须属于同一类型如果两个容器内的所有元素按序相等，那么这两个容器相等采用字典式顺序判断某个容器是否小于另一个容器第12页/共88页第十二页，共89页。STL概述(ish)STL容器的共通(gngtng)操作赋值（assignment）和交换（swap）swap用于提高赋值操作效率与迭代器（iterator）相关的操作begin()返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一
12、个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素之后第13页/共88页第十三页，共89页。STL概述(ish)容器的共通(gngtng)操作元素操作insert(pos,e)将元素e的拷贝安插于迭代器pos所指的位置erase(beg,end)移除beg，end区间内的所有元素clear()移除所有元素第14页/共88页第十四页，共89页。STL概述(ish)迭代器（iterator）（示例:iterator）可遍历STL容器内全部或部分元素的对象指出容器中的一个(y)特定位置迭代器的基本操作操作操作效果效果*返回当前位置上的元素值。如果该元素有成员，可以通返回当前位置上的元素
13、值。如果该元素有成员，可以通过迭代器以过迭代器以operator -取用取用+将迭代器前进至下一元素将迭代器前进至下一元素=和和!=判断两个迭代器是否指向同一位置判断两个迭代器是否指向同一位置=为迭代器赋值（将所指元素的位置赋值过去）为迭代器赋值（将所指元素的位置赋值过去）第15页/共88页第十五页，共89页。STL概述(ish)迭代器（iterator）所有容器都提供获得(hud)迭代器的函数操作操作效果效果begin()返回一个迭代器，指向第一个元素返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后返回一个迭代器，指向最后一个元素之后begin()end()半开区
14、间beg, end)的好处：1.为遍历元素时循环的结束(jish)时机提供了简单的判断依据（只要未到达end()，循环就可以继续）2.不必对空区间采取特殊处理（空区间的begin()就等于end()）第16页/共88页第十六页，共89页。STL概述(ish)迭代器（iterator）所有容器(rngq)都提供两种迭代器container:iterator以“读/写”模式遍历元素container:const_iterator以“只读”模式遍历元素迭代器示例：iteratorbegin()end() + pos第17页/共88页第十七页，共89页。STL概述(ish)迭代器（iterator）迭
15、代器分类双向迭代器可以双向行进,以递增运算前进或以递减运算后退、可以用=和!=比较。list、set和map提供双向迭代器随机(suj)存取迭代器除了具备双向迭代器的所有属性，还具备随机(suj)访问能力。可以对迭代器增加或减少一个偏移量、处理迭代器之间的距离或者使用之类的关系运算符比较两个迭代器。vector、deque和string提供随机(suj)存取迭代器vector v; for(pos=v.begin();posv.end();+pos list l; for(pos=l.begin();pos!=l.end();+pos 第18页/共88页第十八页，共89页。STL容器(rngq
16、)vectorvector模拟动态(dngti)数组vector的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）必须包含的头文件#includevector支持随机存取vector的大小（size）和容量（capacity）size返回实际元素个数，capacity返回vector能容纳的元素最大数量。如果插入元素时，元素个数超过capacity，需要重新配置内部存储器。第19页/共88页第十九页，共89页。STL容器(rngq)vector构造(guzo)、拷贝和析构操作操作效果效果vector c产生空的产生空的vectorvector c
17、1(c2)产生同类型的产生同类型的c1，并将复制，并将复制c2的所有元的所有元素素vector c(n)利用类型利用类型T的默认构造函数和拷贝构造函的默认构造函数和拷贝构造函数生成一个大小为数生成一个大小为n的的vectorvector c(n,e)产生一个大小为产生一个大小为n的的vector，每个元素都，每个元素都是是evector c(beg,end)产生一个产生一个vector，以区间，以区间beg,end为元为元素初值素初值vector()销毁所有元素并释放内存。销毁所有元素并释放内存。第20页/共88页第二十页，共89页。STL容器(rngq)vector非变动(bindng)操作
18、操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量（固定值）返回元素最大可能数量（固定值）c.capacity()返回重新分配空间前可容纳的最大元素数量返回重新分配空间前可容纳的最大元素数量c.reserve(n)扩大容量为扩大容量为nc1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2第21页/共88页第二十一页，共89页。STL容器(rngq)vector赋值操作(
19、cozu) std:list l; std:vector v; v.assign(l.begin(),l.end();所有的赋值操作都有可能调用元素类型的默认构造函数，拷贝(kobi)构造函数，赋值操作符和析构函数操作操作效果效果c1 = c2将将c2的全部元素赋值给的全部元素赋值给c1c.assign(n,e)将元素将元素e的的n个拷贝赋值给个拷贝赋值给cc.assign(beg,end)将区间将区间beg;end的元素赋值给的元素赋值给cc1.swap(c2)将将c1和和c2元素互换元素互换swap(c1,c2)同上，全局函数同上，全局函数第22页/共88页第二十二页，共89页。STL容器
20、(rngq)vector元素(yuns)存取 std:vector v;/empty v5= t;/runtime error std:cout v.front();/runtime error操作操作效果效果at(idx)返回索引返回索引idx所标识的元素的引用，进行越界检查所标识的元素的引用，进行越界检查operator (idx)返回索引返回索引idx所标识的元素的引用，不进行越界检查所标识的元素的引用，不进行越界检查front()返回第一个元素的引用，不检查元素是否存在返回第一个元素的引用，不检查元素是否存在back()返回最后一个元素的引用，不检查元素是否存在返回最后一个元素的引用，
21、不检查元素是否存在第23页/共88页第二十三页，共89页。STL容器(rngq)vector迭代(didi)器相关函数 迭代器持续有效，除非发生(fshng)以下两种情况：（1）删除或插入元素（2）容量变化而引起内存重新分配操作操作效果效果begin()返回一个迭代器，指向第一个元素返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个
22、元素第24页/共88页第二十四页，共89页。STL容器(rngq)vector安插(nch)（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的副本的副本第25页/共88页第二十五页，共89页。STL容器(rngq)vec
23、tor移除（remove）元素(yuns)操作操作效果效果c.pop_back()移除最后一个元素但不返回最后一个元素移除最后一个元素但不返回最后一个元素c.erase(pos)删除删除pos位置的元素，返回下一个元素的位置位置的元素，返回下一个元素的位置c.erase(beg,end)删除区间删除区间beg;end内所有元素，返回下一个元内所有元素，返回下一个元素的位置素的位置c.clear()移除所有元素，清空容器移除所有元素，清空容器c.resize(num)将元素数量改为将元素数量改为num（增加的元素用（增加的元素用defalut构构造函数产生，多余的元素被删除）造函数产生，多余的元
24、素被删除）c.resize(num,e)将元素数量改为将元素数量改为num（增加的元素是（增加的元素是e的副本）的副本）第26页/共88页第二十六页，共89页。STL容器(rngq)vectorvector应用(yngyng)实例：vector第27页/共88页第二十七页，共89页。STL容器(rngq)dequedeque模拟动态数组deque的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）必须包含的头文件#includedeque支持(zhch)随机存取deque支持(zhch)在头部和尾部存储数据deque不支持(zhch)capacit
25、y和reserve操作第28页/共88页第二十八页，共89页。STL容器(rngq)deque构造(guzo)、拷贝和析构操作操作效果效果decque c产生空的产生空的dequedecque c1(c2)产生同类型的产生同类型的c1，并将复制，并将复制c2的所有元的所有元素素decque c(n)利用类型利用类型T的默认构造函数和拷贝构造函的默认构造函数和拷贝构造函数生成一个大小为数生成一个大小为n的的dequedecque c(n,e)产生一个大小为产生一个大小为n的的deque ，每个元素都，每个元素都是是edecque c(beg,end)产生一个产生一个deque ，以区间，以区间b
26、eg,end为为元素初值元素初值decque()销毁所有元素并释放内存。销毁所有元素并释放内存。第29页/共88页第二十九页，共89页。STL容器(rngq)deque非变动(bindng)操作操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量（固定值）返回元素最大可能数量（固定值）c1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2第30页/共88页第三十页，共89页
27、。STL容器(rngq)deque赋值操作(cozu) std:list l; std:deque v; v.assign(l.begin(),l.end();所有的赋值操作都有可能调用元素类型的默认(mrn)构造函数，拷贝构造函数，赋值操作符和析构函数操作操作效果效果c1 = c2将将c2的全部元素赋值给的全部元素赋值给c1c.assign(n,e)将元素将元素e的的n个拷贝赋值给个拷贝赋值给cc.assign(beg,end)将区间将区间beg;end的元素赋值给的元素赋值给cc1.swap(c2)将将c1和和c2元素互换元素互换swap(c1,c2)同上，全局函数同上，全局函数第31页/
28、共88页第三十一页，共89页。STL容器(rngq)deque元素(yuns)存取 std:deque dq;/empty dq5= t;/runtime error std:cout dq.front();/runtime error操作操作效果效果at(idx)返回索引返回索引idx所标识的元素的引用，进行越界检查所标识的元素的引用，进行越界检查operator (idx)返回索引返回索引idx所标识的元素的引用，不进行越界检查所标识的元素的引用，不进行越界检查front()返回第一个元素的引用，不检查元素是否存在返回第一个元素的引用，不检查元素是否存在back()返回最后一个元素的引用，
29、不检查元素是否存在返回最后一个元素的引用，不检查元素是否存在第32页/共88页第三十二页，共89页。STL容器(rngq)deque迭代器相关(xinggun)函数 迭代器持续有效，除非发生以下两种情况：（1）删除或插入元素（2）容量(rngling)变化而引起内存重新分配操作操作效果效果begin()返回一个迭代器，指向第一个元素返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后返回一个迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后
30、一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素第33页/共88页第三十三页，共89页。STL容器(rngq)deque安插(nch)（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_fro
31、nt(e)在头部添加一个元素在头部添加一个元素e的副本的副本第34页/共88页第三十四页，共89页。STL容器(rngq)deque移除（remove）元素(yuns)操作操作效果效果c.pop_back()移除最后一个元素但不返回最后一个元素移除最后一个元素但不返回最后一个元素c.pop_front()移除第一个元素但不返回第一个元素移除第一个元素但不返回第一个元素c.erase(pos)删除删除pos位置的元素，返回下一个元素的位置位置的元素，返回下一个元素的位置c.erase(beg,end)删除区间删除区间beg;end内所有元素，返回下一个元内所有元素，返回下一个元素的位置素的位置c
32、.clear()移除所有元素，清空容器移除所有元素，清空容器c.resize(num)将元素数量改为将元素数量改为num（增加的元素用（增加的元素用defalut构构造函数产生，多余的元素被删除）造函数产生，多余的元素被删除）c.resize(num,e)将元素数量改为将元素数量改为num（增加的元素是（增加的元素是e的副本）的副本）第35页/共88页第三十五页，共89页。STL容器(rngq)dequedeque应用(yngyng)实例：deque第36页/共88页第三十六页，共89页。STL容器(rngq)list使用(shyng)双向链表管理元素list的元素可以是任意类型T，但必须具备
33、赋值和拷贝能力必须包含的头文件#includelist不支持随机存取，因此不提供下标操作符在任何位置上执行元素的安插和移除都非常快。安插和删除不会导致指向其他元素的指针、引用、iterator失效。第37页/共88页第三十七页，共89页。STL容器(rngq)list构造(guzo)、拷贝和析构操作操作效果效果list c产生空的产生空的listlist c1(c2)产生同类型的产生同类型的c1，并将复制，并将复制c2的所有元素的所有元素list c(n)利用类型利用类型T的默认构造函数和拷贝构造函数生的默认构造函数和拷贝构造函数生成一个大小为成一个大小为n的的listlist c(n,e)产
34、生一个大小为产生一个大小为n的的list，每个元素都是，每个元素都是elist c(beg,end)产生一个产生一个list，以区间，以区间beg,end为元素初值为元素初值list()销毁所有元素并释放内存。销毁所有元素并释放内存。第38页/共88页第三十八页，共89页。STL容器(rngq)list非变动性操作(cozu)操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量返回元素最大可能数量c1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断
35、判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2第39页/共88页第三十九页，共89页。STL容器(rngq)list赋值操作操作效果效果c1 = c2将将c2的全部元素赋值给的全部元素赋值给c1c.assign(n,e)将将e的的n个拷贝赋值给个拷贝赋值给cc.assign(beg,end) 将区间将区间beg;end的元素赋值给的元素赋值给cc1.swap(c2)将将c1和和c2的元素互换的元素互换swap(c1,c2)同上，全局函数同上，全局函数第40页/共88页第四十页，共89页。STL容器(rngq)list元素(yuns)存取 std:list l;/
36、empty std:cout l.front();/runtime error if(!l.empty()std:coutl.back();/ok 操作操作效果效果front()返回第一个元素的引用，不检查元素是否存在返回第一个元素的引用，不检查元素是否存在back()返回最后一个元素的引用，不检查元素是否存在返回最后一个元素的引用，不检查元素是否存在第41页/共88页第四十一页，共89页。STL容器(rngq)list迭代器相关(xinggun)函数操作操作效果效果begin()返回一个双向迭代器，指向第一个元素返回一个双向迭代器，指向第一个元素end()返回一个双向迭代器，指向最后一个元素
37、之后返回一个双向迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素第42页/共88页第四十二页，共89页。STL容器(rngq)list安插(nch)（insert）元素操作操作效果效果c.insert(pos,e)在在pos位置插入位置插入e的副本，并返回新元素位置的副本，并返回新元素位置c.insert(pos,n,e)在在pos位置插入位置插入n个个e的副本的副本c.insert(pos,beg,end)
38、 在在pos位置插入区间位置插入区间beg;end内所有元素内所有元素的副本的副本c.push_back(e)在尾部添加一个在尾部添加一个e的副本的副本c.push_front(e)在头部添加一个在头部添加一个e的副本的副本第43页/共88页第四十三页，共89页。STL容器(rngq)list移除（remove）元素(yuns)操作操作效果效果c.pop_back()移除最后一个元素但不返回移除最后一个元素但不返回c.pop_front()移除第一个元素但不返回移除第一个元素但不返回c.erase(pos)删除删除pos位置的元素，返回下一个元素的位置位置的元素，返回下一个元素的位置c.rem
39、ove(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的副本）的副本）第44页/共88页第四十四
40、页，共89页。STL容器(rngq)list特殊(tsh)变动性操作操作操作效果效果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)区间内所有元素区间内所有元素转移转移到到
41、c2的的pos之前之前第45页/共88页第四十五页，共89页。STL容器(rngq)list特殊(tsh)变动性操作（续）操作操作效果效果c.sort()以以operator 为准则对所有元素排序为准则对所有元素排序c.sort(op)以以op为准则对所有元素排序为准则对所有元素排序c1.merge(c2)假设假设c1和和c2都已排序，将都已排序，将c2全部元素转移到全部元素转移到c1并保证合并后并保证合并后list仍为已排序仍为已排序c.reverse()将所有元素反序将所有元素反序第46页/共88页第四十六页，共89页。STL容器(rngq)listlist应用(yngyng)实例：lis
42、t第47页/共88页第四十七页，共89页。STL容器(rngq)map/multimap使用平衡二叉树管理元素元素包含两部分(key,value)，key和value可以是任意类型必须包含的头文件#include根据元素的key自动对元素排序(pix)，因此根据元素的key进行定位很快，但根据元素的value定位很慢不能直接改变元素的key，可以通过operator直接存取元素值map中不允许key相同的元素，multimap允许key相同的元素第48页/共88页第四十八页，共89页。STL容器(rngq)map/multimap内部存储(cnch)结构749258111361012yyxyq
43、ywxzyqz第49页/共88页第四十九页，共89页。STL容器(rngq)map/multimap构造(guzo)、拷贝和析构操作操作效果效果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()销毁所有元素并释放内存。销
44、毁所有元素并释放内存。其中map可以是下列形式(xngsh)map一个以less（）为排序准则的map，map一个以op为排序准则的map第50页/共88页第五十页，共89页。STL容器(rngq)map/multimap非变动性操作(cozu)操作操作效果效果c.size()返回元素个数返回元素个数c.empty()判断容器是否为空判断容器是否为空c.max_size()返回元素最大可能数量返回元素最大可能数量c1=c2判断判断c1是否等于是否等于c2c1!=c2判断判断c1是否不等于是否不等于c2c1c2判断判断c1是否大于是否大于c2c1=c2判断判断c1是否小于等于是否小于等于c2第5
45、1页/共88页第五十一页，共89页。STL容器(rngq)map/multimap赋值操作操作效果效果c1 = c2将将c2的全部元素赋值给的全部元素赋值给c1c1.swap(c2)将将c1和和c2的元素互换的元素互换swap(c1,c2)同上，全局函数同上，全局函数第52页/共88页第五十二页，共89页。STL容器(rngq)map/multimap特殊(tsh)搜寻操作操作操作效果效果count(key)返回返回”键值等于键值等于key”的元素个数的元素个数find(key)返回返回”键值等于键值等于key”的第一个元素，找不到返回的第一个元素，找不到返回endlower_bound(ke
46、y) 返回返回”键值大于等于键值大于等于key”的第一个元素的第一个元素upper_bound(key) 返回返回”键值大于键值大于key”的第一个元素的第一个元素equal_range(key)返回返回”键值等于键值等于key”的元素区间的元素区间第53页/共88页第五十三页，共89页。STL容器(rngq)map/multimap迭代器相关(xinggun)函数操作操作效果效果begin()返回一个双向迭代器，指向第一个元素返回一个双向迭代器，指向第一个元素end()返回一个双向迭代器，指向最后一个元素之后返回一个双向迭代器，指向最后一个元素之后rbegin()返回一个逆向迭代器，指向逆向
47、遍历的第一个元素返回一个逆向迭代器，指向逆向遍历的第一个元素rend()返回一个逆向迭代器，指向逆向遍历的最后一个元素返回一个逆向迭代器，指向逆向遍历的最后一个元素第54页/共88页第五十四页，共89页。STL容器(rngq)map/multimap安插(nch)（insert）元素操作操作效果效果c.insert(pos,e)在在pos位置为起点插入位置为起点插入e的副本，并返回新元的副本，并返回新元素位置（插入速度取决于素位置（插入速度取决于pos）c.insert(e)插入插入e的副本，并返回新元素位置的副本，并返回新元素位置c.insert(beg,end)将区间将区间beg;end内
48、所有元素的副本插入到内所有元素的副本插入到c中中第55页/共88页第五十五页，共89页。STL容器(rngq)map/multimap移除（remove）元素(yuns)操作操作效果效果c.erase(pos)删除迭代器删除迭代器pos所指位置的元素，无返回值所指位置的元素，无返回值c.erase(val)移除所有值为移除所有值为val的元素，返回移除元素个数的元素，返回移除元素个数c.erase(beg,end) 删除区间删除区间beg;end内所有元素，无返回值内所有元素，无返回值c.clear()移除所有元素，清空容器移除所有元素，清空容器第56页/共88页第五十六页，共89页。STL容
49、器(rngq)map/multimapmap应用(yngyng)实例：map第57页/共88页第五十七页，共89页。STL容器(rngq)stack（实例：stack）后进先出（LIFO）#include核心接口push(value)将元素(yuns)压栈top()返回栈顶元素(yuns)的引用，但不移除pop()从栈中移除栈顶元素(yuns)，但不返回实例：stackstacktop()pop()push()第58页/共88页第五十八页，共89页。STL容器(rngq)queue（实例：queue）先进先出（FIFO）#include核心接口push(e)将元素置入队列front()返回队列
50、头部元素的引用(ynyng)，但不移除back()返回队列尾部元素的引用(ynyng)，但不移除pop()从队列中移除元素，但不返回实例：queuequeuefront()pop()push()back()第59页/共88页第五十九页，共89页。STL容器(rngq)priority_queue（实例：priority_queue）以某种排序准则（默认(mrn)为less）管理队列中的元素#include核心接口push(e)根据元素的优先级将元素置入队列top()返回优先队列头部最大的元素的引用，但不移除pop()从栈中移除最大元素，但不返回empty()队列是否为空第60页/共88页第六十
51、页，共89页。STL算法(sunf)STL提供了一些标准算法来处理容器内的元素搜寻、排序、拷贝、数值运算STL的算法是全局函数明确划分数据和操作泛型函数式编程模式(msh)所有算法可以对所有容器适用，甚至可以操作不同类型容器的元素算法头文件#include#includeSTL算法实例：algorithm第61页/共88页第六十一页，共89页。STL算法(sunf)区间（range）所有算法都用来处理一个或多个区间内的元素。区间可以但不一定涵盖容器内所有元素为了操作元素的某个子集必须将区间的首尾（iterator）当作两个参数传递给算法调用时必须确保区间有效性从起点出发(chf)，逐一前进，能
52、够到达终点。区间首尾两个迭代器必须属于同一容器，且前后放置正确无效区间可能会引起无限循环或者内存非法访问所有算法处理的都是半开区间begin,end)第62页/共88页第六十二页，共89页。STL算法(sunf)STL算法分类(fnli)非变动性算法（nonmodifyingalgorithms）变动性算法（modifyingalgorithms）移除性算法（removingalgorithms）变序性算法（mutatingalgorithms）排序性算法（sortingalgorithms）已序区间算法（sortedrangealgorithms）数值算法（numericalgorithms
53、）第63页/共88页第六十三页，共89页。STL算法(sunf)for_each()算法for_each(InputIteratorbeg,InputIteratorend,UnaryProcop)对区间beg,end)中的每一个元素(yuns)调用op(elem)返回op之后的容器副本op可以改变元素(yuns)op的返回值被忽略复杂度：O(n)示例:foreach第64页/共88页第六十四页，共89页。STL算法(sunf)非变动性算法既不改变(gibin)元素次序也不改变(gibin)元素值名称名称作用作用count()返回元素个数返回元素个数count_if()返回满足某一条件的元素个
54、数返回满足某一条件的元素个数min_element()返回最小元素（以迭代器表示）返回最小元素（以迭代器表示）max_element()返回最大元素（以迭代器表示）返回最大元素（以迭代器表示）find()搜寻等于某值的第一个元素搜寻等于某值的第一个元素find_if()搜寻满足某个准则的第一个元素搜寻满足某个准则的第一个元素search_n()搜寻具有某种特性的第一段搜寻具有某种特性的第一段“n个连续元素个连续元素”search()搜寻某个区间第一次出现的位置搜寻某个区间第一次出现的位置第65页/共88页第六十五页，共89页。STL算法(sunf)非变动性算法元素计数count(InputIt
55、eratorbeg,InputIteratorend,constT&value)计算(jsun)区间中值等于value的元素个数count(InputIteratorbeg,InputIteratorend,Predicateop)计算(jsun)区间中使判断式op结果为true的元素个数op接受单个参数，返回值为bool型复杂度：O(n)示例:count第66页/共88页第六十六页，共89页。STL算法(sunf)非变动性算法最小值和最大值min_element(InputIteratorbeg,InputIteratorend)min_element(InputIteratorbeg,In
56、putIteratorend,CompFuncop)max_element(InputIteratorbeg,InputIteratorend)max_element(InputIteratorbeg,InputIteratorend,CompFuncop)返回区间中最大或最小元素的位置（迭代器）无op参数的版本以（“小于”运算符）进行比较op用来比较两个元素：boolop(elem1,elem2)，如果(rgu)elem1“小于”elem2返回true否则返回false复杂度：O(n)示例:minmax第67页/共88页第六十七页，共89页。STL算法(sunf)非变动性算法搜寻元素find
57、(InputIteratorbeg,InputIteratorend,constT&value)返回区间中第一个“元素值等于value”的元素位置find_if(InputIteratorbeg,InputIteratorend,Predicateop)返回区间中第一个“使op结果为true”的元素位置如果没有(miyu)找到匹配元素，返回end复杂度：O(n)示例:find第68页/共88页第六十八页，共89页。STL算法(sunf)变动性算法直接改变元素(yuns)值或者在复制到另一区间过程中改变元素(yuns)值名称名称作用作用copy()从第一个元素开始正向复制某段区间从第一个元素开始
58、正向复制某段区间copy_backward()从最后一个元素开始反向复制某段区间从最后一个元素开始反向复制某段区间transform()变动（并复制）元素，将两个区间的元素合并变动（并复制）元素，将两个区间的元素合并merge()合并两个区间合并两个区间swap_ranges()交换两个区间的元素交换两个区间的元素fill()以给定值替换每个元素以给定值替换每个元素fill_n()以给定值替换以给定值替换n个元素个元素generate()以某项操作的结果替换每个元素以某项操作的结果替换每个元素第69页/共88页第六十九页，共89页。STL算法(sunf)变动性算法copy(s_beg,s_en
59、d,d_beg)将s_beg,s_end)区间内的元素复制到d_beg位置(wizhi)之后copy_backword(s_beg,s_end,d_end)将s_beg,s_end)区间内的元素复制到dend位置(wizhi)之前复杂度：O(n)示例:copy第70页/共88页第七十页，共89页。STL算法(sunf)移除性算法(sunf)移除某区间内的元素或者在复制过程中移除元素值名称名称作用作用remove()将等于某个特定值的元素全部移除将等于某个特定值的元素全部移除remove_if()将满足某准则的元素全部移除将满足某准则的元素全部移除remove_copy()将不等于某特定值的元素
60、全部复制到其他地方将不等于某特定值的元素全部复制到其他地方remove_copy_if() 将不满足某准则的元素全部复制到其他地方将不满足某准则的元素全部复制到其他地方unique()移除相邻的重复元素移除相邻的重复元素unique_copy()移除相邻的重复元素，并复制到其他地方移除相邻的重复元素，并复制到其他地方第71页/共88页第七十一页，共89页。STL算法(sunf)移除性算法remove(beg,end,value)移除区间beg,end)内和value相等的元素remove_if(beg,end,op)移除区间beg,end)内使操作op为true的元素remove和remove
61、_if只是将未移除元素向前移动，覆盖(fgi)移除元素，并返回新的终点，并没有真正删除元素，真正删除元素需要使用erase复杂度：O(n)示例:remove第72页/共88页第七十二页，共89页。STL算法(sunf)变序性算法通过元素的赋值和交换(jiohun)改变元素顺序名称名称作用作用reverse()将元素的次序逆转将元素的次序逆转reverse_copy()复制的同时逆转元素次序复制的同时逆转元素次序rotate()旋转元素次序旋转元素次序rotate_copy()复制的同时旋转元素次序复制的同时旋转元素次序random_shufle()将元素次序随机打乱将元素次序随机打乱parti
62、on()改变元素次序使改变元素次序使“符合某准则符合某准则”的元素移到前面的元素移到前面stable_partion()与与partion类似，但保持符合准则与不符合准则元类似，但保持符合准则与不符合准则元素的相对位置素的相对位置第73页/共88页第七十三页，共89页。STL算法(sunf)变序性算法逆转元素次序reverse(beg,end)将beg,end)区间内的元素逆序reverse_copy(s_beg,s_end,d_beg)将s_beg,s_end)区间内的元素逆序后拷贝到从d_beg开始的区间示例：reverse旋转(xunzhun)元素次序rotate(first,middl
63、e,last)将first,last)区间内的元素，从middle位置分为first,middle)和middle,last)两部分，将两部分交换位置示例：rotate复杂度：O(n)第74页/共88页第七十四页，共89页。STL算法(sunf)排序算法需要(xyo)动用随机存取迭代器名称名称作用作用sort()对所有元素排序对所有元素排序stable_sort()对所有元素排序，并保持相等元素间的相对次序对所有元素排序，并保持相等元素间的相对次序partial_sort()排序，直到前排序，直到前n个元素就位个元素就位nth_element()根据第根据第n个位置排序个位置排序make_he
64、ap()将区间转换为将区间转换为heappush_heap()将一个元素加入将一个元素加入heappop_heap()从从heap中移除一个元素中移除一个元素sort_heap()对对heap进行排序（排序后不再是进行排序（排序后不再是heap）第75页/共88页第七十五页，共89页。STL算法(sunf)排序算法对所有元素排序sort(beg,end)sort(beg,end,op)stable_sort(beg,end)stable_sort(beg,end,op)不带op参数的版本使用(“小于”运算符)对区间beg,end)内的所有元素排序带op参数的版本使用op(elem1,elem2
65、)为准则对区间beg,end)内的所有元素排序sort和stable_sort的区别是，后者保持(boch)相等元素原来的相对次序不能对list调用这些算法，因为list不支持随机存取迭代器复杂度：O(nlogn)示例：sort经过优化的快速排序算法归并排序算法第76页/共88页第七十六页，共89页。STL算法(sunf)排序算法局部(jb)排序partial_sort(beg,sortEnd,end)partial_sort(beg,sortEnd,end,op)不带op参数的版本使用(“小于”运算符)对区间beg,end)内的元素排序，使区间beg,sortEnd)内的元素有序带op参数的
66、版本使用op(elem1,elem2)对区间beg,end)内的元素排序，使区间beg,sortEnd)内的元素有序复杂度：O(n)和O(nlogn)之间示例：psort堆排序算法第77页/共88页第七十七页，共89页。STL算法(sunf)排序算法根据第n个位置排序nth_element(beg,nth,end)nth_element(beg,nth,end,op)对区间beg,end)内的元素排序，使所有在位置n之前的元素都小于等于它，所有在位置n之后的元素都大于等于它，从而得到两个分隔开的子序列，但子序列并不一定有序。不带op参数的版本使用(shyng)运算符作为排序准则带op参数的版本
67、使用(shyng)op(elem1,elem2)作为排序准则复杂度：O(n)示例：nsort快速排序算法第78页/共88页第七十八页，共89页。STL算法(sunf)排序算法堆排序算法（heapsort）heap是一种特殊的元素组织方式，可以被视为完全二叉树第一个元素总是最大（大顶堆），任意(rny)节点元素大于其孩子节点总是能够在对数时间内增加或移除一个元素98677553641234第79页/共88页第七十九页，共89页。STL算法(sunf)排序算法heap算法make_heap()将某区间内的元素转化为heap，复杂度O(n)push_heap(beg,end)beg,end-1)原本
68、就是heap，将end之前的那个元素加入使区间beg,end)重新成为heap，复杂度O(logn)pop_heap(beg,end)从区间beg,end)取出第一个元素，放到最后位置，区间beg,end-1)重新组成heap，复杂度O(logn)sort_heap()将heap转换为一个有序集合，复杂度O(nlogn)可以用运算符或op(elem1,elem2)作为排序准则(zhnz)示例：heap第80页/共88页第八十页，共89页。STL算法(sunf)已序区间算法所作用的区间以按某种准则(zhnz)排序名称名称作用作用binary_serach()判断区间内是否包含某个元素判断区间内是
69、否包含某个元素includes()判断区间内的每个元素是否都包含在另一个区间中判断区间内的每个元素是否都包含在另一个区间中lower_bound()搜寻第一个搜寻第一个“大于等于给定值大于等于给定值”的元素的元素upper_bound()搜寻第一个搜寻第一个“大于给定值大于给定值”的元素的元素equal_range()返回返回“等于给定值等于给定值”的元素构成的区间的元素构成的区间merge()将两个区间的元素合并将两个区间的元素合并set_union()求两个区间的并集求两个区间的并集set_intersection()set_difference()求两个区间的差集求两个区间的差集第81页
70、/共88页第八十一页，共89页。STL算法(sunf)已序区间算法boolbinary_serach(beg,end,value)boolbinary_serach(beg,end,value,op)判断已序区间beg,end)内是否(shfu)包含“和value相等”的元素op可以作为排序准则返回值只说明搜寻的值是否(shfu)存在，不指明位置调用者必须确保区间已序复杂度：使用随机存取迭代器为O(logn)，否则是O(n)示例：bserach第82页/共88页第八十二页，共89页。STL算法(sunf)已序区间算法lower_bound(beg,end,value)upper_bound(b
71、eg,end,value)lower_bound(beg,end,value,op)upper_bound(beg,end,value,op)lower_bound()返回第一个大于等于value的元素位置(wizhi)，既可以插入value且不破坏区间已序性的第一个位置(wizhi)upper_bound()返回第一个大于value的元素位置(wizhi)，既可以插入value且不破坏区间已序性的最后一个位置(wizhi)op可以作为排序准则调用者必须确保区间已序复杂度：使用随机存取迭代器为O(logn)，否则是O(n)示例：bound第83页/共88页第八十三页，共89页。STL算法(su
72、nf)数值算法以不同(btn)的方式组合数值元素#include名称名称作用作用accumulate()组合所有元素（求和，求积，组合所有元素（求和，求积，）inner_product()组合两区间内的所有元素的内积组合两区间内的所有元素的内积adjacent_difference()将每个元素和其前一元素组合将每个元素和其前一元素组合partial_sum()将每个元素和其先前所有元素组合将每个元素和其先前所有元素组合第84页/共88页第八十四页，共89页。STL算法(sunf)数值算法accumulate(beg,end,initValue)accumulate(beg,end,initV
73、alue,op)对于序列：a1,a2,a3,第一种形式(xngsh)计算initValue+a1+a2+a3+第二种形式(xngsh)计算initValueopa1opa2opa3op示例：accu第85页/共88页第八十五页，共89页。STL算法(sunf)数值(shz)算法inner_product(beg1,end1,beg2,initValue)inner_product(beg1,end2,beg2,initValue,op1,op2)对于序列：a1,a2,a3,;b1,b2,b3,第一种形式计算initValue+(a1*b1)+(a2*b2)+(a3*b3)+第二种形式计算ini
74、tValueop1(a1op2b1)op1(a2op2a2)op示例：inner第86页/共88页第八十六页，共89页。参考(cnko)书籍数据结构(shjjiu)C+标准程序库第87页/共88页第八十七页，共89页。感谢您的欣赏(xnshng)！第88页/共88页第八十八页，共89页。内容(nirng)总结主要内容。特殊容器：stack、queue，priority_queue。class ex_class。ch.set_value(a)。rbegin()返回一个(y )逆向迭代器，指向逆向遍历的第一个(y )元素。除了具备双向迭代器的所有属性，还具备随机访问能力。返回一个(y )逆向迭代器，指向逆向遍历的第一个(y )元素。以op为排序准则，以区间beg,end内的元素产生一个(y )map。返回”键值等于key”的元素个数。感谢您的欣赏第八十九页，共89页。
