第一章——STL

说到STL我们往往认为它是基于模板的，实现了很多数据结构及对应操作的容器库。

从概念上像上面理解一样理解没有问题，从库的内部结构来看，STL主要由container(容器)，algorithm(算法)和iterator(迭代器)三大部分构成。

容器就是指给你在库的内部已经实现好，可以让你直接调用的基于模板的数据结构类型，用于存放数据对象(元素)。常用的数据结构和相对应的头文件如下：

STL算法用于操作容器中的数据对象，即数据结构的对应操作，例如find()，sort()等，且由于STL容器是基于模板设计的，STL算法一般具有很好的通用性和灵活性，具体内容这里不多赘述。

尽管各种STL容器的内部结构并不是完全相同，但他们外部的一些框架都是类似的，例如线性结构；对数据操作也是类似的，例如访问第一个元素，清空所有的元素，求容器内存在有效元素的元素个数，将容器内的元素进行排序。

于是可以将对于STL容器的一些操作设计成通用在各个容器的STL算法，也就是说对于一些通用的操作(STL算法)，它们不再是某些STL容器自己的操作，而是独立出STL容器的通用算法，这些通用的STL算法就与STL容器分离开来了。

STL算法部分主要由头文件< algorithm >，< numeric >和< functional >组成。

由于大量的通用STL算法与STL容器分离开，我们在对容器内的数据进行操作时，需要一个将算法与容器连接起来的桥梁(中介)，STL迭代器在STL中就起到前两这样的作用。

迭代器的使用方式和指针非常类似：可以用迭代器加*去访问容器中的数据对象，每个容器都有自己的迭代器，算法通过迭代器来定位和操作容器中的元素(类似于函数以指针作为参数传递数据)，指针中++，–的运算符在迭代器中的用法和指针是一样的。

不过迭代器绝不是指针，它只是一个仿照指针的使用方式封装起来的类。

常见的迭代器如下

iterator：指向容器中存放元素的迭代器，用于正向遍历容器中的元素。
const_iterator：指向容器中存放元素的常量迭代器，只能读取容器中的元素。
reverse_iterator：指向容器中存放元素的反向迭代器，用于反向遍历容器中的元素。
const_reverse_iterator：指向容器中存放元素的常量反向迭代器，只能读取容器中的元素。

容器，算法，迭代器三者的关系如下图所示：

每个STL容器都是一个类模板，从数据元素按照什么样的逻辑关系存储到容器中分为顺序容器和关联容器(适配器容器是指基于其他容器实现的容器，也就是说适配器容器包含另一个容器作为其底层容器，在底层容器的基础上实现适配器容器的功能，在算法设计中可以将适配器容器作为一般容器来使用，所以我们这里不把它单独地分为一类)。

向量容器用于存储具有相同数据类型的一组元素，相当于不固定长度的数组，如果初始分配的空间不够，当超过空间大小时会重新分配更大的空间(就是我们在另一个专栏提到的扩容的操作，扩容通常按照两倍的大小进行扩展，具体原因见另专栏)。

可以从末尾快速的插入与删除元素，快速地随机访问元素，但是在序列中间插入、删除元素较慢，因为需要移动插入或删除处后面的所有元素。

定义vector容器的几种方式如下：

//定义元素为int的向量
v1vectorv1;
//指定向量v2的初始大小为10个int元素
vectorv2(10);
//指定v3的10个初始double元素的初值为1.23
vector v3(10,1.23);
//用数组a的5个元素初始化v4
vectorv4(a,a+5);

vector的成员函数及其功能如下：

