• • •
cout<<endl<<"Stack is empty."<<endl; return 0;
}
学习小结
• 学习了函数模板和类模板的实现，相信大家对容 器有了初步的认识，在以后的学习中我们会逐步 对标准模板库中的容器进行剖析，虽然到那时候 容器的底层已经由库函数给大家封装好了，但是 经过这一讲的学习，希望大家对容器的原理明确 的认识并能自己实现简单的容器。
STL概述
• • • 1)容器(containers): 各种数据结构, 如:vector,list,deque,set,map,用来存放数据. 2)算法(algorithms): 各种常用算法如:sort,search,copy,erase... 3)迭代器(iterator): 扮演容器与算法直接的胶合剂,可以理解为指针的概念，共有5种类型, 以及其他衍生变化: 4)仿函数(functors): 行为类似函数,可作为算法的某种策略,仿函数是一种重载了operator()的 class或class template,一般函数指针可看作为狭义的仿函数. 5)配接器(adapters): 一种用来修饰容器(containers)或仿函数或迭代器接口的东西. 6)配置器(allocators): 负责空间配置与管理. 是一个实现了动态空间配置\空间管理\空间释放 的class template.
STL概述
• STL的一个重要特点是数据结构和算法的分离。尽 管这是个简单的概念，但这种分离确实使得STL变 得非常通用。 • STL另一个重要特性是它不是面向对象的。为了具 有足够通用性，STL主要依赖于模板而不是封装， 继承和虚函数（多态性）——OOP的三个要素。你 在STL中找不到任何明显的类继承关系。这好像是 一种倒退，但这正好是使得STL的组件具有广泛通 用性的底层特征。另外，由于STL是基于模板，内 联函数的使用使得生成的代码短小高效。
练习
• 写一个函数模板，返回两数比较大小的结果 • 请编写一个函数模板，可比较同类型人群的年龄大小，并 返回比较结果，需要适用以下人群 学生：姓名，学号，年龄 教师：姓名，工号，年龄 家长：姓名，年龄 • 写一个函数模板sum(a,b)，a、b为任意的数据类型(如 int,double,float等)，保证两数相加返回的是b的数据类型。
•
• •
函数模板
• 在c++没有模板（template）机制的时候，我们使用的 就是普通的函数，我们要实现一个加法函数，他能够 对两个参数求和，并根据参数的类型返回具有适当类 型的值，就必须手工书写所有的代码： short sum(short a,short b) {return a+b;} int sum(int a,int b){return a+b;}
•
函数模板
• template<class T> 通常将它称为模板前缀，该代码通知编译器接下来的函数 定义或者函数声明是一个模板，T是一个类型参数。此处， class实际的意思是类型（type）。参数类型T可以被任意类 型所替代，无论是类还是其他。实际上，函数模板的定义 就是函数定义的一个大集合。 • 事实上编译器不会为模板中所有类型都创建一个函数的定 义体，但编译器在对过程代码进行编译时确实是好像已经 为函数重载了所有可能类型的函数定义版本。对于在程序 中使用模板的每个不同类型，编译器都会生成一个单独的 函数定义，但是对于程序中没有使用的模板类型，则不产 生实际的函数体定义。
float sum(float a,float b){ return a+b;}
„„
函数模板
• 非常麻烦，可以用c++的模板函数来表达“通用型的函数” template<class T> //可不可以再加个class V？ (class和typename没有区别 ) T sum(T a,T b) { return a+b; } 现在，c++编译器可以根据我们调用sum函数的参数类型“现场”生成一个适当 的函数，然后调用它。例如： #include <iostream> using namespace std; int main(void) { float fa=1,fb=3,fs; fs=sum(fa,fb); cout<<”sum(float,float) 1and 3=”<<fs<<endl; }
类模板
template<class T> class 类名 ｛ //类声明体 ｝；
template<class T> 返回类型 类名<T>::成员函数1（形式参数表） ｛ //成员函数定义体 ｝ ……
类模板举例
• • • • • • • • • • • • • • •
template <class T> class Stack { public: Stack(int = 10); virtual ~Stack(); int push(const T &); int pop(T &); int isEmpty() const; int isFull() const; private: int size; int top; T *stackPtr; };
STL标准模板库
函数模板和类模板
学习目标
• STL概述 • 讲解STL标准模板库之前，我们从基础的函 数模板和类模板讲起。 • 本讲的目标，希望大家掌握函数模板和类模 板的实现和编译。
STL概述
• • • • • • •
历史上最令人兴奋的工具的最无聊的术语。 STL = Standard Template Library，标准模板库 在C++标准中，STL被组织为下面的13个头文 件： 为了避免和其他头文件冲突， STL的头文件不再使用常规的.h扩展。 <algorithm>、 <numeric> 、 <functional> <vector>、<list>、<map>、<queue>、 <deque>、 <set>、<stack> <iterator> <memory>、 <utility>和其他
类模板举例
• • • • • • • • • • • • • • • • • • • • template <class T> Stack<T>::Stack(int s) { size = s > 0 && s<1000 ? s : 10; top = -1; stackPtr = new T[size]; } template <class T> Stack<T>::~Stack() { if (stackPtr != NULL) { delete [] stackPtr; } } template <class T> int Stack<T>::isEmpty() const { return top == -1; }
示例：
编译器的复杂性
• 许多编译器不支持对模板的单独编译，因此必须在代码中 使用模板的地方包含模板定义。通常情况下，至少要保证 模板函数的声明早于函数模板的使用。 • 能保证绝大多数编译器上模板程序编译成功的布局如下： 将模板的定义与使用模板的程序放在一个文件中，并保证 模板的定义出现在所有使用模板的代码前面。如果你想将 模板的定义放在一个与你的应用程序不同的一个单独文件 中，可以使用#include命令在使用模 • • • • • • • • • • • • • • • • • template <class T> int Stack<T>::isFull() const { return top == size - 1; } template <class T> int Stack<T>::push(const T &item) { if (!isFull()) {stackPtr[++top] = item; return 1;} return 0; } template <class T> int Stack<T>::pop(T &popValue) { if (!isEmpty()) {popValue = stackPtr[top--]; return 1;} return 0; }
类模板举例
• • • • • • • • • • • • int main(int argc, char* argv[]) { Stack<double> doubleStack(5); double f = 1.1; while (doubleStack.push(f)) { cout<<f<<" "; f += 1.1; } cout<<endl<<"Stack is full."<<endl<<f<<endl; while (doubleStack.pop(f)) cout<<f<<" ";
练习
• • • • • • • • • • • • • • • • • • • • 自己创建一个模板类lklist类 template <class T> class lklist { public: lklist(); lklist(const lklist &lk1); bool FindContent(T elem); bool FindPos(int pos, T &elem); void Insert(int pos, T e); void Delete(int pos); void Show(); ~lklist(); private: struct Node { T data; Node * next; }; Node * head;