走向C++之路 WindyWinter windy@ream.at WindyWinter感谢诸位前来捧场。 #include <stdio.h> main(t ,_,a) char*a;{return t<1?main(*a,a[-t],"=a-1kj3gnm:q\ ebh_cf*<r.d>i^+?,()[?qzyrjuvcdefg\ h,!kbpolwxs'.t main(")&&a[-t]&&main (t-1,_,a):t/2?_==*a?putchar(32[a]) :_%115<36||main(t,_,a+1):main( 0,t,"+b:s?#mw{ty}t(x1{|~?\ y<#q?(*#{k)}rsh?vts){\ ?w*#yk<y,}w}z!w)v\ ~>u:!zym^t|x|\ |xtutu!uz\ |#}t") ;}

模板与泛型编程 I First things first

模板 Actually, there is only one template. 实践中需要不同的min函数 int min(int a, int b) { return a>b ? b : a; } double min(double a, double b) { return a>b ? b : a; } 如果还需要其他类型的min怎么办？ char short long long-long float long-double … 类型抽象——T类型 template <typename T> T min(T a, T b) { return a>b ? b : a; } min(1.2, 1.5); min(1, 2.0); template <typename T, typename P, typename R> R min(T a, P b) { return a>b ? b : a; } min<int>(1, 2.0); 想象不止有这几个内置类型，还有很多很多很多类类型，那一个工程里面光min函数就得几十上百个；如果再加上max函数…… 这些min函数的函数体都是一模一样的，唯一不同的是参数和返回值的类型，如果能够把类型当作一个“变量”，就能大幅节省编码时间了。 函数模板。T叫做模板参数，代表某个类型。函数模板不是函数，需要经过一个“实例化”的过程变成函数——在首次调用的时候，编译器推断T的实际类型，生成对应类型的函数。typename也可以写成class，两个的意义是一样的。 这个函数模板写的不好，修改一下？回忆引用、常量引用、拷贝构造函数。 如果编译器无法推断出T类型是什么（推断的时候没有隐式类型转换），那么编译出错。 如果推断出来T使得代码编译不过——比如T类型不能比较大小（如数组类型），那么编译出错。解决的办法是多设定几个模板参数，带来的问题是调用时必须显示指定R代表的类型，否则编译器无从推断R是什么。

模板 类也需要多样性——平面点类： Z×Z R×R C×C Sorry, there does exist the 2nd one. 类也需要多样性——平面点类： Z×Z R×R C×C template <typename T> struct Point { T x, y; }; Z×Z -> Point<int> R×R -> Point<double> C×C -> Point<complex<double> > 类模板。类模板经过实例化变成类。 实例化的方法，与函数不同，类模板实例化必须显式写出模板参数。 模板参数不同的模板实例是不同的类，彼此之间没有任何关系，不能互相访问私有成员。 complex本身也是一个类模板，是C99给复数设计的，complex<double>就是数学上的复数。

模板 模板参数不限于类型。 除类型以外还可以是整数——常用于定义数组类型： The template is really complex. 模板参数不限于类型。 除类型以外还可以是整数——常用于定义数组类型： template<typename T, int N> struct Array { T mData[N]; T & operator[](const int i) { return mData[i]; } const T & operator[](const int i) { return mData[i]; } }; 模板参数还可以是任何可以转化为整数的东西： char bool 枚举类型 定义一个数组类型的用途，或者是好处是什么？ ——检查数组越界，数组越界是常见的错误，如果在operator[]里面加入对下标的检查，可以有效避免。成为“安全数组”。 ——方便数组复制，数组不能直接复制，即使是两个类型一样的数组也不行，但是定义成数组类型，就可以利用编译器合成的拷贝构造函数复制数组。

标准模板库 Hallowed are the C++

标准模板库 C语言有一个小巧精干的标准库； C++在引入泛型编程的思想后，标准库得到了广泛的、革命性的变革——标准模板库。 STL C语言有一个小巧精干的标准库； C++在引入泛型编程的思想后，标准库得到了广泛的、革命性的变革——标准模板库。 string获得大量类的特性； vector、list、deque、queue、stack、priority_queue、set/map纷纷进入STL； STL中的函数不再限定参数的类型，而只做出基本要求： min、max、sort要求此种类型定义过”<“； binary_search要求传递进来的序列可以随机访问； …… 什么是标准库？ 广泛的、革命性的变革，成为标准模板库。C++实现泛型编程思想的工具就是模板。 string相比于C风格字符串，获得了大量类的特性：长度保存为成员变量；插入、删除、查找、取子串是成员函数；两个string可以用+连接成为一个string。 vector——动态增长的数组、list——链表、deque——块状链表/双端队列，统称为容器； priority_queue——堆/优先队列，set/map——平衡二叉树，统称为容器适配器。 C标准库函数要求一个数组或序列时，常采用传递void指针+单个元素的体积的形式，STL受益于模板，不必再如此麻烦。

