C++STL-数据结构与算法实现334

C++STL基础泛型编程技术参考书2／13参考书3／13课程内容第一章

STL

概述第二章

模板与重载第三章输入输出流第四章

string第五章

容器第六章通用算法与迭代器第七章

非可变序列算法第八章可变序列算法第九章

排序与查找算法第十章数值算法4／13第一章STL概述STL导言STL内容简介泛型编程与STLSTL程序的头文件命名空间namespace命名空间应用例5／13STL(StandardTemplateLibrary)

导言C++：应用越来越广泛STL：C++的一部分，编程时不需安装额外插件STL：众多技术人员经验的结晶，不用重复开发直接使用！提高开发效率和代码质量如：栈、队列、堆、树等数据结构及算法招聘：熟练掌握STLSTL导言6／13STL内容简介包括：容器、算法、迭代器（还包括其他的）容器数组、链表、队列、堆、栈、树、哈希表等数据结构直接定义并使用，功能强大，可用多种数据类型算法

增加、删除、查找、修改、排序等直接调用这些函数，实现相应功能迭代器指针的泛型，使算法操作容器中数据其他string类、I/O流类，函数对象，内存配置器等STL内容简介7／13泛型编程(GenericProgramming,GP)泛型数据类型参数化——把数据类型定义为变量，使用时才生成它的具体类型（实例化／特化），实现将算法与数据结构完全分离。目的：代码重用泛型编程

——用模板编程（函数模板／类模板）将常用数据结构（如栈／队列／链表／树）和算法（如排序／查找）写成模板，不论数据结构里面存放何种类型数据，不必再重新编写算法！STL——数据结构和算法的模板集合不必再编写这些数据结构和算法，代码质量很高泛型编程与STL8／13STL程序的头文件开发环境：VC++2012(VS2012)头文件位置：X:\VS2012\VC\include\STL程序的头文件序号功能头文件备注1迭代器#include<iterator>2I/O流#include<iostream>标准I/O#include<fstream>文件I/O#include<sstream>字符串I/O3字符串#include<string>string类4函数对象#include<functional>9／13STL程序的头文件STL程序的头文件序号功能头文件备注5容器#include<vector>向量容器#include<deque>双端队列#include<list>链表容器#include<query>队列/优先队列#include<stack>栈#include<set>集合/多重集#include<map>映射/多映射6算法#include<algorithm>7数值算法#include<numeric>10／13namespaceusingnamespacestd;命名对象变量、函数、类、结构体，…名称冲突开发大规模软件不同厂家(程序员)开发的类库／函数库，可能存在相同的函数名或类名（重名），使用哪一个呢？例：两个库都有fun函数，怎么确定用哪一个呢？解决方法using

namespace

指定名称空间std:C++标准库所有名称都在该命名空间中命名空间11／13#include<iostream>usingnamespacestd;//可后置于main前吗？namespace

myfun//命名空间{voidfun()//定义在myfun中 {cout<<"使用myfun中的fun()"<<endl;}

};namespace

yourfun//命名空间{voidfun()//定义在yourfun中 {cout<<"使用yourfun中的fun()"<<endl;}};命名空间应用例12／13//usingnamespacestd;//前面的可放在此处吗usingnamespacemyfun;//主要用myfunintmain(){ fun();//myfun::fun();

yourfun::fun();//临时用yourfun return0;}命名空间应用例13／13C++STL基础泛型编程技术第二章模板与重载模板概念函数模板类模板类模板继承模板特化操作符重载15／31引入模板——代码重用C++是强类型语言，函数或类的功能类似，只要数据类型不同，就要编写多份代码，增加了编程量和源程序长度。例：求a,b最大值，需编写四个函数（四份代码）intMax(inta,intb){return(a>b)?a:b;}floatMax(floata,floatb){return(a>b)?a:b;}doubleMax(doublea,doubleb){return(a>b)?a:b;}charMax(chara,charb){return(a>b)?a:b;}模板概念只写一份代码适用多种类型——模板功能相同16／31函数模板编写一个函数模子，用这个模子制造出若干功能相同，参数类型和返回类型不同的函数——模板函数函数模板的声明template<classT>//T:类型是参数TMax(Ta,Tb) {return(a>b)?a:b;}//-----------如此，就做好了一个函数模板------------在调用Max函数时，根据实参类型确定T：intx=2,y=5;cout<<Max(x,y);//T→

