前言：

　　在这个笔记中，我把大多数代码都加了注释，我的一些想法和注解用蓝色字体标记了出来，重点和需要关注的地方用红色字体标记了出来。

　　在这一篇文章中，我们主要对标准模板库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是用的大小判断来找的，所以这里找到了

后记：

　　这一篇好长好长啊，估计不会有人看完吧，其实这是考试周，那我现在在干嘛，考试周不好好复习在这捣鼓这些东西，还捣鼓了两个下午（*愤怒*）！明白了，这就去复习，再学这些东西我考试就要挂科了，大家千万不要模仿，感谢大家读到这里，下次再见（下次估计就是考试结束之后了）