本章内容为coursera课程C++程序设计中第八周的课件的整理
泛型程序设计
C++ 语言的核心优势之一就是便于软件的重用C++中有两个方面体现重用：
1.面向对象的思想：继承和多态，标准类库；
2.泛型程序设计(generic programming) 的思想：模板机制，以及标准模板库 STL
简单地说就是使用模板的程序设计法。将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。
标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。
有了STL，不必再写大多的标准数据结构和算法，并且可获得非常高的性能。
STL中的基本的概念 容器：可容纳各种数据类型的通用数据结构,是类模板 迭代器：可用于依次存取容器中元素，类似于指针 算法：用来操作容器中的元素的函数模板 sort()来对一个vector中的数据进行排序 find()来搜索一个list中的对象 算法本身与他们操作的数据的类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。
int array[100]; 该数组就是容器，而 int * 类型的指针变量就可以作为迭代器，sort算法可以作用于该容器上，对其进行排序：
sort(array,array+70); //将前70个元素排序，数组名是迭代器容器概述 可以用于存放各种类型的数据（ 基本类型的变量，对象等）的数据结构，都是类模版,分为三种： 1)顺序容器 vector, deque,list 2)关联容器 set, multiset, map, multimap 3)容器适配器 stack, queue, priority_queue
对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载== 和<运算符。
顺序容器简介 容器并非排序的，元素的插入位置同元素的值无关。 有vector,deque,list 三种 vector 头文件 <vector> 动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间）。
deque 头文件 <deque> 双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间）。
list 头文件 <list> 双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。 不支持随机存取。
关联容器简介 元素是排序的 插入任何元素，都按相应的排序规则来确定其位置 在查找时具有非常好的性能 通常以平衡二叉树方式实现， 插入和检索的时间都是 O(log(N)) set/multiset 头文件 <set> set 即集合。 set中不允许相同元素， multiset中允许存在相同的元素。 map/multimap 头文件 <map> map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,另一个名为second, map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素。 map同multimap的不同在于是否允许相同first值的元素。
容器适配器简介 stack 头文件 <stack> 栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。 后进先出。 queue 头文件 <queue> 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。 先进先出。 priority_queue 头文件 <queue> 优先级队列。最高优先级元素总是第一个出列 顺序容器和关联容器中都有的成员函数 begin 返回指向容器中第一个元素的迭代器 end 返回指向容器中最后一个元素后面的位置的迭代器 rbegin 返回指向容器中最后一个元素的迭代器 rend 返回指向容器中第一个元素前面的位置的迭代器 erase 从容器中删除一个或几个元素 clear 从容器中删除所有元素 顺序容器的常用成员函数 front :返回容器中第一个元素的引用 back : 返回容器中最后一个元素的引用 push_back : 在容器末尾增加新元素 pop_back : 删除容器末尾的元素 erase:删除迭代器指向的元素(可能会使该迭代器失效),或删除一个区间，返回被删除元素后面的那个元素的迭代器 迭代器 用于指向顺序容器和关联容器中的元素 迭代器用法和指针类似 有const 和非 const两种 通过迭代器可以读取它指向的元素 通过非const迭代器还能修改其指向的元素 定义一个容器类的迭代器的方法可以是： 容器类名::iterator 变量名; 或： 容器类名::const_iterator 变量名; 访问一个迭代器指向的元素： * 迭代器变量名 迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，就会出错，类似于使用NULL或未初始化的指针一样。 迭代器示例
#include <vector> #include <iostream> using namespace std; int main() { vector<int> v; //一个存放int元素的数组，一开始里面没有元素 v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::const_iterator i; //常量迭代器 for( i = v.begin();i != v.end();++i ) cout << * i << ","; cout << endl; vector<int>::reverse_iterator r; //反向迭代器 for( r = v.rbegin();r != v.rend();r++ ) cout << * r << ","; cout << endl; vector<int>::iterator j; //非常量迭代器 for( j = v.begin();j != v.end();j ++ ) * j = 100; for( i = v.begin();i != v.end();i++ ) cout << * i << ","; } 输出结果： 1,2,3,4, 4,3,2,1, 100,100,100,100, 双向迭代器 若p和p1都是双向迭代器，则可对p、 p1可进行以下操作： ++p, p++ 使p指向容器中下一个元素 --p, p-- 使p指向容器中上一个元素 * p 取p指向的元素 p = p1 赋值 p == p1 , p!= p1 判断是否相等、不等 随机访问迭代器 若p和p1都是随机访问迭代器，则可对p、 p1可进行以下操作： 双向迭代器的所有操作 p += i 将p向后移动i个元素 p -= i 将p向向前移动i个元素 p + i 值为: 指向 p 后面的第i个元素的迭代器 p - i 值为: 指向 p 前面的第i个元素的迭代器 p[i] 值为: p后面的第i个元素的引用p < p1, p <= p1, p > p1, p>= p1
容器 容器上的迭代器类别 vector 随机访问 deque 随机访问 list 双向 set/multiset 双向 map/multimap 双向
stack 不支持迭代器 queue 不支持迭代器 priority_queue 不支持迭代器
note：有的算法，例如sort，binary_search需要通过随机访问迭代器来访问容器中的元素，那么list以及关联容器就不支持该算法！
vector的迭代器是随机迭代器，遍历 vector 可以有以下几种做法(deque亦然)：
vector<int> v(100); int i; for(i = 0;i < v.size() ; i ++) cout << v[i];//根据下标随机访问 vector<int>::const_iterator ii; for( ii = v.begin(); ii != v.end ();ii ++ ) cout << * ii; //随机访问迭代器支持<操作 for( ii = v.begin(); ii < v.end ();ii ++ ) cout << * ii; //间隔一个输出： ii = v.begin(); while( ii < v.end()) { cout << * ii; ii = ii + 2; } list 的迭代器是双向迭代器，正确的遍历list的方法： list<int> v; list<int>::const_iterator ii; for( ii = v.begin(); ii != v.end ();++ii ) cout << * ii;错误的做法：
//双向迭代器不支持 <，下面做法错误 for( ii = v.begin(); ii < v.end ();ii ++ ) cout << * ii; //list不支持随机访问，没有 [] 成员函数，下面做法错误 for(int i = 0;i < v.size() ; i ++) cout << v[i];算法简介 算法就是一个个 函数模板, 大多数在<algorithm> 中定义 STL中提供能在各种容器中通用的算法，比如查找，排序等 算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找 有的算法返回一个迭代器。比如 find() 算法，在容器中查找一个元素，并返回一个指向该元素的迭代器 算法可以处理容器，也可以处理普通数组
算法示例： find()
template<class InIt, class T> InIt find(InIt first, InIt last, const T& val); first 和 last 这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点[first,last)。区间的起点是位于查找范围之中的，而终点不是。find在[first,last)查找等于val的元素，用 == 运算符判断相等。 函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器等于last。 #include <vector> #include <algorithm> #include <iostream> using namespace std; int main() { //find算法示例 int array[10] = {10,20,30,40}; vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator p; p = find(v.begin(),v.end(),3); if( p != v.end()) cout << * p << endl; //输出3 p = find(v.begin(),v.end(),9); if( p == v.end()) cout << "not found " << endl; p = find(v.begin()+1,v.end()-2,1); //整个容器：[1,2,3,4]， 查找区间：[2,3) if( p != v.end()) cout << * p << endl; int * pp = find( array,array+4,20);//数组名是迭代器 cout << * pp << endl; } 输出： 3 not found 3 20STL中“大”“小” 的概念 关联容器内部的元素是从小到大排序的 有些算法要求其操作的区间是从小到大排序的，称为“有序区间算法”。例：binary_search 有些算法会对区间进行从小到大排序，称为“排序算法”。例： sort 还有一些其他算法会用到“大”，“小”的概念。
使用STL时，在缺省的情况下，以下三个说法等价： 1) x比y小 2) 表达式“ x<y”为真 3) y比x大 STL中“相等”的概念 有时，“x和y相等”等价于“x==y为真”。例：在未排序的区间上进行的算法，如顺序查找find…… 有时“ x和y相等”等价于“ x小于y和y小于x同时为假”。例：有序区间算法，如binary_search；关联容器自身的成员函数find。
STL中“相等”概念演示
#include <iostream> #include <algorithm> using namespace std; class A { int v; public: A(int n):v(n) { } bool operator < ( const A & a2) const { cout << v << "<" << a2.v << "?" << endl; return false; } bool operator ==(const A & a2) const { cout << v << "==" << a2.v << "?" << endl; return v == a2.v; } }; int main() { A a [] = { A(1),A(2),A(3),A(4),A(5) }; cout << binary_search(a,a+4,A(9)); //折半查找 return 0; } 输出结果： 3<9? 2<9? 1<9? 9<1? 1
