1、 程序设计实习 课程(C+ Programming Practice)程序设计实习第二十讲 标准模板库 STL I主讲教师：田永鸿http:/ 5月 19日北京大学 程序设计实习 课程课堂问题o 下列代码是否存在错误，若存在，该如何改正？template class CTempfriend void myClass:func();private:T elementssize;public:CTemp(T arg);template void myClass :func()CTemp a(10);int i;for(i=0; i obj;obj.func();北京大学 程序设计实习 课程课堂问题
2、o 有如下类模板定义template class CTempfriend myClassA;friend myClassB;private:T1 elementssize;public:CTemp(T arg);则 myClassA、 myClassB、 myClassA、myClassA都是 CTemp的友员类北京大学 程序设计实习 课程课堂问题n 找出下列代码中的错误之处，并解释 a(10)（或 b(8.9)、 的含义）template class CTempfriend void func(int);private:T elementssize;public:CTemp(T arg);v
3、oid func(int size)CTemp a(10);CTemp b(8.9);CTemp c(10);CTemp d(10);int i;for(i=0; i50; i+) couta.elementsi“ ” b.elementsiendl;return;北京大学 程序设计实习 课程提纲o 1. 引言o 2. STL中的基本概念o 3. 容器概述o 4. 迭代器o 5. 算法简介o 6. 顺序容器北京大学 程序设计实习 课程概论o C+ 语言的核心优势之一就是便于软件的重用o C+中有两个方面体现重用：n 1. 面向对象的思想：继承和多态，标准类库n 2. 泛型程序设计 (gener
4、ic programming) 的思想：模板机制，以及标准模板库 STL北京大学 程序设计实习 课程泛型程序设计o 泛型程序设计，简单地说就是 使用模板的程序设计 法。n 将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。o 标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。主要由 Alex Stepanov 开发，于 1998年被添加进 C+标准o 有了 STL，不必再从头写大多的标准数据结构和算法，并且可获
5、得非常高的性能。北京大学 程序设计实习 课程STL中的几个基本概念o 容器：可容纳各种数据类型的数据结构。o 迭代器：可 依次存取 容器中元素的东西o 算法：用来操作容器中的元素的 函数模板 。例如， STL用 sort()来对一个 vector中的数据进行排序，用 find()来搜索一个 list中的对象。n 函数本身与他们操作的数据的结构和类型无关 ，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。o 比如，数组 int array100就是个容器，而 int * 类型的指针变量就可以作为迭代器，可以为这个容器编写一个排序的算法北京大学 程序设计实习 课程容器概述o 可以用于存
6、放各种类型的数据（基本类型的变量，对象等）的数据结构。o 容器分为三大类：1) 顺序容器 vector：后部插入 /删除，直接访问deque：前 /后部插入 /删除，直接访问list：双向链表，任意位置插入 /删除2)关联容器set：快速查找，无重复元素multiset ：快速查找，可有重复元素map：一对一映射，无重复元素，基于关键字查找multimap ：一对一映射，可有重复元素，基于关键字查找前 2者合称为第一类容器 3)容器适配器stack： LIFOqueue： FIFOpriority_queue：优先级高的元素先出 北京大学 程序设计实习 课程容器概述o 对象被插入容器中时，被插入的是 对象的一个复制品 。o 许多算法，比如排序，查找，要求对容器中的元素进行比较，所以，放入容器的对象所属的类，还应该实现 = 和 运算符。