string #include<string> 成员函数： []：返回指定位置的字符； size()、length()：返回长度，O(1)时间； clear()：清空； +=、insert()：插入； erase()：删除； find()：查找； substr()：取子串； +：连接。 使用string需要引入string头文件。 []是string重载的运算符，使string用起来像C风格字符串一样。 求C风格字符串的长度，用C标准库的strlen函数，将遍历整个字符串，直到找到结尾标志\0为止，所用时间是O(n)，string求长度只需要常数时间。 +=也是重载的运算符，用于将一个字符附加到末尾。

string <、>、<=、>=、==、！= getline(cin, str)：从标准输入流cin读取一行，放入str。 cout<<str：从标准输出流cout输出str。 cin>>str：从标准输入流读取一个字符串（以非空白字符开头、空白字符结尾），放入str。 它们的详细用法、函数原型，以及更多的成员函数和用法，请去http://www.cplusplus.com/reference/string/string 查找。 这六个比较运算符被重载，比较两个string的大小是按字典序。

vector #include<vector> vector<T> a; [], at()：取指定位置的元素，[0]是第一个元素； size()：vector的长度； push_back()：将一个元素插入到vector的最后面； insert()、clear()、erase() http://www.cplusplus.com/reference/stl/vector/ vector是长度可变的数组，内部机制是数组。vector可以扩大和缩小，满了之后扩容为两倍，空了之后缩小为一半。 定义一个元素为T类型的vector。一个刚刚定义的vector一个元素也没有，容量是100。 []保持了与数组的一致性，取不存在元素会出现问题，但不会报错；成员函数at也实现了去指定位置的元素，但取不存在的元素时会报错。 通常用push_back为vector增加新元素。

迭代器 最简单的迭代器相当于指向容器中元素的指针； vector<T>::iterator i; iterators 最简单的迭代器相当于指向容器中元素的指针； vector<T>::iterator i; i=a.begin(); *i 取得一个元素的引用；i->push_back()。 a.end() 表示“超出末端的位置”： for (i=a.begin(); i<a.end(); ++i) vector的迭代器可以随机访问： --i; i += 2; i -= 6; 与iterator相仿的是reverse_iterator，对应有rbegin()、rend()。 其他类型的迭代器比较复杂。 http://www.cplusplus.com/reference/std/iterator/ a.begin()返回一个迭代器，指向a中的第一个元素。 与指针一样，对迭代器使用解引用运算符，可以得到迭代器指向的那个元素的引用。 看下面这个循环，i初始化为a的第一个元素的位置，每次++i，表示将i后挪一个位置，a.end()表示“超出末端的位置”，于是a中每个元素的位置都在a.end()之前，当i==a.end()时，说明i已经挪到了a之外，不再指向a中某个元素的位置了。于是这个循环遍历了a中的每一个元素。 表示前移1个位置、后挪2个位置，前移6个位置，若向后挪到了a之外，则i会与a.end()相等，向前挪到a之外，则会自动挪到第一个位置。随机访问就是指可以跳跃性的访问任意一个元素，而不需要一个一个挪。 reverse_iterator的特点是，+表示向前挪，-表示向后挪；rbegin()是a的最后端，rend()是“超出前端”。

list #include<list> list<T> b; size()：list的长度，O(1)时间； push_back()/push_front()：将一个元素插入到list的最后面/最前面； insert()、clear()、erase() splice()、merge() list<T>::iterator 只能++/--，不能随机访问。 http://www.cplusplus.com/reference/stl/list/ list是链表，内部实现机制为双向链表。 list类型不用[]取元素，只能用迭代器。 list的迭代器不能随机访问，只能前移1位，后移1位。

迭代器 迭代器的失效——如果一个迭代器指向的元素已经被删除，那么该迭代器失效，访问该迭代器后果不可预料。 迭代器的分类： 随机访问迭代器 iterators 迭代器的失效——如果一个迭代器指向的元素已经被删除，那么该迭代器失效，访问该迭代器后果不可预料。 迭代器的分类： 随机访问迭代器 前向迭代器 双向迭代器 输入迭代器 输出迭代器 正向迭代器 反向迭代器 常量迭代器 流迭代器 五种迭代器——Primer 356页。 常量迭代器用于当容器是个常量，带有const属性的时候，正常的迭代器默认元素是左值，可以更改，常量迭代器指定元素是右值，就像指向常量的指针一样。

