C++语言程序设计 第十章℃++标准模板库 清华大学郑莉
第十章 C++标准模板库 清华大学 郑 莉 C++语言程序设计
C++语言程序设计 清华大学郑莉 主要内容 ·泛型程序设计 。迭代器 ●顺序容器 ●关联容器 。函数对象 ●算法 深度探索 ★
C++语言程序设计 清华大学 郑莉 2 主要内容 ⚫ 泛型程序设计 ⚫ 迭代器 ⚫ 顺序容器 ⚫ 关联容器 ⚫ 函数对象 ⚫ 算法 ⚫ 深度探索
C++语言程序设计 清华大学郑莉 泛型程序设计 泛 编写不依赖于具体数据类型的程序 型 ● 将算法从特定的数据结构中抽象出来，成 为通用的 程 ● C+的模板为泛型程序设计奠定了关键的 序 基础 设 ·几个术语 计 概念(concept) 用来界定具备一定功能的数 据类型，如“支持<’运算符” 的数据类型构 成Comparable:这一概念； 模型(model): 符合一个概念的数据类型称 为该概念的模型， 如int型是Comparable概的 模型
C++语言程序设计 清华大学 郑莉 3 泛型程序设计 ⚫ 编写不依赖于具体数据类型的程序 ⚫ 将算法从特定的数据结构中抽象出来，成 为通用的 ⚫ C++的模板为泛型程序设计奠定了关键的 基础 ⚫ 几个术语 – 概念（concept）：用来界定具备一定功能的数 据类型，如“支持‘<’运算符”的数据类型构 成Comparable这一概念； – 模型（model）：符合一个概念的数据类型称 为该概念的模型，如int型是Comparable概念的 模型。 泛 型 程 序 设 计
C++语言程序设计 清华大学郑莉 STL程序实例（例10-1） 泛 //包含的头文件略去… using namespace std; 型 int main(){ 程 const int N 5; 容器 序 vectors(N); for (int i=0;i N;i++) 迭代器 设 函数对象 cin >s[i]; 计 transform(s.begin(),s.end(), ostream_iterator(cout, negate()) 算法 cout <endl; return 0;
C++语言程序设计 清华大学 郑莉 STL程序实例(例10-1) 4 //包含的头文件略去…… using namespace std; int main() { const int N = 5; vector s(N); for (int i = 0; i > s[i]; transform(s.begin(), s.end(), ostream_iterator(cout, " "), negate()); cout << endl; return 0; } 容器 函数对象 算法 迭代器 泛 型 程 序 设 计
C++语言程序设计 清华大学郑莉 STL的组成部分 泛 ·STL是泛型程序设计的一个范例 型 容器(container) 迭代器(iterator) 程 算法(algorithms) 序 函数对象(function object) 设 迭代器 算法 迭代器 容器 (iterator (algorithm) (iterator 容器 计 (container) (container) 函数对象 (function object)
C++语言程序设计 清华大学 郑莉 STL的组成部分 ⚫ STL是泛型程序设计的一个范例 – 容器（container） – 迭代器（iterator） – 算法（algorithms） – 函数对象（function object） 5 泛 型 程 序 设 计 容器 (container) 算法 (algorithm) 容器 (container) 迭代器 (iterator) 函数对象 (function object) 迭代器 (iterator)
C++语言程序设计 清华大学郑莉 输入流迭代器和输出流迭代器 。输入流迭代器 istream_iterator 迭 以输入流（如cin)为参数构造 可用*(p+)获得下一个输入的元素 代 ·输出流迭代器 器 ostream_iterator 构造时需要提供输出流（如cout) 可用(p+)=x将x输出到输出流 。二者都属于适配器 适配器是用来为己有对象提供新的接口的对象 氯命鎏酒配器利和输出流适配器为流对象提供了铁
C++语言程序设计 清华大学 郑莉 输入流迭代器和输出流迭代器 ⚫ 输入流迭代器 – istream_iterator – 以输入流（如cin）为参数构造 – 可用*(p++)获得下一个输入的元素 ⚫ 输出流迭代器 – ostream_iterator – 构造时需要提供输出流（如cout） – 可用(*p++) = x将x输出到输出流 ⚫ 二者都属于适配器 – 适配器是用来为已有对象提供新的接口的对象 – 输入流适配器和输出流适配器为流对象提供了迭代 器的接口 6 迭 代 器
C++语言程序设计 清华大学郑莉 例10-2 /包含的头文件略去… using namespace std; 迭 double square(double x){ 代 return xx; 器int main0{ transform(istream_iterator(cin), istream_iterator(), ostream iterator(cout,"\t"),square); cout <endl; return 0;
C++语言程序设计 清华大学 郑莉 例10-2 7 //包含的头文件略去…… using namespace std; double square(double x) { return x * x; } int main() { transform(istream_iterator(cin), istream_iterator(), ostream_iterator(cout, "\t"), square); cout << endl; return 0; } 迭 代 器
C++语言程序设计 清华大学郑莉 迭代器的概念图 输入迭代器 输出迭代器 (Input Iterator) (Output Iterator) 代 前向迭代器(Forward Iterator) 双向迭代器(Bidirectional Iterator) 随机访问迭代器(Random Access Iterator)
C++语言程序设计 清华大学 郑莉 迭代器的概念图 8 输入迭代器 (Input Iterator) 输出迭代器 (Output Iterator) 前向迭代器(Forward Iterator) 双向迭代器(Bidirectional Iterator) 随机访问迭代器(Random Access Iterator) 迭 代 器
C++语言程序设计 清华大学郑莉 迭代器支持的操作 迭代器是泛化的指针，提供了类似指针的操作（诸如 ++、 、>运算符) ● 输入迭代器 迭 可以用来从序列中读取数据，如输入流迭代器 代 ● 输出迭代器 允许向序列中写入数据，如输出流迭代器 器 ●前向迭代器 爵器鸛入达代器又是输出达代器，并且可以对序列进行单向 ·双向迭代器 与前向迭代器相似，但是在两个方向上都可以对数据遍历 随机访问迭代器 忠餐双向造公器， 但能够在序列中的任意两个位置之可悫 ,如指针、使用vector的begin(O、end(O函数得到的 代器
C++语言程序设计 清华大学 郑莉 9 迭代器支持的操作 ⚫ 迭代器是泛化的指针，提供了类似指针的操作（诸如 ++、 * 、->运算符） ⚫ 输入迭代器 – 可以用来从序列中读取数据，如输入流迭代器 ⚫ 输出迭代器 – 允许向序列中写入数据，如输出流迭代器 ⚫ 前向迭代器 – 既是输入迭代器又是输出迭代器，并且可以对序列进行单向 的遍历 ⚫ 双向迭代器 – 与前向迭代器相似，但是在两个方向上都可以对数据遍历 ⚫ 随机访问迭代器 – 也是双向迭代器，但能够在序列中的任意两个位置之间进行 跳转，如指针、使用vector的begin()、end()函数得到的迭 代器 迭 代 器
C++语言程序设计 清华大学郑莉 迭代器的区间 ●两个迭代器表示一个区间：[p1,p2) 迭 ●STL算法常以迭代器的区间作为输入 代 ，传递输入数据 器 ·合法的区间 -p1经过n次(n>0)自增(++)操作后满足p1 ==p2 ● 区间包含p1,但不包含p2
C++语言程序设计 清华大学 郑莉 迭代器的区间 ⚫ 两个迭代器表示一个区间：[p1, p2) ⚫ STL算法常以迭代器的区间作为输入 ，传递输入数据 ⚫ 合法的区间 – p1经过n次(n > 0)自增(++)操作后满足p1 == p2 ⚫ 区间包含p1，但不包含p2 10 迭 代 器