前言：
在这个笔记中，我把大多数代码都加了注释，我的一些想法和注解用蓝色字体标记了出来，重点和需要关注的地方用红色字体标记了出来。
在这一篇文章中，我们主要对标准模板库STL进行各方面的介绍
1. 泛型程序设计
C++语言的核心优势之一就是便于软件的重用
C++中有两个方面体现重用：
1.面向对象的思想：继承与多态，标准类库
2.泛型程序设计（generic programming）的思想：模板机制，以及标准程序库STL
简单的说就是使用模板的程序设计法。
将一些常用的数据结构（链表，数组，二叉树）和算法（排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。
标准模板库（Standard Template Library）就是一些常用数据结构和算法的模板的集合。
有了STL，不必再写大多的标准数据结构与算法，并且可以获得非常高的性能。（一般来说自己写的还没他们写的效率高）
2. STL中的基本的概念
容器：可容纳各种数据类型的通用数据结构，是类模板
迭代器：可用于依次存取容器中的元素，类似于指针
算法：用来操作容器中的元素的函数模板
sort()来对一个vector中的数据进行排序
find()来搜索一个list中的对象
算法本身与他们操作的数据的类型无关，因此他们可以从简单数组到高度复杂容器的任何数据结构上使用。
int array[100];
该数组就是容器，而int* 类型的指针变量就可以作为迭代器，sort算法可以作用于该容器上，对其进行排序：
sort(array,array+70);
这里的array就是迭代器
3. 容器概述
可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是类模板，分为三种：
1）顺序容器
vector（动态数组，一维数组），deque（双向队列），list（双向链表）
2）关联容器
set，multiset，map，multimap（本质上来说都是平衡二叉树，查找效率高，自带排序）
3）容器适配器
stack（栈），queue（队列），priority_queue（优先级队列）
对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载==和<运算符。
4. 顺序容器简介
容器并非排序的，元素的插入位置同元素的值无关。
有vector，deque，list三种
vector：
头文件：#include<vector>
动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能（大部分情况下是常数时间）（特殊情况下是O(n)时间，在超出它预先分配的空间的时候，再增加元素就要这么多时间了，包括重新分配空间和把原来的空间的元素复制过来的时间）。在前面增删元素也是需要更多时间的，可以直接当作数组来理解。
deque：
头文件：#include<deque>
双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（但次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）（这玩意这样理解比较好：普通的数组是从下标0开始，但是这玩意是从n开始，所以能在n-1存元素，相应的算法相信一看到是这样存的都懂了，不过它有一点处理很有意思：在队尾存到不能再存的时候，它会把下个元素存到a[0]，然后把队尾设成对应下标，相当于循环队列了）
list：
头文件：#include<list>
双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
5. 关联容器简介
1、元素是排序的
2、插入任何元素，都按相应的排序规则来确定其位置
3、在查找时具有非常好的性能
4、通常以平衡二叉树方式实现，插入和检索的时间都是O(log(N))
set/multiset
头文件：#include<set>
set即集合。set中不允许相同元素，multiset中允许存在相同的元素。（一般来说我就是把它当集合来用，看一看哪个元素是否访问过了之类的）
map/multimap
头文件：#include<map>
map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first，另一个名为second，map根据first值对元素进行从小到大排序（可以自定义排序方式的），并可快速地根据first来检索元素。（有点像python里面的字典，哈哈哈，说不定是同一个东西）
map同multimap的不同在于是否允许相同first值的元素。
6. 容器适配器简介
stack
头文件：#include<stack>
栈。是项的有限序列，并满足序列中被删除，检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出。
queue
头文件：#include<queue>
队列。插入只可以在尾部进行，删除，检索和修改只允许从头部进行。先进先出。
priority_queue
头文件：#include<queue>
优先级队列。最高优先级元素总是第一个出列。
7. 顺序容器和关联容器都有的成员函数
begin：返回指向容器中第一个元素的迭代器
end：返回指向容器中最后一个元素后面位置的迭代器
rbegin：返回容器中最后一个元素的迭代器
rend：返回指向容器中第一个元素前面位置的迭代器（r==reverse）
erase：从容器中删除一个或几个元素
clear：从容器中删除所有元素
8. 顺序容器的常用成员函数
front：返回容器中第一个元素的引用
back：返回容器中最后一个元素的引用
push_back：在容器末尾增加新元素
pop_back：删除容器末尾的元素
erase：删除迭代器指向的元素（可能会使得该迭代器失效），或删除一个区间，返回被删除元素后面那个元素的迭代器
9. 迭代器
1、用于指向顺序容器和关联容器中的元素
2、迭代器用法和指针类似
3、有const和非const两种
4、通过迭代器可以读取它指向的元素
5、通过非const迭代器还能修改其指向的元素
定义一个容器类的迭代器的方法可以是：
容器类名::iterator 变量名;
或：
容器类名::const_iterator 变量名;
访问一个迭代器指向的元素：
*迭代器变量名
迭代器上可以执行++操作，以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，这时再使用它，就会出错，类似于使用NULL或未初始化的指针一样。
样例：
1 #include<vector>
2 #include<iostream>
3 using namespace std;
4
5 int main(int argc, char const *argv[])
6 {
7 vector<int> v;//一个存放int元素的数组，一开始里面没有元素
8 v.push_back(1);
9 v.push_back(2);
10 v.push_back(3);
11 v.push_back(4);
12 vector<int>::const_iterator i;//常量迭代器
13 for ( i = v.begin(); i != v.end(); i++)
14 {
15 cout<<*i<<",";
16 }
17 cout<<endl;//输出：1,2,3,4,
18 vector<int>::reverse_iterator r;//反向迭代器
19 for (r = v.rbegin(); r != v.rend(); r++)
20 {
21 cout<<*r<<",";
22 }
23 cout<<endl;//输出：4,3,2,1,
24 vector<int>::iterator j;//非常量迭代器
25 for ( j = v.begin(); j != v.end(); j++)
26 {
27 *j = 100;
28 }
29 for ( i = v.begin(); i != v.end(); i++)
30 {
31 cout<<*i<<",";
32 }
33 cout<<endl;//输出：100,100,100,100,
34 return 0;
35 }
样例
10. 双向迭代器
若p和p1都是双向迭代器，则可对p，p1进行以下操作：
++p，p++：使p指向容器中下一个元素
--p，p--：使p指向容器中上一个元素
*p：取p指向的元素（可以用来修改元素的值）
p = p1：赋值
p == p1，p!=p1：判断是否相等、不等
正确的遍历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
for( int i = 0; i < v.size(); ++i)
cout<<v[i]
（双向迭代器不支持<，list没有[]成员函数）
11. 随机访问迭代器
若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有以下几种做法：
1 #include<vector>
2 #include<iostream>
3 using namespace std;
4
5 int main(int argc, char const *argv[])
6 {
7 vector<int> v;
8 v.push_back(1);
9 v.push_back(2);
10 v.push_back(3);
11 v.push_back(4);
12
13 for (int ii = 0; ii < v.size(); ii++)
14 {
15 cout<<v[ii];//根据下标随机访问
16 }
17 cout<<endl;
18 vector<int>::const_iterator i;
19 for ( i = v.begin(); i != v.end(); i++)
20 {
21 cout<<*i;//i != v.end;
22 }
23 cout<<endl;
24 for ( i = v.begin(); i < v.end(); i++)
25 {
26 cout<<*i;//i < v.end;
27 }
28 cout<<endl;
29 i = v.begin();
30 while (i < v.end())
31 {
32 cout<<*i;
33 i = i+2;//间隔一个输出
34 }
35
36 return 0;
37 }
样例
12. 容器对应的迭代器
vector：随机访问迭代器
deque：随机访问迭代器
list：双向迭代器
set/multiset：双向迭代器
map/multimap：双向迭代器
stack：不支持迭代器
queue：不支持迭代器
priority_queue：不支持迭代器
（这样看来其实底层是数组实现的就是随机访问迭代器，底层不是数组的是双向迭代器，最后队列和栈因为不提供逐个访问的功能就不能用迭代器了）
注：有的算法，例如sort，binary_search需要通过随机访问迭代器来访问容器中的元素，那么list以及关联容器就不支持该算法。
13. 算法简介
1、算法就是一个个函数模板，大多数在<algorithm>中定义
2、STL中提供能在各种容器中通用的算法，比如查找，排序等
3、算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找
4、有的算法返回一个迭代器。比如find()算法，在容器中查找一个元素，并返回一个指向该元素的迭代器
5、算法可以处理容器，也可以处理普通数组
14. 算法示例：find()
template<class init, class T>
init find(init first, init last, const T& val)
1、first和last这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点[first,last)。区间的起点是位于查找范围之中的，而终点不是。find在[first,last)查找等于val的元素
2、用 == 运算符判断相等
3、函数返回值是一个迭代器。如果找到，则返回该迭代器指向被找到的元素。如果找不到，则该迭代器等于last
样例：
1 #include<vector>
2 #include<algorithm>
3 #include<iostream>
4 using namespace std;
5
6 int main(int argc, char const *argv[])
7 {
8 int array[10] = {10,20,30,40};
9 vector<int> v;
10 v.push_back(1);
11 v.push_back(2);
12 v.push_back(3);
13 v.push_back(4);
14 vector<int>::iterator p;
15 p = find(v.begin(),v.end(),3);
16 if (p != v.end())
17 {
18 cout<<*p<<endl;//输出：3
19 }
20 p = find(v.begin(),v.end(),9);
21 if (p == v.end())
22 {
23 cout<<"not found"<<endl;//输出：not found
24 }
25 p = find(v.begin()+1,v.end()-2,1);//整个容器：[1,2,3,4]，查找区间：[2,3)
26 if (p != v.end())
27 {
28 cout<<*p<<endl;//输出：3//v.end()指向的是3
29 }
30 int *pp = find(array,array+4,20);//数组名是迭代器
31 cout<<*pp<<endl;//输出：20
32 return 0;
33 }
样例
（注意：STL中只要提到区间，那么它们都是左闭右开的）
15. STL中“大”，“小”的概念
1、关联容器内部的元素是从小到大排序的
2、有些算法要求其操作的区间是从小到大排序的，称为“有序区间算法”，如：binary_search
3、有些算法会对区间进行从小到大排序，称为“排序算法”，如：sort（这里的大和小的定义可以自己设定，可以看我以前的笔记）
4、还有一些其他算法会用到“大”，“小”的概念
在使用STL时，在缺省的情况下，以下三个说法等价：（这里的缺省指没有自己定义的情况下）
1）x比y小
2）表达式“x<y”为真
3）y比x大
16. STL中相等的概念
有时，“x和y相等”等价于“x==y为真”
例：
在未排序的区间上进行的算法，如排序查找find
有时“x和y相等”等价于“x小于y和y小于x同时为假”（这里的小于也是可以自定义的，不是严格意义上的小于，比如我设定大于为“x个位数大于y则x>y”，那么在这种情况下11等于1）
例：
有序区间算法，如binary_search
关联容器自身的函数成员find
17. STL中“相等”的概念的演示
样例：
1 #include<algorithm>
2 #include<iostream>
3 using namespace std;
4
5 class A
6 {
7 int v;
8 public:
9 A(int n):v(n){}
10 bool operator <(const A & a2)const
11 {
12 cout<<v<<"<"<<a2.v<<"?"<<endl;
13 return false;//总是不成立
14 }
15 bool operator ==(const A & a2)const
16 {
17 cout<<v<<"=="<<a2.v<<"?"<<endl;
18 return v == a2.v;
19 }
20 };
21 int main(int argc, char const *argv[])
22 {
23 A a[] = {A(1),A(2),A(3),A(4),A(5)};
24 cout<<binary_search(a,a+4,A(9));//折半查找
25 /*
26 输出：
27 3<9?
28 2<9?
29 1<9?
30 9<1?
31 1
32 */
33 return 0;
34 }
可见binary_search是用的大小判断来找的，所以这里找到了
后记：
这一篇好长好长啊，估计不会有人看完吧，其实这是考试周，那我现在在干嘛，考试周不好好复习在这捣鼓这些东西，还捣鼓了两个下午（*愤怒*）！明白了，这就去复习，再学这些东西我考试就要挂科了，大家千万不要模仿，感谢大家读到这里，下次再见（下次估计就是考试结束之后了）