sort #include<algorithm> vector<int> a; sort(a.begin(), a.end()); vector<person> c; sort(c.rbegin(), c.rend()); int b[100]; sort(b, b+100); list<double> d; sort(d.begin(), d.end()); X d.sort() O http://www.cplusplus.com/reference/algorithm/sort/ STL除了提供各种基本数据结构之外，也提供基本算法。sort是STL中提供的最常用的排序算法，在algorithm头文件中，其内部实现是冒泡排序和快速排序。 C标准库中有一个qsort函数，那个函数要求一段数组和一个比较函数。sort在这一点上与qsort很相似，它要求一对能随机访问的迭代器，一个指向序列开头，一个指向序列的“超出末端位置”， 并不要求这两个迭代器是正向的还是反向的，另外它要求被排序的序列中的元素带有<运算符，且<运算符必须被定义为严格小于——即表达式(x<x)必须返回false/0。 sort也可以用于排序数组，此时数组的头指针就是序列的开头，最后一个元素的位置+1就是“超出末端位置”。 下面，直接用sort去排序一个链表是不行的，因为sort要求随机访问迭代器，而链表的begin和end返回的迭代器不能随机访问。但链表提供了自己的sort函数，内部实现也是快速排序。

其他的小工具 #include<algorithm> min(a, b) max(a, b) swap(a, b) http://www.cplusplus.com/reference/algorithm/ 这三个小工具分别求a,b中较小的一个，较大的一个，以及交换a,b的值。 STL中包括很多好用的工具，善用这些工具，能让我们写程序事半功倍。

流输入输出 严格来说，这不是STL的一部分。 iostream——scanf/pringf fstream——fscanf/fprintf stringstream——sscanf/sprintf cin>>XXX; cout<<XXX; ifstream fin(“input.txt”); ofstream fout(“output.txt”); fin>>XXX; fout<<XXX; stringstream s; s<<XXX; s>>XXX; http://www.cplusplus.com/reference/iostream/ C中提供了scanf、printf等操作IO流的函数，C++又提供了更高层次的流操作，iostream，fstream，stringstream，他们分别对应于C中的XXX。 所有stream类的东西，用法都非常相似。cin和cout是C++标准定义的两个标准对象，分别代表标准输入和标准输出。只要某个类型具有与stream类相关的<</>>，就可以用这个三种流做输入输出。WEBase的Time类就有一个重载的<<运算符，在Utilitites.h的471行。 cin输入一个变量之后，会在内部设置成功/失败标志符，直接把cin写在bool表达式里面，就返回成功/失败，true/false，这就是while(cin>>x>>y)的写法，cin遇到输入截止，返回失败。 除了cout之外，iostream还包括clog、cerr两个标准输出对象，分别对应于log输出和错误输出。

Tags Cloud Soli Deo gloria. string vector list 迭代器 sort Keywords string vector list 迭代器 sort iostream fstream stringstream 到这里为止，C++的部分就介绍完了，今天的内容更像是一篇读书指引，只告诉了大家C++提供了哪些东西，至于这些东西如何使用，却要依靠大家自己去钻研，去发掘。 对于被我破坏了学习C++的兴趣的同学，我感到非常的抱歉——C++是一门优美的语言，大煞风景的只是我糟糕的讲课水平，希望你们仍能以平和的心态面对C++，实在无法平静，就转向Java吧；对于忍受了我两次折磨却坚持下来的同学，我借用winsty的一句话送给你们——执着未必能感动上苍，坚持一定会创造奇迹！ Soli Deo gloria.

勘误和补充 友元可以是定义和声明在一起 直接调用构造函数的例子： Vector(1.0, 1.0)，生成一个临时的Vector对象。 explicit关键字： 一个类的带参构造函数，可以定义一种把某种类型转换为该类的隐式类型转换。explicit关键字加在某个构造函数的声明前，禁止这种隐式类型转换。 模板与泛型编程 II： C++ Lite Memo 溯源 授人以渔 Vector是WEBase中的平面点类。 C++ Primer 394页。 模板与泛型编程II不属于本次课程的内容。C++于1983年在贝尔实验室诞生，迄今为止经历了三个发展阶段： 面向对象阶段（第一天课程），1979年~1995年。C++作为C语言的扩充，完善面向对象特性。 泛型编程阶段（第二天课程），1995年~2000年。C++的模板机制最早在1991年出现，之后HP写出了第一份标准模板库的实现，并于1994年底进入C++标准（ANSI）。到1998年C++的第一个ISO标准出现时，C++在全世界程序设计语言中的占有率达到了史无前例的76%。之后由于Java和C#等新兴语言的出现，C++不断受到冲击。该阶段到模板的集大成者——boost库出现为止。 模板元编程阶段，2000年~今。在不断尝试模板编程的过程中，人们发现C++的模板机制是图灵完备的（一个语言是图灵完备的，意味着该语言的计算能力与一个通用图灵机相当，这也是现代计算机语言所能拥有的最高能力）。于是boost库的一个分支mpl出现了。迄今为止，C++的模板仍然是所有编程语言的模板中唯一图灵完备的。模板与泛型编程II就是指模板元编程的部分。