简约手绘风商务年中总结PPT模板.ppt 42页

'By————黄泽雨OpenTopic2C++STL中的顺序存储容器MYOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOT1 01.STL？Chapter102.顺序存储容器Chapter203.注意事项Chapter3目录2 01STL?MYOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOT 1.STL?C++的标准模板库，StandardTemplateLibrary。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。除此之外，还包括迭代器、仿函数、内存配置器和配接器。4 1.STL？有了STL，程序员就不必编写大多数常用的数据结构和算法。而且STL是经过精心设计的，运行效率很高，比水平一般的程序员编写的同类代码速度更快。是泛型程序设计最成功应用的实例。5 顺序存储容器02MYOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOT6 2.顺序存储容器一个容器就是一些特定类型对象的集合。顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。string,vector,array,deque,list,forward_list.7 2.顺序存储容器8 2.顺序存储容器头文件first。9 2-1vector常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器10 常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器2-1.vector必须提供元素类型信息在<>内！！可以初始化，也可以不（有条件）<>内也可以是容器类型构造函数11 2-1.vector迭代器iteration目标：指向容器中的某个元素/容器尾元素的下一个位置（有效）；无效的迭代器（类似于指针）功能：主要功能在于提供了一种遍历容器内所有元素的方式（通过指针/下标也可以），以及提供了指定容器内某个元素或某范围的一个方法。迭代器只能指向容器，但迭代器比指针更智能，更安全。常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器 2-1.vector声明：（类型包含在对应头文件中)begin()和end();其实还有cbegin()和cend()；操作：*iter++iter--iteriter1==iter2iter1!=iter2iter+Niter1-iter2迭代器常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器13 2-1.vector一个例子：迭代器范围：由两个有效的迭代器构成（必须指向同一个容器中的元素），如begin和end，从begin指向的元素开始，到end指向的前一个元素结束。构成的范围也叫左闭合区间。[begin,end)迭代器常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器14 2-1.vector还有一种初始化方式：vectorv(i,e)//i和e都是指向同一容器中元素的有效迭代器，且不可指向v本身！！这种初始化方式的好处：可以将不同类型容器中的元素拷贝进来。构造函数常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器 2-1.vector赋值操作：v1={12,34}v2=v1用右侧所有元素替换左侧数组中的全部元素。也可以v3=v1+v2v3为v1与v2相连不能用内置数组直接给vector赋值v1.swap(v2)swap(v1,v2)swap也可用于内置数组（如之前oj1-2第4题）赋值与swap常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器 2-1.vectorc.size()返回c中元素数目c.empty()返回布尔值，若c没有元素则返回0，否则返回1改变大小的成员函数：resize()大小常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器 2-1.vector成员函数们：添加：1.push_back(t)2.emplace_back(construct)3.insert(p,···)···//在p指向位置之前插入元素！添加/删除元素常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器18 2-1.vector成员函数们：删除：1.pop_back()//删除尾元素，返回void2.erase(p)//删除迭代器p指定的元素，返回指向下一个元素的迭代器2’erase(b,e)//删除迭代器b，e范围内的元素（左闭区间，还记得不）3.clear()//删除所有元素添加/删除元素常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器19注意：插入/删除元素，会使该元素后面的所有迭代器、指针、引用都失效。插入元素时前面的也有可能会失效。（若发生重新分配内存地址） 2-1.vector==!=字面意思<,>,<=,>=比较第一个不同的元素，按数字大小/字典中顺序比较（区分大小写）注意：两个容器必须同类且存储的元素同类且对该类元素，关系运算符有定义。关系运算符常用的基本容器操作构造函数赋值与swapc1=c2或c1={a,b,···}a.swap(b)等价于swap(a,b)大小c.size()c.empty()添加/删除元素关系运算符迭代器20 2-1.vector题目：给定一个数组{1，2，3，4，5，6，7，8，9，10}，要求复制所有偶数，输出复制完后的数组。21 这样一道小题。。。约瑟夫问题：有n只猴子，按顺时针方向围成一圈选大王（编号为1~n），从第1号开始报数，一直数到m，数到m的猴子退到圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王。编程求输入n、m后,输出最后猴王的编号。22 什么是链表结构？顺序存储结构：内置数组类型，vector,string,array,deque（地址连续）单向/双向链表结构2-2.forward_list——单向链表结构23 基本的操作方法相同。不同：1.forward_list不支持size操作（一个很实用的成员函数）2.不支持迭代器加减运算，以及--。（但支持++it)3.有专门的一套插入/删除元素的成员函数（之前介绍的仅不适用于forward_list，对string,deque,list都适用）2-2.forward_list24 forward_list的特殊添/减元素操作(lst都代表一个forward_list容器)：1.首前迭代器lst.before_begin()lst.cbefore_begin()//指向首元素前一个位置，即头结点，不能解引用。2.添加元素：lst.insert_after(p,···)//在迭代器p指定的元素后插入元素，具体方法同c.insert(p,···)。返回指向最后一个新插入元素的迭代器。lst.emplace_after(p,construct)//同前3.删除元素：lst.erase_after(p)//删除p指定的下一个元素。lst.erase_after(b,e)//删除b指定的下一个元素到e指定的元素之前的所有元素，左开右开。返回指向被删元素后一个位置的迭代器。2-2.forward_list25 接前面的小题26 *访问元素*1.每个顺序容器均有成员函数front()c.front()返回c的首元素的引用。如对某顺序容器c:autoval1=*c.begin();val2=c.front();(val1==val2)2.除forward_list外顺序容器均有成员函数back()，同理。随机访问（非顺序访问）：3.下标c[n]或c.at(n)均可实现随机访问（list和forward_list不支持）其中c.at(n)的方式更加安全，当下标越界时，抛出out_of_range异常。 2-3.string之前介绍的所有vector支持的操作，对于string同样适用string还有许多独特的接口/实现在此主要介绍三个：getline()find()成员函数字符串与数值间的转换函数字符串类容器28 2-3.string1.getline()作用：将整行的所有字符读到字符串中。在读取字符时，遇到文件结束符、分界符、回车符时，将终止读入操作，且文件结束符、分界符、回车符在字符串中不会保存。使用方法：29 2-3.string例如：stringname(“AnnaBelle”);autopos1=name.find(“Anna”,0);//从第0个位置开始查找并返回指定字符“Anna”第一次出现的下标，若不存在，则返回npos。（对大小写敏感）2.find()成员函数30 2-3.string31 2-3.string要转换为数值的第一个非空白字符必须是字符中可能出现的字符，仅包括：1234567890.+-还有许多类：stoi,stol,stoul,stoll,stoull,stof,stold3.字符串与数值间的转换32 2-4.deque操作与vector几乎一样还有push_front()和pop_front()的添加/删除元素的函数。插入元素，删除除首尾位置外的元素均会使deque所有指针，引用，迭代器失效。双端队列 2-5.list更加复杂同时也很方便的结构。与forward_list不同在于，它支持vector/deque支持的大部分操作，包括push_front,size,还可以方便的在中间任意插入/删除元素。但不支持下标，随机访问。双向链表结构 注意事项03MYOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOT35 3.注意事项1.检查是否有效在每次解引用迭代器/循环之前，都应进行判断，迭代器是否是有效迭代器，以及容器是否有元素。36 3.注意事项2.总结一下失效的情况无论什么，被删除元素的迭代器、指针、引用一定失效。对于list和forward_list，无论添加还是删除，其余的迭代器、指针、引用均不会失效。对于vector或string，添加/删除元素后，插入位置之后的一定失效，若存储空间被重新分配，则全失效（删除时前面的仍有效）。对于deque，在非首尾处添/删元素，全失效。在首位添加，仅迭代器失效，删除尾元素，仅尾后迭代器失效37 3.注意事项3.insert和insert_after函数返回值insert()返回指向插入元素中的第一个的迭代器；insert_after()则返回指向插入元素中的最后一个的迭代器。（这是forward_list专用的）38 3.注意事项4.有两种getline一种前面已经介绍，定义在string头文件中的全局函数（并非成员函数）声明是getline(cin,s,d)其中s是string，d是输入结束的字符，可无，默认为换行符。还有一种是istream的成员函数，声明（现阶段）是:cin.getline(char*s,s,d)与第一种不同的在于第一个参数是一个指向char数组的指针（前一位同学讲过了），不能作用于string，后两个参数同前。39 3.注意事项5.如何选择顺序容器？1.除非有很好的理由选择其他容器，否则应使用vector。2.如果程序中有许多小元素，且空间额外开销很重要，则不要用list和forward_list。3.程序要求随机访问元素？在中间插入/删除元素？在头尾插入删除元素？4.有一种方法，若必须在中间位置插入元素，可以在输入阶段使用list，一旦输入完成，将list中内容拷贝到一个vector中。40 感谢：马老师的悉心指导41 黄泽雨感谢聆听MYOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOTOT42'