容器名.empty()：判断当前向量容器是否为空。
容器名.size()：返回当前向量容器的中的实际元素个数。
容器名[]：返回指定下标的元素。
容器名.reserve(n)：为当前向量容器预分配n个元素的存储空间。
容器名.capacity()：返回当前向量容器在重新进行内存分配以前所能容纳的元素个数。
容器名.resize(n) ：调整当前向量容器的大小，使其能容纳n个元素。
(resize的功能较为复杂，如果当前向量容器的大小大于n，相当于截去第n个元素后面的元素；如果当前向量的大小小于n，相当于补充了若干个相同的元素)
容器名.push_back(elem)：在当前向量容器尾部添加了一个元素elem。
(同理有一个删除尾部元素的操作为pop_back，用法相同)
容器名.insert(pos,elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定元素之前。
容器名.front()：获取当前向量容器的第一个元素。
容器名.back()：获取当前向量容器的最后一个元素。
容器名.erase(pos)，容器名.erase(pos1,pos2)：删除当前向量容器中某个迭代器或者迭代器区间指定的元素。
容器名.clear()：删除当前向量容器中所有元素(但是不清空内存)。
容器名.begin()：返回iterator或const_iterator，引用容器的第一个元素。
容器名.end()：返回iterator或const_iterator，引用容器的最后一个元素的后面一个元素。
(end()不指向容器内的任何一个存在的元素,指向最后一个元素的下一个元素)
容器名.rbegin()：返回reverse_iterator或const_reverse_iterator，引用容器的最后一个元素。
容器名.rend()：返回reverse_iterator或const_reverse_iterator，引用容器的第一个元素的前面一个元素。

string是一个保存字符序列的容器，所有元素为字符类型，类似vector< char >(char数组，但各操作的效率都低于char数组，char指针数组，很多库的函数的参数都固定要求是char指针数组的指针变量而不是string变量)。

除了有字符串的一些常用操作以外，还有包含了所有的序列容器的操作。字符串的常用操作包括增加，删除，修改，查找比较，连接，输入，输出等(就是说重载了+，-，＞，＜，+=，-=，<<，>>等很多运算符)。

创建string容器的几种方式如下：

//创建char数组cstr 
char cstr[]="China! Greate Wall";
//用char数组cstr创建string类字符串s1	
string s1(cstr);
//用string类字符串s1创建string类字符串s2			
string s2(s1);
//截取char数组pos1到pos2之间的片段创建string类字符串s3				
string s3(cstr,pos1,pos2);
//从第0位开始从char数组cstr截取n个字符创建string类字符串s4		
string s4(cstr,n);
//以连续n个字符x创建string类字符串s5	 
string s5(n,char x);			

string的成员函数及其功能如下：

容器名.empty()：判断当前字符串是否为空串。
容器名.size()：返回当前字符串的实际字符个数(返回结果为size_type类型)。
容器名.length()：返回当前字符串的实际字符个数(一般用size)。
容器名[idx]：返回当前字符串位于idx位置的字符，idx从0开始。
容器名.at(idx)：返回当前字符串位于idx位置的字符。
容器名.compare(const string& str)：返回当前字符串与字符串str的比较结果。在比较时，若两者相等，返回0；前者小于后者，返回-1；否则返回1。
(可以直接使用重载后的><：s1>s2,s1 
deque(双端队列容器) 
deque是一个双端队列类模板(即只能从首和尾进行增删和访问的数据结构)。
 
双端队列容器内部由若干个块构成，每个块中元素地址是连续的，块之间的地址是不连续的，有一个特定的机制将这些块构成一个整体(从最基础的数据结构的角度来看就是多重队列——multi_queue)。
 
deque可以从前面或后面快速插入与删除元素，并可以快速地随机访问元素，但在中间位置进行增删就较慢。由于不像vector一样将所有的元素保存在一段连续的内存中，而是采用多个连续地存储块存放数据元素，所以空间的重新分配要比vector快，因为重新分配空间后原有的元素不需要被复制(和扩容的方式有关)。
 
创建deque容器的几种方式如下(和vector基本是一样的)：
 
//定义元素为int的双端队列dq1
dequedq1;	
//指定dq2的初始大小为10
dequedq2(10);
//指定dq3的10个初始double元素的初值为1.23	
dequedq3(10,1.23);
//用dq2的所有元素初始化dq4			
dequedq4(dq2.begin()，dq2.end());	
 
成员函数也是基本类似的：
 
容器名.empty()：判断双端队列容器是否为空队。
容器名.size()：返回双端队列容器中元素个数。
容器名.push_front(elem)：在队头插入元素elem。
容器名.push_back(elem)：在队尾插入元素elem。
容器名.pop_front()：删除队头的第一个元素。
容器名.pop_back()：删除队尾的第一个元素。
容器名.erase()：从双端队列容器中删除一个或几个元素。
容器名.clear()：删除双端队列容器中所有元素。
容器名.begin()：返回iterator或const_iterator，引用容器的第一个元素。
容器名.end()：返回iterator或const_iterator，引用容器的最后一个元素的后面一个元素。
(end()不指向容器内的任何一个存在的元素,指向最后一个元素的下一个元素)
容器名.rbegin()：返回reverse_iterator或const_reverse_iterator，引用容器的最后一个元素。
容器名.rend()：返回reverse_iterator或const_reverse_iterator，引用容器的第一个元素的前面一个元素。
 
stack(栈容器)，queue(队列容器) 
从思想上来看，双端队列容器deque是队列容器queue的一个衍生，但从实现上来看deque允许从头和尾进行增删改查的操作，可以作为先进后出的栈容器(stack)先进先出的队列容器(queue)的底层容器(事实上从实现来看就是带有deque残缺功能的一般容器)。
 
栈和队列中都没有迭代器的操作，即begin()，end()等，所以相比于双端队列容器deque，单从实现角度来看，以deque作为底层容器的栈容器和队列容器的操作要简单很多：
 
//stack容器的主要成员函数如下： 
容器名.empty()：判断栈容器是否为空。
容器名.size()：返回栈容器中实际元素个数。
容器名.push(elem)：元素elem进栈。
容器名.top()：返回栈顶元素。
容器名.pop()：元素出栈。
//queue容器的主要成员函数如下：
容器名.empty()：判断队列容器是否为空。
容器名.size()：返回队列容器中实际元素个数。
容器名.front()：返回队头元素。
容器名.back()：返回队尾元素。
容器名.push(elem)：元素elem进队。
容器名.pop()：元素出队。
 
list(链表容器) 
list是一个双链表类模板。可以从任何地方快速插入与删除(链表的性质)。它的每个结点之间通过指针链接，不能随机访问元素。
 
list在表的中间插入和删除元素比vector要快，对每个元素单独分配空间，所以不存在扩容的问题。
 
几种定义方式和vector容器的定义方式是完全相同的，这里就不再做赘述了。
 
主要成员函数也与vector容器的主要成员函数类，其中reverse()函数，unique()函数，sort()函数在vector容器中也是通用的，只是课本在介绍vector容器中没有提到(unique()函数常用于离散化操作)：
 
容器名.empty()：判断链表容器是否为空。
容器名.size()：返回链表容器中实际元素个数。
容器名.push_back()：在链表尾部插入元素。
容器名.pop_back()：删除链表容器的最后一个元素。
容器名.remove()：删除链表容器中所有指定值的元素。
容器名.remove_if(cmp)：删除链表容器中满足条件的元素。
容器名.erase()：从链表容器中删除一个或几个元素。
容器名.unique()：删除链表容器中相邻的重复元素。
容器名.clear()：删除链表容器中所有的元素。
容器名.insert(pos,elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定元素之前。
容器名.insert(pos,n,elem)：在pos位置插入n个元素elem。
容器名.insert(pos,x1,x2)：在迭代器pos处插入[x1,x2)的元素。
容器名.reverse()：反转链表。
容器名.sort()：对链表容器中的元素排序。
容器名.begin()：返回iterator或const_iterator，引用容器的第一个元素。
容器名.end()：返回iterator或const_iterator，引用容器的最后一个元素的后面一个元素。
(end()不指向容器内的任何一个存在的元素,指向最后一个元素的下一个元素)
容器名.rbegin()：返回reverse_iterator或const_reverse_iterator，引用容器的最后一个元素。
容器名.rend()：返回reverse_iterator或const_reverse_iterator，引用容器的第一个元素的前面一个元素。
 
set(集合容器)/multiset(多重集合容器) 
前面提到的几种容器内的数据按照线性次序的位置进行存储，也就是我们所说的顺序容器。接下来介绍的几种容器为关联容器，关联容器中的每个元素都有一个key(关键字)，通过key来存储和读取元素，而不是直接存储到连续的内存中。
 
set和multiset都是集合类模板，其元素值称为关键字。set中元素的关键字是唯一的，multiset中元素的关键字可以不唯一(但最多允许存在两个相同关键字的元素)，而且在默认情况下会对容器内的元素按关键字自动进行升序排列。
 
set对关键字的查找速度比较快，并且同时支持集合的交，差和并等一些集合上的运算。
 
set/multiset的成员函数如下，其中upper_bound，lower_bound作为二分搜索在排序后的vector中通用：
 
容器名.empty()：判断容器是否为空。
容器名.size()：返回容器中实际元素个数。
容器名.insert()：插入元素。
容器名.erase()：从容器删除一个或几个元素。
容器名.clear()：删除所有元素。
容器名.count(k)：返回容器中关键字k出现的次数。
(由于是集合类模板，count关键字返回的值要么为0要么为1)
find(k)：如果容器中存在关键字为k的元素，返回该元素的迭代器，否则返回end()值。
(find和count的区别在于一个判断是否存在，一个精确定位到元素的迭代器)
容器名.upper_bound()：返回一个迭代器，指向关键字大于k的第一个元素。
容器名.lower_bound()：返回一个迭代器，指向关键字不小于k的第一个元素。
(upper_bound()和lower_bound()都是封装好的搜索，属于有序表中较优的查找方式)
容器名.begin()：返回iterator或const_iterator，引用容器的第一个元素。
容器名.end()：返回iterator或const_iterator，引用容器的最后一个元素的后面一个元素。
(end()不指向容器内的任何一个存在的元素,指向最后一个元素的下一个元素)
容器名.rbegin()：返回reverse_iterator或const_reverse_iterator，引用容器的最后一个元素。
容器名.rend()：返回reverse_iterator或const_reverse_iterator，引用容器的第一个元素的前面一个元素。
 
map(映射容器)/multimap(多重映射容器) 
map和multimap都是映射类模板。容器中的数据都是以pair(一种常用但不常介绍的类)二元组(key,value)的形式进行存储和读取的。
 
其中key仍做关键字的作用，和set一样在容器中唯一(multimap允许关键字重复出现)且按照key的升序进行排列。value是与关键字key对应的值，相当于数学中建立了key值集合到value值集合的映射，在map中可以通过key的值快速找到与之对应的value。
 
map/multimap的主要成员函数如下：
 
容器名.empty()：判断容器是否为空。
容器名.size()：返回容器中实际元素个数。
容器名[key]：返回关键字为key的元素的引用，如果不存在这样的关键字，则以key作为关键字插入一个元素（不适合multimap）。
容器名.insert(elem)：插入一个元素elem并返回该元素的位置。
容器名.clear()：删除所有元素。
容器名.find()：在容器中查找元素，返回指向它的迭代器。
容器名.count()：容器中指定关键字的元素个数（map中只有1或者0）。
容器名.begin()：返回iterator或const_iterator，引用容器的第一个元素。
容器名.end()：返回iterator或const_iterator，引用容器的最后一个元素的后面一个元素。
(end()不指向容器内的任何一个存在的元素,指向最后一个元素的下一个元素)
容器名.rbegin()：返回reverse_iterator或const_reverse_iterator，引用容器的最后一个元素。
容器名.rend()：返回reverse_iterator或const_reverse_iterator，引用容器的第一个元素的前面一个元素。
 
其中insert函数和[]插入的方式有一定的区别：如果map中原本就有想要插入的key值，insert插入相同的key值被判定为无效，[]被判定为修改。
 
同样的，在用[]查找key时，也需要用find先判断是否存在这样的key，否则会出错。
 
set和map都是基于红黑树实现的容器，有关红黑树的具体内容详见上科大专栏的lecture 15.1。
 
priority_queue(优先队列容器) 
priority_queue是一个优先队列类模板，priority_queue允许任意顺序的插入元素以及访问和删除队首的元素，队首的元素为容器中优先级最高的元素。
 
priority_queue的底层实现本质上是complete heaps，complete heaps是heaps通过complete tree进行的优化，而complete tree用数组来实现较为方便，所以priority_queue作为适配器容器的底层容器为vector(另外堆的实现和功能上有很多细节，详情见上科大专栏的lecture 12和Fibonacci Heaps)。
 
priority_queue容器的成员函数如下：
 
容器名.empty()：判断优先队列容器是否为空。
容器名.size()：返回优先队列容器中实际元素个数。
容器名.push(elem)：元素elem进队。
容器名.top()：获取队头元素。
容器名.pop()：元素出队。
（另有decrease-key操作这里不多赘述） 
 
至于为什么set和map都有排序的功能，不用set和map来完成priority_queue容器，我的建议是去看上科大的课件和Fibonacci Heaps，算法设计的课本和数据结构的课表关于这方面都没有做介绍。
 
 
STL在算法设计中的应用 
存放主数据/临时数据 
算法设计重要步骤是设计数据的存储结构，除非特别指定，程序员可以采用STL中的容器存放主数据，选择何种容器不仅要考虑数据的类型，还有考虑数据的处理过程。
 
其实除了使用list能够方便使用链表和使用string来方便进行字符串的操作(string效率较低，在对效率较高的问题上谨慎使用)，最主要的就是vector比起普通数组在长度上不固定，能够在某些情况下减少空间开销的应用。
 
例 1.11 
有一段英文由若干单词组成，单词之间用一个空格分隔。编写程序提取其中的所有单词。
 
每个单词之间用空格分隔，于是我们可以将英文用string存储，用string的成员函数find来寻找空格，通过空格的位置和成员函数substr来截取单词存储到vector容器里(这里其实简单的string数组也可以)，主要的难点在于要去特殊处理最后一个单词(最后一个单词后面没有空格)。
 
#include
#include
#include
using namespace std;
//将字符串str的单词存入到words中 
void solve(string str,vector &words){ 
	string w;
    int i=0;//i作为前一个单词的最后一个字符的下标-1 
    int j=str.find(" ");//查找第一个空格
    while (j!=-1){//找到单词后循环	
		w=str.substr(i,j-i);//提取一个单词
		words.push_back(w);//单词添加到words中
		i=j+1;
		j=str.find(" ",i);//查找下一个空格,通过空格查找单词 
    }
    //处理最后一个单词 
    if (i	
		w=str.substr(i);	//提取最后一个单词
 		words.push_back(w);	//最后单词添加到words中
    }
}
int main(){
	//str为需要处理的字符串  
	string str="The following code computes the intersection of two arrays";
	vectorwords;//words作为存放string的vector容器,存放单词 
	solve(str,words);
	cout<<"所有的单词:"<::iterator it;
	for (it=words.begin();it!=words.end();++it) cout << "  " << *it << endl;
	return 0; 
}
 
存放临时数据也是处理数据，如果数据的处理分批次，且满足先进入容器的先处理或者先进入容器的后处理的原则，就可以考虑使用队列或者stack容器(Bellman-ford算法的优化——SPFA算法)，如果按照某个优先级的顺序分批次处理，可以使用priority_queue()(UCS)。
 
例 1.12 
设计一个算法，判断一个含有()，[]，{}三种类型括号的表达式中所有括号是否匹配。
 
经典的括号匹配问题，因为先进入容器的左半边括号内部包含的符号越多，所以后进行右半边的括号匹配，满足先进后出的处理顺序，用stack容器进行处理。
 
问题是老生常谈的这里不多赘述。
 
检测数据元素的唯一性 
用map来记录元素出现的次数来检验数据元素的唯一性(set更直接，但个人觉得set不是很好操作)。
 
例题 1.13 
设计一个算法判断字符串str中每个字符是否唯一。如："abc"的每个字符是唯一的，算法返回true；而"accb"的中字符’c’不是唯一的，算法返回false。
 
按照上面的逻辑处理，比较简单的问题。
 
//检测str中的所有字符是否唯一的
bool isUnique(string &str){  
	map mymap;//value值表示key值的字符出现多少次,用于检验唯一性 
    for (int i=0;i	
		mymap[str[i]]++;
		if (mymap[str[i]]>1) return false;
	}
    return true;
}
 
求多少对相反数 
有N个非零且各不相同的整数，请你编一个程序求出它们中有多少对相反数。
 
以整数的绝对值作为容器的key值，如果value值为2说明出现了一对相反数，统计容器内value值为2的pair数即可(课件上用了insert，个人觉得没有必要)。
 
数据的排序 
主要就是学习如何根据自己想要的规则通过sort对容器内的数据进行排序，内置的有greater和less两种规则(递增，递减)，这对于一些自定义的结构体是不通用的。
 
对于自定义的结构体解决的策略有两种：1.重载比较符号；2.自定义结构体的新的关系函数，传递关系函数按照关系函数进行排序。
 
两种方式的案例如下：
 
#include
#include
#include
#include
using namespace std;
//自定义的结构体如下 
struct Stud{  
	int no;
    string name;
    //构造函数
    Stud(int no1,string name1){no=no1; name=name1;}
    //重载＞＜符号,然后仍使用内置的关系函数进行排序 
   	bool operator<(const Stud &s)const{
		return s.no则按no递增排序   
    }
};
//自定义关系函数 
struct Cmp{  
	bool operator()(const Stud &s,const Stud &t)const{
		return s.name则按name递减排序
   	}
};
//用正向迭代器输出vector容器内的元素
void Disp(vector &myv){   
	vector::iterator it;
    for (it = myv.begin();it!=myv.end();it++) cout<no<<","<name<<"t";
    cout<  
	Stud a[]={Stud(2,"Mary"),Stud(1,"John"),Stud(5,"Smith")};
    int n=sizeof(a)/sizeof(a[0]);
    vector myv(a,a+n);
    cout<<"初始myv:    "; 
	Disp(myv);
	//重载运算符,仍使用内置的关系函数  
	sort(myv.begin(),myv.end());
    cout<<"按no递减排序:   "; 
	Disp(myv);	
	//自定义关系函数,使用自定义的关系函数 
    sort(myv.begin(),myv.end(),Cmp());  
    cout<<"按name递增排序: "; Disp(myv);
	return 0;
}
 
优先队列作为堆 
C++的priority_queue不提供decrease-key的操作(这一点对于一些算法而言是比较糟糕的，需要使用一些替代的处理方法)，优先队列作为堆和前面的排序一样主要问题就是当内置的数据类型无法满足自己的需求，对于自定义的数据类型，该如何进行一个排序。
 
事实上的处理策略和排序是一致的：1.重载比较关系(和排序不同的是，重载＜对应less的内置关系函数，重载＞则对应great而得内置关系函数，而排序重载一个＜就都可以对应)；2.自定义关系函数。
 
两种方式的案例如下：
 
#include
#include
#include
using namespace std;
//自定义结构体 
struct Stud{  
	int no; string name;
	//构造函数 
    Stud(int n,string na){no=n; name=na;}
	//重载<关系函数
    bool operator<(const Stud &s) const{return no关系函数
    bool operator>(const Stud &s) const{return no>s.no;}
};
//自定义关系函数 
struct StudCmp{   
	bool operator()(const Stud &s,const Stud &t) const{
		return s.name  
	Stud a[]={Stud(2,"Mary"),Stud(1,"John"),Stud(5,"Smith")};
   	int n=sizeof(a)/sizeof(a[0]);
    //(1)使用重载后的<关系函数来定义less关系的优先队列pq1
   	priority_queue pq1(a,a+n);
   	cout<<"pq1出队顺序: ";
   	//按no递减输出
   	//优先队列由于是按照complete heaps的原理实现的,除队首之外的元素是不得访问且不是按照严格顺序排列的
	//如果想要输出,需要一个一个元素的出队 
   	while (!pq1.empty()){	
	   	cout<<"["<关系函数来定义less,greater关系的优先队列pq1
	//这里声明了底层容器为deque 
    priority_queue,greater > pq2(a,a+n);
    cout<<"pq2出队顺序: ";
	//按no递增输出
    while (!pq2.empty()){	
	   	cout<<"["<,StudCmp > pq3(a,a+n);
    cout<<"pq3出队顺序: ";
	//按name递减输出
    while (!pq3.empty()){	
	   	cout<<"["<