《程序设计实习标准模板》由会员分享，可在线阅读，更多相关《程序设计实习标准模板（50页珍藏版）》请在金锄头文库上搜索。
1、程序设计实习课程(C+ Programming Practice)程序设计实习第二十一讲 标准模板库 STL-II主讲教师：田永鸿 http:/ http:/ 2008年5月26日*北京大学程序设计实习课程内容回顾o容器类模板和迭代器n顺序：vector(随机) deque (随机) list(双向)n关联：set (双向) multiset (双向) map (双向) multimap (双向)n容器适配器：stack(不支持) queue (不支持) priority_queue (不 支持)n每一类迭代器所能执行的操作不一样。o函数模板nfindp = find(v.begin(),v.
2、end(),9); /vectorint * pp = find( array,array+4,20);/数组ncopyostream_iterator output(cout ,“*“);copy (v.begin(),v.end(),output);o重点介绍了vector类模板(其实就是动态数组, 尾部添加 数据, 用户无需维护内存) 空构造函数 数组构造 push_back() erase() vector:iterator p北京大学程序设计实习课程课堂问题(1)o给定如下list容器，下述哪些语句是错误的？为什么？ list v; list:const_iterator ii; (
3、a)for( ii = v.begin(); ii != v.end ();ii + ) cout v; v.push_back(1); v.push_back(2); vector:reverse_iterator r; for( r = v.rbegin();r != v.rend();r-) cout ivec(10); vector svec(10); list ilist(10); (a) vector:iterator it=ivec.begin(); (b) list:iterator it=ilist.begin()+2; (c) vector:iterator it= (d)
4、 for (vector:iterator it=svec.begin(); it != 0; +it) /o对于下列程序任务，采用哪种顺序容器是实现最合适？解释选择 的理由？ (a)从一个文件中读入未知数目的单词，以生成英文句子； (b)读入固定数目的单词，在输入时将它们按字母序插入到容器中 。 (c)读入未知数目的单词，总在容器尾部插入新单词，在容器首部 删除下一个值； (d)从一个文件中读入未知数目的整数，对这些整数排序，然后把 它们输出到标准输出设备。1.由于单词数目未知，且需要以非确定的顺序处理 这些单词，因此vector最合适，因为它支持随机 访问； 2.采用list实现最合适，因
5、为需要在容器的任意位 置插入元素。（实际上本节将讲述的关联容器更 好） 3.采用deque实现最合适 4.若一边输入一边排序，则list最合适，因为读入 时需要在容器的任意位置插入元素来实现排序； 若先读入所有整数再排序，采用vector最合适， 因为进行排序最好有随机访问能力。北京大学程序设计实习课程课堂问题(3)o若iv是一个int型的vector容器，下面的程序错在哪里？ 如何改正？vector:iterator mid=iv.begin()+iv.size()/2;while (vector:iterator iter != mid)if (iter = some_val) o添加一条
6、语句后，下面的程序是否还有错？如何改正 ？vector:iterator iter =iv.begin();vector:iterator mid=iv.begin()+iv.size()/2;while (vector:iterator iter != mid)if (*iter = some_val)iv.insert(iter, 2* some_val);1. vector:iterator iter =iv.begin();while (iter != iv.begin()+iv.size()/2)if (*iter = some_val) iter = iv.insert(iter,
7、 2* some_val);2. iter += 2; /使iter指向下一个要处理的原始元素3. 4. else5. iter+; /使iter指向下一个要处理的原始元素6. 北京大学程序设计实习课程内容提要o新概念n函数对象npair 模板oSTL中的其它容器类模板nmultiset/set nmultimap/map nstack/queue/priority_queueo复习copy函数模板北京大学程序设计实习课程函数对象o是个对象，但是用起来看上去象函数调用，实际上也 执行了函数调用 class CMyAverage public: double operator()( int a1
8、, int a2, int a3 ) /重载 () 运算符 return (double)(a1 + a2+a3) / 3; ; / 重载 () 运算符时，参数可以是任意多个o CMyAverage Average; /函数对象o cout T accumulate(InIt first, InIt last, T val, Pred pr); opr 就是个函数对象，实际上是个函数也可以对 first,last)中的每个迭代器 I, 执行val = pr(val,* I) ,返回最终的val#include #include #include #include #include using
9、namespace std; int sumSquares( int total, int value) return total + value * value; template class SumSquaresClass public: const T ;int main() const int SIZE = 10;int a1 = 1, 2,3,4,5,6,7,8,9,10 ; vector v(a1,a1+SIZE); ostream_iterator output(cout,“ “); cout s; result = accumulate(v.begin(),v.end(),0,
10、s); / (1) cout public:const T ;.result = accumulate(v.begin(),v.end(),0,SumSquaresClass(); /(1)效果一样北京大学程序设计实习课程函数对象类模板obinary_function定义： template struct binary_function typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; ; 北京大学程序设计实习课程函数对象类模板oSTL 的 里还有以下
11、函数对象类模板 (v2版的P750/ v5版的P879)：ndividesnequal_tongreaternlessn.o这些模板可以用来生成函数对象北京大学程序设计实习课程greater 函数对象类模板template struct greater : public binary_function bool operator()(const T ;北京大学程序设计实习课程greater 的应用olist 有两个sort函数，前面看到的是不带参数的 sort函数，它将list按 pr); 可以用来进行降序排序#include #include using namespace std; int
12、 main() const int SIZE = 5; int aSIZE = 5,1,4,2,3; list lst(a,a+SIZE); lst.sort(greater();/greater()是个对象/本句进行降序排序 ostream_iterator output(cout,“,“); copy( lst.begin(),lst.end(),output); cout , class A = allocator class multiset ;o第二个参数 Pred 是个函数对象nPred决定了multiset 中的元素，“一个比另一个小”是怎么定义 的，即 Pred(x,y) 如果
13、返回值为true,则 x比y小nPred的缺省值是 lessoless 模板的定义： template struct less : public binary_function bool operator()(const T 就等效于 multiset a;o由于less模板是用 using namespace std; class A ; int main() multiset a; a.insert( A(); /errorreturn /编译出错是因为，插入元素时，multiset会将被插入元素 和已有元素进行比较，以决定新元素的存放位置。本 例中缺省地就是用less函数对象进行比较，然
14、而 less函数对象进行比较时，前提是A对象能用 struct pair typedef T first_type; typedef U second_type;T first; U second;pair(); pair(const T template pair(const pair ; opair模板可以用于生成 key-value对om.equal_range(k)：返回一个迭代器的pair对象；它的 first成员等价于m.lower_bound(k)，而second成员则等价 于m.upper_bound(k) 北京大学程序设计实习课程pair模板opair模板类用来绑定两个对象为
15、一个新的对象，该类型 在头文件中定义。opair模板类支持如下操作：npair p1：创建一个空的pair对象，它的两个元素分别 是T1和T2类型，采用值初始化npair p1(v1, v2)：创建一个pair对象，它的两个元素分 别是T1和T2类型，其中first成员初始化为v1，second成员初始 化为v2nmake_pair(v1, v2)：以v1和v2值创建一个新的pair对象，其元素 类型分别是v1和v2的类型np1 #include using namespace std; class MyLess;class A private:int n; public: A(int n_ ) n = n_; friend bool operator MSET1;typedef multiset MSET2;/ MSET2 里，元素的排序规则与 MSET1不同，/假设 le 是一个 MyLess对象，a1和a2是MSET2对象/里的元素，那么， le(a1,a2) = true 就说明 a1比
