8 类模板和容器vector.pptVIP

算法与数据结构 类模板 -- 容器 向量vector容器 回顾一下：什么是函数模板？ 是对不同数据类型通用的函数，函数模板处理的数据类型是用参数T表示的 它是在函数定义前面加上一句 template typename T 函数模板定义的函数像普通的函数一样调用，只需给出具体类型的实参即可，编译器在编译时会用具体的实参生成普通函数的代码 问题的提出 大家知道，可以有各种数据类型的数组，系统内置的数组使用起来有很多不足 如：数组不能直接赋值 数组下标越界不给出错误提示 数组大小固定 我们可不可以定义一个数组类, 让它具有内置数组的功能，再弥补上述缺陷 class array{ private： 数据 } 可以，必须要考虑它的数据类型，岂不是要针对不同的数据类型定义不同的数组类，no 类模板 template typename T class array{ 含有数据类型T的数据成员和成员函数 array(int s=10); void function(); … T *data; int size; }； 在类定义外部的每个成员函数都是函数模板 template typename T arrayT::class_name() { … } template typename T void arrayT::function() { } … arrayT:: 每个函数用类模板作用域 注意：类模板的定义和各个成员函数的模板定义要放在同一个array.h文件中，不要再有一个array.cpp文件 如果是分离建立的array.h 和 array.cpp， 在使用的时候用#includearray.cpp即可 模板在要实例化之后生成代码再编译 使用类模板创建对象 要用实际数据类型的参数去特化类模板 #include“array.h” int main() { arrayint a(100); //100个元素的整型数组 arrayfloat b; //默认10个元素的实型数组 … } 例 存储store类模板（存储的数据用参数T表示) #ifndef STORE_CLASS #define STORE_CLASS #include iostream using namespace std; template typename T class store { public: store(const T item = T() ); //默认实参：T的默认构造函数 T getValue() const; // return value void setValue(const T item); // update value friend ostream operator (ostream ostr, const storeT obj) { ostr Value = obj.value; return ostr; } private: T value; }; 一般的线性表、队列、堆栈、树、图等数据结构都是与数据类型无关的，既可以有任意类型数据形成这些数据结构 因此它们都可以定义成类模板 C++标准模板库STL (standard template library)中已经定义实现了部分数据结构的类模板 在这个库中称为容器container STL容器概述 STL包含10个容器，分为三种 顺序容器（线性的）向量vector、双端队列deque、表list 适配器容器（通过已有的容器进行适当裁剪而成）：栈stack、队列queue、优先队列（priority queue） 关联容器（数据的位置与数据值有关）： 集合set，多重集合multiset，映射map，多重映射multimap 向量容器vector 数组的元素是同类型的，彼此连续存储，下标随机访问，数组的大小是固定的 数组作为函数的参数通常还要有一个数组大小size参数 例如 int sum( int a[ ], int size); 向量vector 容器是一个基于模板的类, 它有一个模板参数T 用vectorT定义的对象v它有数组的特征 即允许向量对象v使用下标访问它的元素 即v[0], …, v[v.size()-1] 但是它的大小不固定，可以任意改变，