泛型编程STL 与 ACM Roba课件
泛型编程,STL与ACM,何亮 2009-07,Generic Programming,实现一个max函数，返回两参数中的较大值 要求可以处理多种数据类型 方法一： int max(int a, int b) return ab?a:b; double max(double a, double b) return ab?a:b; string max(string a, string b) return ab?a:b; char max(char a, char b) 缺点：大量重复工作，扩展性差,Generic Programming,方法二: 函数模版 template T mymax(T a, T b) return a b ? a : b; /可把typename换成class,类型参数,Generic Programming,函数模版的调用 int main() cout<<mymax(3, 4)<<endl; cout<<mymax(3.1, 4.0)<<endl; string a = “roba”, b = “acm”; cout<<mymax(a,b)<<endl; ,Generic Programming,与宏替换不同，函数模版是在编译期“实例化” 隐式指定参数类型，如上所示 cout(3, 4); mymax(3, 4.1);/正确，3被转换成double型,Generic Programming,类模版：与函数模版类似 template class myClass public: T data; void output() cout<<data<<endl; ,Generic Programming,类模版的实例化 int main() myClass c; c.data = 1; c.output(); myClass c2; c2.data = “tju”; c2.output(); ,Generic Programming,类型参数可以有多个 template T f(T a, U b) 可以指定缺省类型 可以对某些特定类型进行“特化” (specialization) 可以用int作为类型参数 template ,Template Metaprogramming,template class Sum public: static const int x = Sum:x + N; ; template class Sum public: static const int x = 0; ; int main() int k = Sum:x; printf(%dn,k); return 0; ,STL: Standard Template Library 标准模版库 一些重要的概念: 容器(container): 迭代器(iterator): 指针, 内部实现: 数组 vector 支持操作: begin(), end(), size(), clear(), empty(), push_back(), pop_back() insert()O(N) erase()O(N) 可以用于数组大小不定且空间紧张的情况,Sample: TOJ1743 Kings Treasure #include #include using namespace std; vector a240010; int main() int cases,n,i,t,head,tail,src,pans; scanf(%d, Full Code,Iterator用法举例: #include #include using namespace std; int main() int n,i; vector vi; vector :iterator itr; while (scanf(%d, , 支持push_front()和pop_front() 支持push(), pop(), top() 支持push(), pop(), front(), back(), 内部实现: 双向链表 list 支持操作: begin(), end(), size(), clear(), empty() push_back(), pop_back() push_front(), pop_front() insert()O(1) erase()O(1) sort()O(nlogn),不同于中的sort, 内部实现: 红黑树 set insert() O(logn) erase() O(logn) * find() O(logn) 找不到返回a.end() lower_bound() O(logn) 查找第一个不小于k的元素 upper_bound() O(logn) 查找第一个大于k的元素 equal_range() O(logn) 返回pair 允许重复元素,用法: struct SS int x,y; struct ltstr bool operator() (SS a, SS b) return a.x st; ,UVA 105 The Skyline Problem 给定一些楼房的范围和高度，求出他们的轮廓。 Input: 1 11 5 2 6 7 3 13 9 12 7 16 14 3 25 19 18 22 23 13 29 24 4 28 Output: 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 维护一个BST，可以得到复杂度O(nlogn)的算法 可以使用简化编程 Code here , 内部实现: pair组成的红黑树 map insert() O(logn) erase() O(logn) find() O(logn) 找不到返回a.end() lower_bound() O(logn) 查找第一个不小于k的元素 upper_bound() O(logn) 查找第一个大于k的元素 equal_range() O(logn) 返回pair key运算符 O(logn) * 允许重复元素, 没有运算符,TOJ 1378 Babelfish Code: (0.4k) #include #include #include using namespace std; map mp; int main() char buf100,s1100,s2100; while (gets(buf) if (strlen(buf) = 0) break; sscanf(buf,%s%s,s1,s2); mp(string)s2 = (string)s1; , while (gets(buf) if (mp.find(string)buf) != mp.end() printf(%sn,mp(string)buf.c_str(); else printf(ehn); return 0; ,A challenge: TOJ 2175 Computer Games ,TOJ 2796 Erdos Number BFS 图不是以编号形式给出，而是以名字形式给出 用map进行编号 Code Here, 内部实现: 堆 priority_queue 支持操作: push() O(logn) pop() O(logn) top() O(1) See also: push_heap(), pop_heap() in ,用法举例: #include #include using namespace std; priority_queue maxheap;/int最大堆 struct ltstr bool operator()(int a,int b) return a b; ; priority_queue ,ltstr minheap;/int最小堆, 内部实现: Hash表, of course hash_map 重载HashFcn和EqualKey 支持操作: insert();O(1) earse();O(1) ; O(1) 示例：Again TOJ 1378 Babelfish See also: ,#include #include /? #include using namespace std; struct calc_hash size_t operator()(string str) const unsigned long h = 0; int i; for (i = 0 ; i < str.size() ; i+) h <<= 5; h |= stri - a; return (size_t)h;/h%M? ;,struct eqstr bool operator()(string s1, string s2) return s1 = s2; ;/本题此处可省略 int main() hash_map hp; char buf100,s120,s220; while (gets(buf) if (strlen(buf) = 0) break; sscanf(buf,%s%s,s1,s2); hp(string)s2 = (string)s1; while (gets(buf) if (hp.find(string)buf) != hp.end() printf(%sn,hp(string)buf.c_str(); else printf(ehn); return 0; , 1.sort() void sort(RandomAccessIterator first, RandomAccessIterator last); void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp); 区间first,last) 复杂度O(nlogn) (n=last-first,平均情况和最坏情况),用法举例: 1.从小到大排序(int, double, char, string, etc) const int N = 5; int main() int aN = 4,3,2,6,1; string strN = “TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”; sort(a,a+N); sort(str,str+N); return 0; ,2.从大到小排序（需要自己写comp函数) const int N = 5; int cmp(int a,int b) return a b; int main() int aN = 4,3,2,6,1; sort(a,a+N,cmp);/sort(a,a+N,greater() return 0;,3. 对结构体排序 struct SS int first,second; int cmp(SS a,SS b) if (a.first != b.first) return a.first first != (SS*)b)-first) return (SS*)a)-first (SS*)b)-first; return (SS*)a)-second (SS*)b)-second; qsort(array,n,sizeof(array0),cmp);,sort()系列: stable_sort(first,last,cmp);/稳定排序 partial_sort(first,middle,last,cmp);/部分排序 将前(middle-first)个元素放在first,middle)中，其余元素位置不定 e.g. int A12 = 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5; partial_sort(A, A + 5, A