int函数模板17／31函数模板简例18／31函数模板中使用多种类型函数模板中可用多种类型参数——T1,T2每种类型参数前加class问：a,b可否实例化为相同类型？19／31函数重载参数类型不同参数个数不同问：左边两个重载的函数模板的类型参数T

是否可以被实例化为不同的类型？函数模板重载20／31函数模板与普通函数重载函数模板重载21／31类模板(类属类／类生成类)概念像函数模板一样，类模板是生成具体类的一个模子目的把成员变量的类型、成员函数参数的类型、返回值的类型参数化，使之能适用于多种数据类型定义类模板template<classT>//类型参数T，与函数模板一样class类名//类的定义{…//类体};类模板及定义22／31//定义栈的一个类模板constintn=10;template<class

T>//数据类型参数化classStack

//定义类（类模板）{

Tstk[n];//顺序栈，T为元素类型（可变）

inttop;//栈顶元素的位置，int不变public:Stack(){top=-1;}//构造函数，初始化栈顶

voidpush(Tob);//入栈函数，T为参数的类型

Tpop();//出栈函数，T为返回值类型};类模板定义举例23／31template<classT>voidStack<T>::push(Tob){if(top==n-1){cout<<"Stackfull";return;}stk[++top]=ob;}成员函数的类外实现template<classT>TStack<T>::pop(){if(top<0){cout<<"Stackempty";return(0);}returnstk[top--];}观察：与普通类的成员函数实现有何差别？24／31类模板实例化

——生成具体的类，由它创建对象

类名<实际类型>对象名;类模板实例化T具体化25／31全局类型与模板类型同名——局部优先（全局与局部的关系）typedefstring

type;//全局类型名template<classtype>//局部类型名classG{

typen;//n是什么类型？……};//n不是string类型类模板的其他语法规则26／31类型参数可带缺省类型左←右复习：函数参数带缺省值template<classT1=char,classT2=int>classA{

T1m1;T2m2;……};又例：template<classT1=int,classT2>classX;//错template<classT1,classT2=int>classY;//对//实例化时只给一个具体类型，给予谁？类模板的其他语法规则27／31A<>a("abc");//缺省实例化A<double>b;

//1个实参A<int,bool>c;//2个实参不要混淆：类型实例化与变量初始化类模板实例化：类型参数带缺省值template<classT1=char,classT2=int>classA{T1m1;T2m2;};intmain(){

//创建对象时A<int,double>c1;//指定两个类型A<bool>c2;//第二类型参数采用缺省类型A<>c3;//两个类型参数都用缺省类型//空的<>不能省略！}类模板的其他语法规则28／31类模板组合内嵌其他类模板的对象template<classU>

