09STL

模板和STL闵卫[e-mail]01一．为什么需要模板-E预处理g++-Edemo.cpp-S编译g++-Sdemo.cpp1）为同一种数据结构或者算法，定义适用于不同类型的版本——代码冗余。2）借助参数宏摆脱类型的约束，同时也丧失了类型安全——潜在风险。3）让预处理器自动生成针对不同类型的版本——不易于调试。4）可以编写带有参数化类型的通用版本，让编译器自动生成针对不同参数类型的具体版本——模板二．函数模板1）函数的返回值、参数表和局部变量均可使用类型参数。templatetypename类型形参名1，typename类型形参名2，…返回类型函数模板名（形参表）{函数体}使用：函数模板名类型实参1，类型实参2，…(实参表)；2）函数模板的类型参数支持隐式推断。隐式推断不允许隐式转换，但是可以显式的进行类型转换。函数返回类型不支持隐式推断3）函数模板可以重载形参不同的同名模板之间，以及函数模板和同名具体函数之间都可以构成重载关系。PS：当模板函数与具体函数都可匹配时，优先匹配具体函数。三．类模板1.类模板：类的成员函数、成员变量和基类都含有可以参数化的类型。类模板不能隐式推断，只能给出显式类型。Templatetypename类型形参名，typename类型形参名2，…Class模板类名：继承表{成员定义；}使用：类模板名类型实参1，类型实参2，…对象名（构造参数表）【类模板】------实例化-----【类】-------实例化------【对象】编译期运行期2.类模板的静态成员变量，每个实例类各有一份。3.类模板的模板参数可以带有缺省值（从右边缺省开始）。PS：函数模板的参数不能带有缺省值。四．模板的特化1.对于某些特定类型而言，通用模板可能并不适用，可以为通用模板提供一种特殊化的定义，作为一般情况之外的特例，为编译器提供一种更为合适的选择。2.对于类模板，既可以将整个类模板全部特化，也可以只针对具体类型相关的个别成员函数进行特化。（注意：使用成员特化时，特化版本和通用版本的规格必须完全一致。）PS：当使用模板类型做多文件编程时，需要main.cpp文件包含classTemplate.h文件classTemplate.h文件包含classTemplate.cpp文件五．编译模型1.后期编译(1)模板定义只是一种规范描述，而非真正的类型定义。当编译器看到模板定义时，仅做一般性的语法检查，同时保存一份模板的内部表示，并不生成二进制指令。(2)当编译器看到模板被实例化为具体函数或类，才真正用模板的内部表示结合类型实参，生成指令代码。(3)每个C++语言的源文件是单独编译的。因此编译器仅在编译包含模板定义的源文件时保存内部表示。(4)如果模板的实例化与他的定义不再同一个编译单元中，模板就失去被编译的机会，进而导致链接错误。2.包含模型1）将模板的声明和定义放在一个头文件中，或者在其头文件中通过#include预编译指令包含定义该模板的源文件。2）包含模型的缺陷A）暴露了用户不希望或者不了解的实现细节；B）模板头文件被多个源文件包含，会延长编译时间。3．分离模型在定义模板的源文件中，加入一个export声明：Comparatro.cpp当编译器看到某个模板被声明为导出（export）型，会将该模板的内部表示缓存到一个临时文件中。编译器编译到对该模板的实例化代码时，在从这个临时文件中重新读取其内部表示，完成编译和链接。注意：绝大多数C++编译器都不支持分离模型，而且在新C++11标准中已经删除了分离模型，并将export关键字移做它用。六．类模板的局部特化1.针对部分类型参数取特定类型进行特化；编译器优先选择特化程度最高的版本。3.针对类型参数之间的某种关联性进行特化；编译器优先选择匹配程度最高的版本。4.针对指针或者数组进行特化；编译器优先选择针对指针或数组的特化版本。范例：partial.cpp注意：当编译器发现同时存在多个匹配程度一样的版本时，会报告歧义错误。七.非类型参数1.模板既可以带有类型参数，也可以带有非类型参数，传递给非类型参数的实参只能是常量/常量表达式/常属性（const）的变量，且不能同时具备挥发性（volatile）。2.类模板的非类型参数和类型参数一样，也可以带有缺省值。PS：模板的非类型参数不能是浮点数，也不能是类类型。模板的非类型实参不能是字符串字面值。模板的非类型实参不能是全局指针，模板的非类型实参可以是外部变量。八．模板的嵌套和递归ListArrayintlaArrayListintalArrayArrayintaa九．模板型模板实参十．类模板中的模板函数十一.class和typenameClass——-类\模板/参数typename——解决嵌套依赖Day02模板应用（容器、迭代器、泛型算法）STL容器：借助于模板语法实现抽象化的数据结构。迭代器：提供一种与具体的数据结构无关的、统一的、针对容器元素的访问方法。泛型算法：借助模板语法实现抽象化的数据处理。一.容器以双向线性链表模板为例。二．迭代器：在不暴露容器内部表示的前提下，使用户以一种一致且透明的方式访问容器中的对象。1.迭代：从一个到下一个。2.类类型的对象，来模拟一个数组指针遍历的行为。3.封装实际指针，提供指针所支持的运算符：==，!=，++，--，*，-，三．泛型算法：借助于迭代器，以泛型的方式处理容器中的对象。BoostDay03一.STL1.STL的特性1）STL里的所有组件，都是通过模板定义的，全面支持泛型2）STL所追求的目标是最大程度上降低数据结构和算法与具体数据类型的相关性。3）STL的设计宗旨就是通过一个尽量小的框架，实现尽量大的弹性。2.STL的主要容器类型下面三种线性容器：强调元素之间的前后关系1）向量（vector）：内存连续，可以进行下标访问。（可代替数组）2）列/链表（list）：内存不连续，不能以下标访问，随机的插入/删除高效。3）双端队列（deque）：类似于相量，但两端都是开放的。下面三种容器：合称为适配器容器，构建于三种线性容器之上的封装。4）堆栈（stack）：在一端的压入和弹出，后进先出。5）对列（queue）：从一段压入，从另一端弹出，先进先出。6）优先队列（priority_queue）：从一段压入，从另一端弹出，优者先出。下面四种容器：合称为关联容器。7）映射（map）：通过平衡有序二叉树，存放key-value对的集合，提高搜索性能。key必须唯一，一一对应关系。8）多重映射（multimap）：允许key重复的映射。一对多的关系。9）集合（set）：没有value的映射。10）多重集合（multiset）：没有value的多重映射。PS：平衡二叉树：对任何一个节点，它的左子树的深度与右子树的深度最大相差1。3.STL容器的共性1）所有的容器都支持深拷贝2）所有的容器都可以和同型容器做关系比较（==!=…..）3）容器中的元素都是副本4）所有的容器都支持迭代器（支持泛型算法）二．向量（vector）1.基本特性1）存储结构：使用一段连续的内存空间来存放数据。2）具备常数时间的随机访问特性（下标访问）。3）支持下标运算符。4）支持动态内存管理：（向量将他所有的元素存放在一个连续的内存块中，这并不会妨碍新元素被无限地插入到容器中。如果当前内存无法满足一个向量中所有元素连续存放的需要，那么这个向量就会自动转移到一个新的内存位置，原先位置上的所有元素都将被复制到新分配的内存中，而原先的内存空间被释放）。5）通过预分配空间来降低动态内存管理的开销。6）也支持随机位置的插入/删除，但是只有在尾部做插入/删除才是高效的。2.实例化#includevector1）vector元素类型向量对象；如：vectorintvi;2）vector元素类型向量对象（初始大小）；如：vectorintvi(10);初始预分配空间范围内的元素，基本类型：初始化为0；类类型：调用缺省构造函数初始化。3）vector元素类型向量对象（初始大小，初值）；如：vectorintvi(10,1234);用初值值初始化预分配空间内的每个元素。4）vector元素类型向量对象（起始迭代器，终止迭代器）；用另一个容器从起始迭代器，到终止迭代器之前为止的范围内的元素，来初始化所构造的向量。如：intarr[5]={1,2,3,4,5}Vectorintvi(arr,arr+5);Vectorintvi(&arr[0],&arr[5]);3.函数front/back/push_back/pop_back，注意不能再首端push/pop操作4.迭代器1）四个迭代器iterator/const_iteratorreverse_iterator/const_reverse_iterator2）随机迭代器A只有连续内存的容器（vector/deque）才有随机迭代器。B支持和整数的加减运算，支持迭代器的比较和相减运算。3）迭代器的分类按照迭代方向分：正向/反向迭代器按照访问特性分：可写/只读迭代器按照迭代特性分：顺序/随机迭代器vector::iterator正向、可写、随机list::const_reverse_iterator反向、只读、顺序5.insert/erase函数6.大小和容量大小：实际容纳元素的个数容量：最多容纳元素的个数（vector的容量只增不减）size()——返回大小resize()——改变大小，可增可减，增则构造，减则析构。max_size()——返回向量的最大容量（也可insert/push_back元素）Clear()——等价于resize(0)清空empty()——判断是否为空capacity()——返回容量reserve（）——预留容量，只增不减，新增部分不初始化向量的容量无论是通过resize()，还是通过调用reserve()，都是只增不减的。因此向量不适宜保存大对象，如果对象需要使用较多的资源，建议通过构造和析构函数来动态分配和释放该资源。vectorStudent*vs;vs.push_back(newStudent());7.查找和排序#includealgorithmfind():原型iteratorfind(iteratorbegin,iteratorend,constvalue_type&val)在begin和end之间查找与val相匹配的第一个元素，返回该元素的迭代器，如果查找失败，返回第二个参数end。sort()：原型voidsort(iteratorbegin,iteratorend);voidsort(iteratorbegin,iteratorend,lesscmp);比较器：就是一个返回bool类型值，用于判断第一个元素参数是否小于第二个元素参数的函数或函数对象。bool比较器函数（元素类型const&a,元素类型const&b）{if(ab)returntrue;elsereturnfalse;}Class比较器类{public:booloperator()(元素类型const&a,元素类型const&b)const{if(ab)returntrue;elsereturnfalse;}}Sort()函数的三参数版本的第三个参数，是比较器函数指针，或比较器对象。PS：类对象的查找，需要重写==操作符，类对象的排序，需要重写操作符8.类类型的向量元素类型往往需要考虑以下问题：1）是否支持深拷贝（拷贝构造、拷贝赋值）2）是否支持相等性==比较，find()函数重载“==”或类型转换3）是否支持运算符，sort()函数重载“”或比较器PS：size_typestring：：find_first_of(stringconst&str,size_typepos=0);返回调用字符串中，从pos处开始的，第一个出现在str字符串中的字符的下标。如果没有