C+语言程序设计（第4版）第十章 泛型程序设计与C+标准模板库清华大学 郑 莉C+语言程序设计（第4版），郑莉，清华大学目录10.1 泛型程序设计及STL的结构10.2 迭代器10.3 容器的基本功能与分类10.4 顺序容器10.5 关联容器10.6 函数对象10.7 算法10.8 综合实例对个人银行账户管理程序的改进10.9 深度探索10.10 小结2C+语言程序设计（第4版），郑莉，清华大学10.1.1 泛型程序设计的基本概念 编写不依赖于具体数据类型的程序 将算法从特定的数据结构中抽象出来，成为通用的 C+的模板为泛型程序设计奠定了关键的基础 几个术语 概念（concept）：用来界定具备一定功能的数据类型， 如“支持 s(N);for (int i = 0; i si; transform(s.begin(), s.end(),ostream_iterator(cout, “ “), negate(); cout 以输入流（如cin）为参数构造 可用*(p+)获得下一个输入的元素 输出流迭代器 ostream_iterator 构造时需要提供输出流（如cout） 可用(*p+) = x将x输出到输出流 二者都属于适配器 适配器是用来为已有对象提供新的接口的对象 输入流适配器和输出流适配器为流对象提供了迭代器的 接口610.2 迭代器C+语言程序设计（第4版），郑莉，清华大学例10-2从标准输入读入几个实数，分别 将它们的平方输出 /10_2.cpp #include #include #include using namespace std;/求平方的函数 double square(double x) return x * x; int main() /从标准输入读入若干个实数，分别将它们的平方输出transform(istream_iterator(cin), istream_iterator(), ostream_iterator(cout, “t“), square);cout 运算符） 输入迭代器 可以用来从序列中读取数据，如输入流迭代器 输出迭代器 允许向序列中写入数据，如输出流迭代器 前向迭代器 既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历 双向迭代器 与前向迭代器相似，但是在两个方向上都可以对数据遍历 随机访问迭代器 也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转， 如指针、使用vector的begin()、end()函数得到的迭代器910.2 迭代器 10.2.2 迭代器的分类C+语言程序设计（第4版），郑莉，清华大学10.2.3 迭代器的区间 两个迭代器表示一个区间：p1, p2) STL算法常以迭代器的区间作为输入，传递输入数据 合法的区间 p1经过n次(n 0)自增(+)操作后满足p1 = p2 区间包含p1，但不包含p21010.2 迭代器C+语言程序设计（第4版），郑莉，清华大学例10-3 综合运用几种迭代器的示例/10_3.cpp #include #include #include #include using namespace std;/将来自输入迭代器p的n个T类型的数值排序，将结果通过输出迭代器result输出 template void mySort(InputIterator first, InputIterator last, OutputIterator result) /通过输入迭代器p将输入数据存入向量容器s中 vector s; for (;first != last; +first) s.push_back(*first); sort(s.begin(), s.end();/对s进行排序，sort函数的参数必须是随机访问迭代器 copy(s.begin(), s.end(), result);/将s序列通过输出迭代器输出 1110.2 迭代器 10.2.3 迭代器的区间C+语言程序设计（第4版），郑莉，清华大学例10-3 （续）int main() /将s数组的内容排序后输出 double a5 = 1.2, 2.4, 0.8, 3.3, 3.2 ; mySort(a, a + 5, ostream_iterator(cout, “ “); cout (istream_iterator(cin), istream_iterator(), ostream_iterator(cout, “ “); cout 、= begin()、end()：获得容器首、尾迭代器 clear()：将容器清空 empty()：判断容器是否为空 size()：得到容器元素个数 s1.swap(s2)：将s1和s2两容器内容交换 相关数据类型（S表示容器类型） S:iterator：指向容器元素的迭代器类型 S:const_iterator：常迭代器类型1610.3 容器的基本功能与分类C+语言程序设计（第4版），郑莉，清华大学可逆容器、随机访问容器 可逆容器 S:reverse_iterator：逆向迭代器类型 S:const_reverse_iterator：逆向常迭代器类型 rbegin() ：指向容器尾的逆向迭代器 rend()：指向容器首的逆向迭代器 随机访问容器 sn：获得容器s的第n个元素1710.3 容器的基本功能与分类C+语言程序设计（第4版），郑莉，清华大学10.4.1 顺序容器的基本功能 顺序容器的接口 赋值 assign 插入函数 insert， push_front（只对list和deque）， push_back 删除函数 erase，clear，pop_front（只对list和deque） ，pop_back 其他顺序容器访问函数 front，back 改变大小 resize1810.4 顺序容器C+语言程序设计（第4版），郑莉，清华大学例10-4 顺序容器的基本操作/10_4.cpp，包含的头文件略去 /输出指定的整型顺序容器的元素 template void printContainer(const char* msg, const T cout s; for (int i = 0; i x; s.push_front(x); 1910.4 顺序容器 10.4.1 顺序容器的基本功能C+语言程序设计（第4版），郑莉，清华大学例10-4 （续）printContainer(“deque at first“, s); /用s容器的内容的逆序构造列表容器l list l(s.rbegin(), s.rend(); printContainer(“list at first“, l); /将列表容器l的每相邻两个容器顺序颠倒 list:iterator iter = l.begin(); while (iter != l.end() int v = *iter; iter = l.erase(iter); l.insert(+iter, v); printContainer(“list at last“, l); /用列表容器l的内容给s赋值，将s输出 s.assign(l.begin(), l.end(); printContainer(“deque at last“, s); return 0; 2010.4 顺序容器 10.4.1 顺序容器的基本功能C+语言程序设计（第4版），郑莉，清华大学例10-4 （续） 运行结果如下： 0 9 8 6 4 3 2 1 5 4deque at first: 4 5 1 2 3 4 6 8 9 0list at first: 0 9 8 6 4 3 2 1 5 4list at last: 9 0 6 8 3 4 1 2 4 5deque at last: 9 0 6 8 3 4 1 2 4 52110.4 顺序容器 10.4.1 顺序容器的基本功能C+语言程序设计（第4版），郑莉，清华大学10.4.2 三种顺序容器的特性向量（Vector） 特点 一个可以扩展的动态数组 随机访问、在尾部插入或删除元素快 在中间或头部插入或删除元素慢 向量的容量 容量(capacity)：实际分配空间的大小 s.capacity() ：返回当前容量 s.reserve(n)：若容量小于n，则对s进行扩展，使其 容量至少为n2210.4 顺序容器C+语言程序设计（第4版），郑莉，清华大学双端队列（deque） 特点 在两端插入或删除元素快 在中间插入或删除元素慢 随机访问较快，但比向量容器慢2310.4 顺序容器 10.4.2 三种顺序容器的特性C+语言程序设计（第4版），郑莉，清华大学例10-5 奇偶排序 先按照从大到小顺序输出奇数，再按照从小到大顺序输出偶数。2410.4 顺序容器 10.4.2 三种顺序容器的特性/ 头部分省略 int main() istream_iterator i1(cin), i2;/建立一对儿输入流迭代器vector s1(i1, i2);/通过输入流迭代器从标准输入流中输入数据sort(s1.begin(), s1.end();/将输入的整数排序deque s2;/以下循环遍历s1for (vector:iterator iter = s1.begin(); iter != s1.end(); +iter) if (*iter % 2 = 0)/偶数放到s2尾部s2.push_back(*iter); else/奇数放到s2首部s2.push_front(*iter);/将s2的结果输出copy(s2.begin(), s2.end(), ostream_iterator(cout, “ “);cout s1(names1, names1 + 4); /用names1数组的内容构造列表s1 list s2(names2, names2 + 4); /用names2数组的内容构造列表s2/将s1的第一个元素放到s2的最后 s2.splice(s2.end(), s1, s1.begin(); list:iterator iter1 = s1.begin(); /iter1指向s1首 advance(iter1, 2); /iter1前进2个元素，它将指向s1第3个元素 list:iterator iter2 = s2.begin(); /iter2指向s2首 +iter2; /iter2前进1个元素，它将指向s2第2个元素2610.4 顺序容器 10.4.2 三种顺序容器的特性C+语言程序设计（第4版），郑莉，清华大学例10-6 （续）27list:iterator iter3 = iter2; /用iter2初始化iter3advance(iter3, 2); /iter3前进2个元素，它将指向s2第4个元素/将iter2, iter3)范围内的结点接到s1中iter1指向的结点前s1.splice(iter1, s2, iter2, iter3); /分别将s1和s2输出copy(s1.begin(), s1.end(), ostream_iterator(cout, “ “);cout (cout, “ “);cout s; back_inserter iter(s); *(