classA{A<U>*p;//本类可省略<U>不写。错：A<>*p;};template<classU>classB{A<U>&a,*b;//<U>不可省略，内嵌对象其他模板类的}类模板的其他语法规则29／3130／73类模板派生<T2>不能省略A<tt1>可否?实验分析2个类模板实例化：创建对象构造函数模板特化函数模板实例化用它生成具体的函数（模板函数）——适用多种数据类型类模板实例化用它生成具体的类（模板类）——适用多种数据类型模板特化特殊的实例化对于某种数据类型，不能用模板的通用实例化方法来生成具体的函数或类时，对这种数据类型设计专门的实例化方案——函数模板特化、类模板特化模板特化31／31函数模板特化不能处理t1和t2是char数组的情况专门处理t1和t2是char数组的情况32／31类模板特化完全特化（全特化）对模板的全部类型参数进行特化部分特化（偏特化）对模板的部分类型参数进行特化完全特化下例：类模板特化33／3134／73实例：类模板全特化部分特化template<classT1,classT2>classvector{

//…//};template<classT>//部分特化：还有类型参数Tclassvector<bool,T>//第一个参数为具体类型bool{//第二个参数T没有具体化

//…//};类模板部分特化35／31引入加法例1复数c1=3+4i，c2=5-10i

加法

c=c1+c2=(3+5)+(4-10)i=8-6i加法例2chars1[]="Chi",s2[]="na";

加法

s1

+

s2="China";C++的“+”运算符能实现如此的加法吗？重载“+”，扩展“+”功能，完成新任务

——运算符重载（即运算符函数重载）操作符重载概念36／31返回类型

operator

运算符(形参表){

...//该运算符函数代码}注意：运算符必须是系统定义的，如+,-,=,…不允许重载的运算符.成员访问运算符，如：obj.length().*成员指针访问运算符，如：obj.*pt::域限定符，如：obj::fun()sizeof如：sizeof(int)?:条件运算符，如：x>y?x:y操作符重载的方法运算符函数37／31操作符重载例复数加法例38／31操作符重载例c3=c1+c2

执行函数调用：c3=c1.operator+(c2);39／31运算符函数的重载方式类的成员函数（本讲义）类的友元函数（破坏类封装，不建议）单目／双目运算符重载双目运算符+，执行a+b操作数a和b为A类对象+函数为A类成员函数a+b

等价于a.operator+(b)前置单目运算符++，执行++a++函数不需形参：operator++();后置单目运算符++，执行++aoperator++(int);int参数与前置区别运算符函数40／31单目运算符重载例41／31重载不能改变运算符的操作数个数，例如：><

重载前：二元运算符，需两个操作数重载后：仍是二元运算符*&…既可以是二元运算符，也可以是一元运算符。重载不能改变运算符的优先级，例如：*/优先级高于+-运算符重载函数不能有默认形参否则，改变了参数（操作数）个数重载的运算符功能应与原功能相近，例如：+重载：string对象连接，便于理解操作符重载的限制42／31运算符函数的形参至少有一个是对象或对象的引用，保证重载运算符用于自定义类型（防止修改运算符原功能），例：intoperator+(inta,intb)//错误{return(a-b);}重载赋值运算符=当它执行同类对象的赋值运算时——逐个复制对象的数据成员当对象中有指针成员时，完成对象的“浅拷贝”，因此重载=，完成对象的“深拷贝”。操作符重载的限制43／31重载目的自定义类型的数据不能直接用<<和>>如结构体、类重载它们——输入输出自定义类型的数据重载形式istream&operator>>(istream&,自定义类型&);ostream&operator<<(ostream&,自定义类型&);重载限制只能重载>>和<<为友元函数或普通函数，不能将它们重载为类的成员函数｡重载举例后面章节第八章:max()与min()算法重载：流操作符>>和<<44／31C++STL基础泛型编程技术第三章输入输出流STL中I／O流类标准输入输出流前修课文件输入输出流前修课字符串输入输出流46／33STL：提供若干个类模板，实现输入输出功能。位于std命名空间内：usingnamespacestd;使用灵活、方便，功能强大标准I／O流类istream,ostream,iostream文件I／O流类ifstream,ofstream,fstream字符串I／O流类istringstream,ostringstream,stringstreamSTL中I／O流类47／33标准输入输出流对象cin，cout，重载运算符>>和<<标准输入输出流类空白字符空格/换行/TAB…数据分隔符，>>跳过这些空白字符。如何改进程序？48／33流对象的get系列成员函数int

get();

//无参数功能：读一个字符（含空白字符）返回：该字符的ASCII值(int)

get(char*ch,intn,charc='\n');

//3个参数

getline(char*ch,intn,charc='\n');功能：读n-1个字符(含空白字符)，存入字符数组

ch；遇终止字符c提前结束区别：get遇终止字符时，读位置停留在终止符前，

下次从该位置读取；getline则跳过终止符。返回：输入流对象*thisget系列成员函数49／33intmain(){charch[20]; cout<<"输入字符串:";//Howareyou?

intn=cin.get();cout<<n<<endl;

cin.getline(ch,20);

cout<<"该字符串是:"<<ch<<endl;cout<<"输入字符串:";//12345\7890

cin.getline(ch,20);

//cin.getline(ch,20,'\\');cout<<"该字符串是:"<<ch<<endl;return0;}get系列流成员函数例把上面getline都改为get，输出？50／33问题引入本要输入int数据，结果输入含有其他字符，如何发现和处理这类错误呢？用相关成员函数booleof()返回true：已到达流的末尾boolfail()返回true：I/O操作失败，遇到非法数据（如读取数字时遇到其他字符），流可以继续使用。boolbad()返回true：遇致命错误（物理的），流不能使用。利用流错误信息51／33intmain(){

inta;cout<<"请输入一个整数：";while(1)

{cin>>a;//要求输入整数

if(cin.fail()) {//--------输入数据非法----------- cout<<"输入有错！请重新输入"<<endl;

cin.clear();

//清除流所有标志位

cin.sync();

//清空流缓冲区

}else//---输入数据合法-----------

{cout<<a<<endl;break;}}}例：流错误信息这样写的保护代码并不好！逐个字符判断是否数字。52／33文件I／O流类二进制文件与文本文件二进制文件——字节序列

文件数据与内存数据的格式相同。shortint:5678

内存格式：0001011000101110

存入文件

2字节

每个字节不对应一个字符

人不能阅读（乱码）文本文件——字符序列用某编码ASCII,UNICODE,…把内存数据转换为字符序列后

存入文件。举例：shortint:5678转换为字符序列5678

4字符存入文件4字节

十进制ASCII：5(53),6(54),7(55),8(56)

00110101001101100011011100111000

5

6

7853／33文件流类流对象与某个文件绑定／关联后，流对象即该文件。读写该流对象，就是读写该文件cin:系统定义的流对象，绑定为键盘设备文件cout:系统定义的流对象，绑定为屏幕设备文件ofstream：输出类，写文件：内存→文件ifstream：输入类，读文件：内存←文件fstream：

I／O类，读／写文件头文件#include<fstream>文件I／O流类54／33读写文件的三步打开文件

选择文件流类，创建流对象，与文件绑定读写文件写(Output)：内存变量→文件读(Input)：内存变量←文件关闭文件读写文件完毕后，及时关闭文件下面讲述具体操作读写文件的步骤55／30打开文件创建流对象的同时打开文件

ifstream

in("test.dat",ios::in);创建流对象后，用open成员函数打开

ofstream

out1,out2;out1.open("d:\\test.dat",ios::out);out2.open("..\\test.dat",ios::out);文件名（含路径）

文件名包含路径(绝对路径／相对路径／缺省路径)

可用字符串变量保存文件名，例如：

charfilename[]="d:\\test.dat";

in.open(filename,ios::in);打开文件缺省路径绝对路径相对路径56／30打开文件方式标志的组合举例ios::in|ios::binary二进制方式，读文件ios::out|ios::binary二进制方式，写文件ios::in|ios::out

文本文件方式，可读写

ios::in|ios::out|ios::binary

二进制方式，可读写多个标志共用一个32bits

整数的若干位标志位组合：|

文件打开标志57／30检查文件打开是否成功方式一用流对象的成员函数fail检查

ifstream

in;in.open("test.dat",ios::in)if(in.fail()==true)cout<<"打开文件失败";elsecout<<"打开文件成功";检查文件打开58／30方式二

检查流对象是否等于0if流对象=0，打开失败

else，打开成功---------------------------------------------------

ifstreamin("test.dat",ios::in);if(in==0)//if(!fin)cout<<"打开文件失败";elsecout<<"打开文件成功";检查文件打开59／30文件操作完后应及时关闭，同时打开的文件数有限文件关闭解除流对象与文件的绑定／关联。解绑后，该流对象还可与其他的文件绑定。举例：ofstreamout("demo.txt",ios::out);//out与demo.txt文件关联...…;out.close();//用完后及时关闭out.open("test.dat",ios::out|ios::binary);//out与test.dat文件关联关闭文件60／30读写文本文件写入文本文件：<<流插入符读取文本文件：

>>流提取符与cout<<,cin>>用法和效果一样cin,cout

换成了文件流对象关联某文件>>读文本文件①有字符转换；②忽略空白字符不希望字符转换：用二进制函数read

不希望忽略空白字符：用函数get,getline读写文本文件61／30<<写文本文件例<<

可输出不同类型的数据\t输出数据对齐

tab制表符endl输出\n回车符62／33getline()

读文本文件例63／33读写二进制文件任何类型文件均可用二进制方式读写不用<<

和>>读写字符转换——不希望的文件打开方式默认为文本方式in.open("myfile.dat",ios::in|ios::binary);二进制文件读写函数ostream&file.write((char*)buffer,intlen);istream&file.read((char*)buffer,intlen);file流对象

buffer内存块首地址 len读写字节数，sizeof(…)获得char*按字节读写

读写二进制文件filebufferwriteread64／30举例：读写二进制文件65／33举例：读写二进制文件66／33随机访问文件顺序访问文件：从头至尾读写文件随机访问文件：从文件内任意位置处开始读写注意：文本文件存在字符转换文件位置指示符（文件指针）定义：文件的当前读写位置，存在于流对象内部文件读写过程：

每读写一个字节，文件指针前移一个字节

前移：文件头→尾方向移动随机读写文件67／30移动文件指针，实现随机读写文件ostream&seekp(long,int)//p:put,写文件用

istream&seekg(long,int)//g:get,读文件用

移动文件指针到指定位置：(long,int)int

取值：ios::beg文件头ios::end

文件尾

ios::cur

目前位置(current)long

取值：偏移量(字节)232=4GB

正数

:文件指针→向文件尾移动的字节数

负数

:文件指针←向文件头移动的字节数随机读写文件的函数文件头文件尾当前位置-+68／30移动文件指针例：

out.seekp(20L,ios::beg);//out:流对象获得文件指针longtellp()//写文件用longtellg()//读文件用

返回

值：

//232=4GB——现在的读写位置(相对文件头的字节数)——0：文件头用以上流成员函数，即可实现文件随机读写随机读写文件的函数69／30例：随机读写文本文件光标在这70／30#include<iostream>#include<fstream>usingnamespacestd;voidmain()

{

ifstreamfile("demo.txt",ios::in);if(!file){cout<<"文件打开失败";return;}

longoffset;//偏移量

charch;

//当前读取的字符

intnext;//下一个待读取的字符cout<<"打开位置："<<file.tellg()<<endl;

cout<<"定位到文件尾"<<endl;

file.seekg(0L,ios::end);cout<<"当前位置："<<file.tellg()<<endl;

cout<<"定位到文件头"<<endl;

file.seekg(0,ios::beg);cout<<"当前位置："<<file.tellg()<<endl<<endl;例：随机读写文本文件71／30例：随机读写文本文件72／30二进制方式读写文本文件0xa=1073／33字符串I/O流

流对象与string绑定，而非与文件或标准设备绑定用法与标准I/O相同#include<sstream>STL定义三种字符串流类

istringstream

输入流，读string

ostringstream

输出流，写string

stringstream

I/O流，读写string字符串Ｉ／Ｏ流类74／33例1：字符串Ｉ／Ｏ流流对象与string绑定I/O操作的是string75／33例2：字符串Ｉ／Ｏ流76／33用字符串流来进行数据类型转换方便例3：字符串Ｉ／Ｏ流77／33C++STL基础泛型编程技术第四章C++stringstring：创建string：迭代器string：容量string：访问元素string：修改内容string：串操作string：综合示例79／26C++字符串'\0'结束的char数组。理解：字符与字符串的区别STL的string类提供string类操作字符串。使用简便，功能强大构造string对象（初始化）stringstr//str:空字符串stringstr("LiSi")//字符串常量初始化stringstr(s)//变量s:string成员或char[]stringstr(s,2)//s[2…end]初始化stringstr(s,2,5)//s[2…5]初始化stringstr(5,'c')//str:5个字符'c'stringstr(s.begin(),s.end())//迭代器字符串创建不能用数值或字符初始化string对象80／26例：字符串创建与初始化81／26迭代器（Iterator）——类似指针begin()迭代器：指向容器vec第一个元素end()迭代器：指向容器vec最后一个元素之后rbegin()反向迭代器：指向容器vec最后一个元素rend()反向迭代器：指向容器vec第一个元素之前反向迭代器++/--++/

--运算方向相反不是每种迭代器都允许反向迭代器，如流迭代器字符串迭代器++++4个迭代器82／26例：字符串迭代器83／26容量（Capacity）size()和length()：返回字符串长度empty()：判断字符串是否为空clear()：清空字符串max_size()：返回字符串最大长度(4294967294)resize()：修改字符串多去少补，不重新分配空间capacity()：不重新分配内存的最大字符数reserve()：增加字符串空间字符串容量84／26例：字符串容量改为16,32，观察容量变化85／26访问元素（ElementAccess）——单个字符

方式1：str[n]

方式2：str.at(n)返回：当前字符串str第n个字符(0…n-1)at()：越界时触发异常用try{…}catch(…)进行出错处理

[]：越界时触发断言assert在Debug版本起作用的宏

用于检查“不应该”发生的情况。运行过程中如果触发assert，程序中止，出现提示信息。——调试技术访问字符串的元素86／26例：访问字符串的元素87／26isalnum(c)isdigit(c)isalpha(c)iscntrl(c) isgraph(c)isprint(c)islower(c)isupper(c)ispunct(c) isspace(c)isxdigit(c) tolower(c)toupper(c)字符串中的字符处理c是字母或数字

c是数字c是字母

c是控制符

c是可打印字符c是可打印字符c是小写字母c是大写字符c是标点符号 c是空白字符c是十六进制0-F转换为小写字母转换为大写字母88／26修改（Modifiers）assign() 赋值（灵活）+= 追加字符串（简单）append() 追加字符串（灵活）push_back() 追加单个字符insert() 插入字符串erase() 删除部分字符replace() 替换部分字符swap() 与另一字符串交换内容用法举例修改字符串89／26例：修改字符串——赋值90／26例：修改字符串——追加s1+="W"; cout<<s1<<endl;91／26例：修改字符串——插入与删除s2.insert(5,"Y")92／26例：修改字符串——替换与交换93／26c_str()

返回const

char*data() 返回constchar*_Copy_s() 复制到char[]find()

查找（前→后）rfind() 查找（前←后）find_first_of() 查找第一次出现位置find_last_of() 查找最后一次出现位置find_first_not_of()find_last_not_of()substr()

获得子串compare() 串比较。比较运算符更简单字符串操作兼容C用法类似94／26例：字符串操作——C_stringconst不去掉的理由？需要非const怎么办？从原串第2个位置开始拷贝5个字符95／26例：字符串操作——find()找到了？没找到？96／26例：字符串操作——find()97／26例：字符串操作——rfind()98／26find_first_of()与find_last_of()find_first_of()：头→尾查找find_last_of()：头←尾查找99／26find_first_not_of()find_first_not_of()：头→尾查找find_last_not_of()：头←尾查找100／26例：字符串操作——substr()101／26字符串综合举例新增成员函数实现类型转换和修剪修剪串：去首尾空格类型转换:stringtointinttostring功能要求102／26103／26C++STL基础泛型编程技术第五章STL容器容器分类、特点、共性序列容器：向量vector序列容器：双端队列deque序列容器：链表list关联容器：集合set关联容器：映射map关联容器：Hash集合关联容器：Hash映射容器适配器105／73容器Container存放同类型元素的类模板：容器分类标准容器(通用容器)容器适配器(特殊容器)容器顺序容器关联容器vectordequelistset,multisetmap,multimaphash_set,hash_multisethash_map,hash_multimapstackqueuepriority_queue106／73顺序容器：元素有序ordered，但未排序sorted关联容器：元素按关键字(key)排序，快速查找容器适配器：修改容器接口，具备新特点顺序容器SequenceContainersvector<T>

向量——应用广泛动态数组：大小自动调整随机访问：连续存放，常量时间插入删除：末端快，其他位置慢（移动元素）重新分配空间：保留内存不够时，空间加倍——

元素复制如对象需构造和析构选择容器：顺序容器特点107／73deque<T>

双端队列(double-endedqueue)存储格式：块内顺序+块间链表，逻辑上连续随机访问：速度远不如

vector（严重缺点）插入删除：两端快（优点），其他位置慢空间分配：无保留空间(reserved)，增加一块连续

空间连入即可，速度比vector快很多list<T>链表存储结构：双向循环链表每个结点放一个元素顺序访问元素双向，不能随机访问不能用[],at()不存在空间不够：无容量和内存重新分配函数任何位置上插入删除效率高（优点）选择容器：顺序容器特点108／73关联容器AssociatedContainers——快速查找容器元素:

<key,value>对,按key有序数据结构：平衡二叉树BBTBalancedBinaryTree

红黑树RB-Tree——快速查找set<key>

集合

只一个查找键key，且唯一相等multiset<key>

多重集合只一个查找键key，可重复map<key,value>

映射

key–value对，key唯一multimap<key,value>

多重映射

key–value对，key可重复选择容器：关联容器特点按key排序109／73有些编译器VC2005增加了4种关联容器类型：数据结构：散列表

Hash表查找时间效率更高hash_set<key>

散列集

#include<hash_set>hash_multiset<key>

散列多重集

#include<hash_set>hash_map<key,value>

散列映射

#include<hash_map>hash_multimap<key,value>

散列多重映射

#include<hash_map>选择容器：关联容器特点key无序过时的，淘汰的MSDN110／73容器适配器ContainerAdapter修改原容器basecontainer，具备新特点容器适配器：不提供迭代器stack 栈

STL:deque 后进先出LIFOqueue 队列

STL:deque先进先出FIFOpriority_queue优先队列

STL:

vector优先：每个元素有一个优先值=key名为队列，实非队列：不满足FIFO堆heap

：max-heap,min-heap

复习数据结构

STL

默认：max-heap

优先值最高(大)者先“出队”选择容器：容器适配器特点111／73似容器almostcontainer，拟容器——像容器，但与真正容器不尽相同string

字符串元素类型：不像容器可选择各种数据类型专门优化：用法与容器有差别valarray<T>

值数组为数值计算而优化的向量提供数值运算和数学函数bitset<N>

位集合提供二进制位集合位数N的各种操作方便二进制位运算选择容器：似容器特点112／73缺省构造函数：容器类的默认初始化拷贝构造函数：生成现有容器的副本析构函数：

不需要容器时整理内存empty()

容器中元素个数=0返回truemax_size()

返回容器最多能容纳的元素个数size()

返回容器中当前元素个数容器赋值：=

一个容器赋给另一个容器容器比较：<<=>>===!=

两个容器比较，条件成立返回true

不适于priority_queueswap() 交换两个容器的元素容器共性一般不关心113／73begin()

返回(const_)iterator

指向第一个元素end()

返回(const_)iterator

指向最后一个元素之后rbegin()

返回(const_)reverse_iterator

指向最后一个元素rend()

返回(const_)reverse_iterator

指向第一个元素之前erase()

删除若干个元素clear()

删除全部元素标准容器共性114／73例：vector构造与初始化string数组头文件v4有几个元素？类型？v5有几个元素？类型？问题115／73例：vector容量230-1capacity()：???重新分配内存前的最大容量下页116／73例：vector容量想一想：怎么显示vector中的每个元素？117／73

下标操作符vt[index] 返回：index元素的引用

可读可写成员函数vt.at(index) 返回：index元素的引用vt.front() 返回：第一个元素的引用vt.back() 返回：最后一个元素的引用迭代器位置指示iterator

vt.begin()reverse_iteratorvt.rbegin()iteratorvt.end()

reverse_iteratorvt.rend()vector访问元素vector<typenameT>vt118／73例：vector访问元素119／73例：vector判空初始化向量v逐个添加元素结构体逐个读取元素逐个删除元素capacity=?删除操作自动减少vector的容量吗？120／73例：vector插入元素//下页容器内元素变化使迭代器失效插入元素自动增加vector容量121／73例：vector插入元素回顾122／73元素赋值voidassign(size_type_Count,constType&_Val); _Count:_Val个数，_Val:容器元素值(赋值)template<classIterator>//输入型迭代器voidassign(Iterator_First,Iterator_Last);//区间删除元素iteratorerase(const_iterator_Where);//删除位置iteratorerase(const_iterator_First,const_iterator_Last);voidpop_back(); //erase(end()-1,end())voidclear(); //erase(begin(),end())交换元素voidswap(vector<Type,Allocator>&_Right);friendvoidswap(vector<Type,Allocator>&_Left, vector<Type,Allocator>&_Right);vector元素：赋值删除交换123／73赋值（一）赋值（二）元素地址交换的是什么？元素值？地址？earse()怎么用？124／73deque

特点接近于vector与vector比较选择容器优点：两端插入删除很快，提供相应的成员函数不用的内存即释放。删除即释放，需要则分配内存分配速度快分块存储，无

capacity概念缺点：支持随机访问元素，但速度远不如vector除首尾元素外，其他位置插入删除速度也很慢*如需频繁在首尾外位置插入删除元素，应用list顺序容器：双端队列回顾125／73deque:头插与删头126／73deque与vector内存分配deque←这两句的区别？127／73自编FIFO

队列类构思：队列数据存储？构思：FIFO队列操作限制？需要哪些成员函数？参数和返回值？怎么自编队列？128／73list特点特有成员函数voidremove(constT&x);删除所有元素值=x

元素voidremove_if(T

pr); 删除符合条件谓词pr的元素voidsort(); 所有元素排序默认升序less<int>()voidsort(Tpr); 按条件谓词pr

排序voidunique(); 相邻的重复元素预排序仅留一个voidsplice(iteratorit,list&L);

合并两个list:插入Lvoidsplice(iteratorit,list&L,iteratoritL);插一个元素voidsplice(iteratorit,list&L,iteratorfirstL,iteratorlastL);voidmerge(list&x); 不如splice灵活voidmerge(list&x,Tpr);voidreverse(); 反转元素的位序顺序容器：链表回顾详细用法，下页举例函数对象129／73例：list基本函数sortsort130／73list:splice()用法例L1和L3并入L2用list迭代器将L4并入L2展开初始化L1~L4131／73特有成员函数

int

count(Key&key);返回：值=key的元素个数

iterator

find(Key&key);返回迭代器：值等于key；不满足返回end()

iterator

lower_bound(Key&key);>=key

iterator

upper_bound(Key&key);>key返回迭代器：>=key或>key,

不满足返回end()

pair<first,second>

equal_range(Key&key);返回两个迭代器：first=lower,second=upper

void

swap(set&s); 交换单集合元素

void

swap(multiset&s); 交换多集合元素无pop和push系列函数，用insert()

和erase()关联容器：set／multiset回顾用法举例：下页最末一个元素后面132／73multiset构造集合的构造方法133／73set与multiset成员函数个数集合的成员函数134／73template<classKey, //排序键(sortkey)类型classType, //映射值value类型classTraits

=less<Key>,//key比较，缺省(升序)，可改变

classAllocator=allocator<pair<constKey,Type>>//用缺省

>

class

map

;

//类模板//----------------------------------------------------------------------------template

<classKey,classType,classTraits=less<Key>,

classAllocator=allocator<pair<constKey,Type>>>

class

multimap;

//类模板关联容器：map／multimap定义回顾模板参数135／73

typedef

typedefpair<Key,Type>

value_type;

将两个数据(key,value)构成一个key-vlaue对成员函数见msdn

multimap&

operator=(multimap&_Right);

Aftererasinganyexistingelementsinamultimap,

perator=eithercopiesormovesthecontentsof_Rightintothemultimap.map／multimup对象赋值：=右端赋值给=左端iteratoremplace(val);插入元素val并返回指向val的迭代器若插入key-vlaue，不需构成<key-vlaue>对类型关联容器：map／multimap136／73multimap构造int改char*???int改string???省略，只能进行简单的string处理137／73multimap构造按key排序138／73multimap构造(2)比较上例上例：int139／73multimap构造(2)比较上例<key–value>140／73multimap构造：插入和赋值不需pail<key,value>比较上例141／73multimap成员函数

返回地址即迭代器升序注意比较注意比较注意比较将容器清空142／73bucket（桶）存储元素：hash(key)值相同冲突的元素存入同一个桶桶的数量：容器里有若干个桶,bucket_count()插入元素：桶数量自动增加必要时,rehash()

指定最小值元素顺序：先插入的元素在前，key相等元素逻辑相邻intbucket_count() 返回：容器中桶的数量intbucket(key) 返回：桶的编号，存放元素keyintbucket_size(n) 返回：编号n的桶中元素数量iterator

emplace(val)

插入val，返回指向val的迭代器Hashhash_function() 返回：hash函数对象void

rehash(n) 重建hash表，桶数>=nfloat

load_factor() 平均装填因子=元素数量/桶数量floatmax_load_factor()最大装填因子装满=1，改变无意义unordered_set／_multiset类特殊成员函数回顾143／73hash_set／hash_multiset

构造方法回顾与multiset比较复习：哈希函数冲突解决144／73unordered_multiset构造方法回顾hash_multiset145／73unordered_multiset类成员函数unordered_multiset成员函数146／73unordered_multiset高级#include<unordered_set>9/649/128147／73unordered_map／_multimap回顾148／73unordered_map／_multimap比较前例149／73multimap查找删除比较前例key无序150／73multimap查找删除修改元素<key,value>清空容器151／73栈基本概念

复习数据结构顺序栈：顺序存储结构链式栈：链式存储结构容器适配器：stack和queue固定数组存储动态数组存储NULL单向链表存储双向链表存储152／73队列基本概念

复习数据结构顺序队列：顺序存储结构链式队列：链式存储结构容器适配器：stack和queue…队尾对头固定数组存储动态数组存储单向链表存储双向链表存储逻辑结构153／73基本容器

(有条件)在已有容器基础上修改，具备新特点stack基本容器具有

size,empty,push_back,pop_back,front,back等函数——

vector

,deque,listqueue基本容器具有

size,empty,push_back,pop_front,front,back等函数——deque,list容器适配器：stack和queue回顾vector没有自编队列例顺序链式链式154／73template

<classType,classContainer=deque<Type>>classstack

{…}//-----------------------------------------------template

<classType,classContainer=deque<Type>>classqueue{…}STL:stack和queue定义155／73例：STLstack156／73例：STLstack创建栈v1,v2,v3

进栈读栈顶元素:top()出栈或弹栈:pop()清空栈iota()生成v1,v2,v3157／73例：STLqueue入队s1,s2,s3,s4读队尾元素(类型)？读队头读队头出队全部出队输出屏幕158／73优先队列：

就是堆，或者用堆实现的优先值排序：

堆排序max-heap

复习数据结构逻辑结构：具有父母优势的一棵完全二叉树父母优势：任意父母结点key≥子女结点key

容器适配器：priority_queue回顾最大堆最小堆不是堆975481完全二叉树159／73满二叉树FullBinaryTree,FBT定义：设树高h，结点总数

n=

2h-1

的二叉树。图示n=20+21+22+…+2h-1

=2h-1特点：不存在单分支度=1结点不缺叶结点只出现在最底层不缺满二叉树h=4层数完全二叉树CompletedBin