STL(Standard Template Library)，即标准模板库。下面是紫书中的几个相关例题，记录学习一下。

1. 排序与检索

algorithm头文件中的sort可以给任意对象排序，包括内置类型和自定义类型，前提是类型定义了“<”运算符。排序之后可以用lower_bound查找大于或等于x的第一个位置。待排序/查找的元素可以放在数组里，也可以放在vector里。还有一个unique函数可以删除有序数组中的重复元素。

例题5-1 大理石在哪儿

现有N个大理石，每个大理石上写了一个非负整数。首先把各数从小到大排序，然后回答Q个问题。每个问题问，是否有一个大理石写着某个整数x，如果是，
还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1~N。（在样例中，为了节约篇幅，所有大理石上的数合并到一行，所有问题也合并到一行）。

样例输入：
4 1
2 3 5 1
5
5 2
1 3 3 3 1
2 3

样例输出：
CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3

不知道是我理解能力的问题，还是题目本身表达的就不清楚，半天没看懂什么意思QAQ，后来看样例输入才明白，害，，，大致意思就是输入一组数和当前属于的循环次数，然后排序，再查找输入的要找的数的位置。使用algorithm头文件中的sort和lower_bound就可以完成了。lower_bound的作用是查找“大于或等于x的第一个位置”。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=10000;

int main(){
	int n,q,x,a[maxn],kase=0;
	while(scanf("%d%d",&n,&q)==2 && n){
		printf("CASE# %dn",++kase);
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		sort(a,a+n);//排序
		while(q--){
			scanf("%d",&x);
			int p=lower_bound(a,a+n,x)-a;//在已排序数组a中寻找x
			if(a[p]==x)
				printf("%d found at %dn",x,p+1);
			else
				printf("%d not foundn",x); 
		} 
	}
	return 0;
}

2. 不定长数组：vector

vector就是一个不定长数组。例如，若a是一个vector，可以用a.size()读取它的大小，a.resize()改变大小，a.push_back()向尾部添加元素，a.pop_back()删除最后一个元素。
vector是一个模板类，所以需要用vector<int> a 或者vector<double> a 这样的方式来声明一个vector。vector<int>是一个类似于int a[] 的整数数组，而vector<string>就是一个类似string a[] 的字符串数组。vector可以直接赋值，还可以作为函数的参数或者返回值，而无须像传递数组那样另外用一个变量指定元素个数。

例题5-2 木块问题

从左到右有n个木块，编号为0~n-1，要求模拟以下4种操作（下面的a和b都是木块编号）。

 - move a onto b：把a和b上方的木块全部归位，然后把a螺在b上面。
 - move a over b：把a上方的木块全部归位，然后把a放在b所在木块堆的顶部。
 - pile a onto b：把b上方的木块全部归位，然后把a及上面的木块整体螺在b上面。
 - pile a over b：把a及上面的木块整体螺在b所在木块堆的顶部。遇到quit时终止一组数据。a和b在同一堆的指合是非法指合，应当忽略。

分析：
每个木块堆的高度不确定，所以用vector来保存很合适；而木块堆的个数不超过n，所以用一个数组来存就好了。
代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
const int maxn=30;
int n;
vector<int> pile[maxn];//每个pile[i]是一个vector 

//找木块a所在的pile和height，以引用的形式返回调用者 
void find_block(int a,int& p,int& h){
	for(p=0;p<n;p++)
		for(h=0;h<pile[p].size();h++)
			if(pile[p][h]==a) return ;
}

//把第p堆高度为h的木块上方法所有木块移回原位
void clear_above(int p,int h){
	for(int i=h+1;i<pile[p].size();i++){
		int b=pile[p][i];
		pile[b].push_back(b);//把木块b放回原位 
	}
	pile[p].resize(h+1);//pile只应保留下标0~h的元素 
} 

//把第p堆高度为h及其上方的木块整体移动到p2堆的顶部
void pile_onto(int p,int h,int p2){
	for(int i=h;i<pile[p].size();i++)
		pile[p2].push_back(pile[p][i]);
	pile[p].resize(h);
} 

void print(){
	for(int i=0;i<n;i++){
		printf("%d:",i);
		for(int j=0;j<pile[i].size();j++)
			printf(" %d",pile[i][j]);
		printf("n");
	}
}
int main(){
	int a,b;
	cin>>n;
	string s1,s2;
	for(int i=0;i<n;i++)
		pile[i].push_back(i);
	while(cin>>s1>>a>>s2>>b){
		int pa,pb,ha,hb;
		find_block(a,pa,ha);
		find_block(b,pb,hb);
		if(pa==pb) continue;//非法指令
		if(s2=="onto") clear_above(pb,hb);
		if(s1=="move") clear_above(pa,ha);
		pile_onto(pa,ha,hb); 
	}
	print();
	return 0;
}

3. 集合：set

集合与映射也是两个常用的容器。set就是数学上的集合——每个元素最多只出现一次，和sort一样，自定义类型也可以构造set，但同样必须定义“<”运算符。

例题5-3 安迪的第一个字典

输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出。单词不区分大小写。
样例输入：
Adventures in Disneyland 
Two blondes were going to Disneyland when they came to a fork in the road.The sign read:"Disneyland Left."
So they went home.

样例输出（为了节约篇幅只保留前5行）：
a 
adventures 
blondes 
came 
disneyland

分析：本题没有太多的技巧，只是为了展示set的用法：由于string已经定义了“小于”运算符，直接使用set保存单词集合即可。注意，输入时把所有非字母的字符变成空格，然后利用stringstream得到各个单词。

#include <cstring>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;

set<string> dict;//string集合 

int main(){
	string s,buf;
	while(cin>>s){
		for(int i=0;i<s.length();i++)
			if(isalpha(s[i])) s[i]=tolower(s[i]);
			else s[i]=' ';
		stringstream ss(s);
		while(ss>>buf) dict.insert(buf);
	}
	for(set<string>::iterator it=dict.begin();it!=dict.end();++it)
		cout<<*it<<"n";
	return 0;
}

上面的代码用到了set中元素已经从小到大排好序的性质，用一个for循环即可从小到大遍历所有元素。

4. 映射：map

map就是从键（key）到值（value）的映射。因为重载了 [] 运算符，map像是数组的“高级版”，也称“关联数组”。例如可以用一个map<string,int> month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。

例题5-4 反片语

输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在
输出时应保留输入中的大小写，按字典序进行排列（所有大写字母在所有小写字母的前面）。
样例输入：
ladder came tape soon leader acme RIDE lone Dreis peat 
ScAIE orb eye Rides dealer NotE derail LaCeS drled 
noel dire Disk mace Rob dries
#
样例输出：
Disk
NotE 
derail
drled
eye
ladder
soon

分析：
把每个单词标准化，即全部转化为小写字母再进行排序，然后再放到map中进行统计。

#include <cstring>
#include <vector>
#include <iostream>
#include <cctype>
#include <map>
#include <algorithm>
using namespace std;

map<string,int> cnt;
vector<string> words;

//将单词s进行“标准化”
string repr(const string& s){
	string ans=s;
	for(int i=0;i<ans.length();i++)
		ans[i]=tolower(ans[i]);
	sort(ans.begin(),ans.end());
	return ans;
} 

int main(){
	int n=0;
	string s;
	while(cin>>s){
		if(s[0]=='#') break;
		words.push_back(s);
		string r=repr(s);
		if(!cnt.count(r)) cnt[r]=0;
		cnt[r]++;
	}
	vector<string> ans;
	for(int i=0;i<words.size();i++)
		if(cnt[repr(words[i])]==i)
			ans.push_back(words[i]);
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++)
		cout<<ans[i]<<endl;
	return 0;
}

5. 栈、队列和优先队列

STL还提供3种特殊的数据结构：栈、队列与优先队列。

栈

所谓栈，就是符合“后进先出”规则的数据结构，有PUSH和POP两种操作。其中PUSH把元素压入“栈顶”，而POP从栈顶把元素“弹出”。

STL的栈定义在头文件<stack>中，可以用stack<int> s方式声明一个栈，用push()和pop()实现元素的入栈和出栈操作，top()取栈顶元素（但不删除元素）。

例题5-5 集合栈计算机

有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作。

• PUSH：空集“{}”入栈。
• DUP：把当前栈顶元素复制一份后再入栈。
• UNION：出栈两个集合，然后把二者的并集入栈。
• INTERSECT：出栈两个集合，然后把二者的交集入栈。
• ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈。

每次操作后，输出栈顶集合的大小（即元素个数）。例如，栈顶元素是A={}，
{{3}}，下一个元素是B={}，{{0}}}，则：

• UNION操作捋得到（}，{0}，{{{}}}}，输出3。
• INTERSECT操作捋得到{}}，输出1。
• ADD操作捋得到（}，{{}}}，{}，{{3}}}，输出3。

输入不超过2000个操作，并且保证操作均能顺利进行（不需要对空栈执行出栈操作）。

【分析】
本题的集合并不是简单的整数集合或者字符串集合，而是集合的集合。为了方便起见，此处为每个不同的集合分配一个唯一的ID，则每个集合都可以表示成所包含元素的ID集合，这样就可以用STL的set<int>来表示了，而整个栈则是一个stack<int>。

typedef set<int> Set;
map<Set,int> IDcache;//把集合映射成ID 
vector<Set> Setcache;//根据ID取集合

//查找给定集合x的ID，如果找不到，分配一个新ID
int ID(Set x){
	if(IDcache.count(x))
		return IDcache[x];
	Setcache.push_back(x);//添加新集合
	return IDcache[x]=Setcache.size()-1; 
} 

对任意集合s（类型是上面定义的Set），IDcache[s]就是它的ID，而Setcache[IDcache[s]]就是s 本身。下面的ALL和INS是两个宏：

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

分别表示“所有的内容”以及“插入迭代器”，具体作用可以从代码中推断出来。主程序如下，请读者注意STL内置的集合操作（如set_union和set_intersection）

stack<int> s;//题目中的栈
int n;
cin>>n;
for(int i=0;i<n;i++){
	string op;
	cin>>op;
	if(op[0]=='P') s.push(ID(Set()));//PUSH
	else if(op[0]=='D') s.push(s.top());//DUP
	else{
		Set x1=Setcache[s.top()];s.pop();
		Set x2=Setcache[s.top()];s.pop();
		Set x;
		if(op[0]=='U') set_union(ALL(x1),ALL(x2),INS(x));//UNION
		if(op[0]=='I') set_intersection(ALL(x1),ALL(x2),INS(x));//INTERSECT
		if(op[0]=='A'){//ADD
			x=x2;x.insert(ID(x1));
		} 
		s.push(ID(x));
	}
	cout<<Setcache[s.top()].size()<<endl;
} 

队列

队列是符合“先进先出”原则的“公平队列”，如下图：

STL队列定义在头文件<queue>中，可以用queue<int>s方式声明一个队列，用push()和pop()进行元素的入队和出队操作，front()取队首元素（但不删除）。

团体队列

有个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，则他会排到长队的队尾。
输入每个团队中所有队员的编号，要求支持如下3种指合（前两种指合可以穿插进行）。

• ENQUEUE x：编号为x的人进入长
• DEQUEUE：长队的队首出队。
• STOP：停止模拟。

对于每个DEQUEUE指合，输出出队的人的编号。
【分析】
本题有两个队列：每个团队有一个队列，而团队整体又形成一个队列。例如，有3个团队1，2，3，队员集合分别为{101，102，103，104}、{201，202}和{301，302，303}，当前长队为{301，303，103，101，102，201}，则3个团队的队列分别为{103，101，102}、
{201}和（301，303}，团队整体的队列为{3，1，2}。代码如下：

#include <cstdio>
#include <queue>
#include <map>
using namespace std;

const int maxt=1000+10;

int main(){
	int t,kase=0;
	while(scanf("%d",&t)==1&&t){
		printf("Scenario #%dn",++kase);
		
		//记录所有人的团队编号 
		map<int,int> team;//team[x]表示编号为x的人所在的团队编号 
		for(int i=0;i<t;i++){
			int n,x;
			scanf("%d",&n);
			while(n--){
				scanf("%d",&x);
				team[x]=i;
			} 
		}
		
		//模拟
		queue<int> q,q2[maxt];//q是团队的队列，q2[i]是团队i成员的队列
		for(;;){
			int x;
			char cmd[10];
			scanf("%s",cmd);
			if(cmd[0]=='S') break;
			else if(cmd[0]=='D'){
				int t=q.front();
				printf("%dn",q2[t].front());q2[t].pop();
				if(q2[t].empty()) q.pop();//团体t全体出队列 
			}
			else if(cmd[0]=='E'){
				scanf("%d",&x);
				int t=team[x];
				if(q2[t].empty()) q.push(t);//团队t进入队列
				q2[t].push(x); 
			}
		} 
		printf("n"); 
	}
	return 0;
} 

优先队列

优先队列是一种抽象数据类型（Abstract Data Type，ADT），行为有点像队列，但先出队列的元素是队列中优先级最高的元素，这样就可以允许类似于“急诊病人插队”这样的事情发生。

STL的优先队列也定义在头文件<queue>里，用priority_queue<int>pq来声明。这个pq是一个“越小的整数优先级越低的优先队列”。由于出队元素并不是最先进队的元素，出队 方法由queue的front()变为了top()。

自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只要能比较大小即可，所以，只要元素定义了“小于”运算符，就可以使用优先队列。在一些特殊的情况下，需要使用自定义方法比较优先级。例如，要实现一个“个位数大的整数优先级反而小”的优先队列，可以定义一个结构体cmp，重载“( )”运算符，使其看上去像一个函数，然后用priority_queue<int,vector<int>,cmp>pq的方式定义。下面是这个cmp的定义：

struct cmp{
	bool operator() (const int a,const int b){//a的优先级比b小时返回true 
		return a%10 > b%10;
	}
};

对于一些常见的优先队列，STL提供了更为简单的定义方法，例如，“越小的整数优先级越大的优先队列”可以写成priority_queue<int，vector<int>，greater<int> >pq。注意，最后两个“>”符号不要写在一起，否则会被很多（但不是所有）编译器误认为是“>>”运算符。

STL的queue头文件提供了优先队列，用priority_queue<int>s方式定义，用push（）和pop（）进行元素的入队和出队操作，top（）取队首元素（但不删除）。

丑数

丑数是指不能被2，3，5以外的其他素数整除的数。把丑数从小到大排列起来，结果如下：
1，2，3，4，5，6，8，9，10，12，15…
求第1500个丑数。

【分析】
本题的实现方法有很多种，这里仅提供一种，即从小到大生成各个丑数。最小的丑数是1，而对于任意丑数x，2x、3x和5x也都是丑数。这样，就可以用一个优先队列保存所有已生成的丑数，每次取出最小的丑数，生成3个新的数。唯一需要注意的是，同一个丑数有多种生成方式，所以需要判断一个丑数是否已经生成过。代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int coeff[3]={2,3,5};

int main(){
	priority_queue<LL, vector<LL>, greater<LL> >pq;
	set<LL> s;
	pq.push(1);
	s.insert(1);
	for(int i=1;;i++){
		LL x=pq.top();pq.pop();
		if(i==1500){
			cout<<"The 1500'th ugly number is "<<x<<".n";
			break;
		}
		for(int j=0;j<3;j++){
			LL x2=x*coeff[j];
			if(!s.count(x2)){
				s.insert(x2);pq.push(x2);
			}
		}
	}
	return 0;
}
//The 1500'th ugly number is 859963392.

测试STL

库也是需要测试的，一方面是因为库是人写的，也有可能有bug，另一方面是因为测试之后能更好地了解库的用法和优缺点。

测试的方法大同小异，下面只以sort为例进行介绍。首先，写一个简单的测试程序：

int a[]={3,2,4};
sort(a,a+3);
printf("%d%d%d",a[0],a[1],a[2]);

输出为234，是一个令人满意的结果。但这样就够了吗？不！测试程序太简单，说明不了问题。应该写一个更加通用的程序，随机生成很多整数，然后排序。

先来看看随机数发生器。核心函数是cstdlib中的rand()，它生成一个闭区间[0, RAND_MAX]内的均匀随机整数（均匀的含义是：该区间内每个整数被随机获取的概率相同），其中RAND_MAX至少为32767（2¹⁵-1），在不同的环境下值可能不同。严格的说，这里的随机数是伪随机数，因为她也是由数学公式计算出来的，不过在算法领域，多数情况下把它当作真正的随机数。

如何产生[0，n]之间的整数呢？很多人喜欢用rand（）%n产生区间[0，n-1]内的一个随机整数，姑且不论这样产生的整数是否仍然分布均匀，只要n大于RAND_MAX，此法就不能得到期望的结果。由于RAND_MAX很有可能只有32767这么小，在使用此法时应当小心。另一个方法是执行rand（）之后先除以RAND_MAX，得到[0，1]之间的随机实数，扩大n倍后四舍五入，得到[0，n]之间的均匀整数。这样，在n很大时“精度”不好（好比把小图放大后会看到“锯齿”），但对于普通的应用，这样做已经可以满足要求了。

cstdlib中的rand（）可生成闭区间[0，RAND_MAX]内均匀分布的随机整数，其中RAND_MAX至少为32767。如果要生成更大的随机整数，在精度要求不太高的情况下可以用rand（）的结果“放大“得到。

需要随机数的程序在最开始时一般会执行一次srand（time（NULL）），目的是初始化“随机数种子”。简单地说，种子是伪随机数计算的依据。种子相同，计算出来的“随机数”序列总是相同。如果不调用srand而直接使用rand（），相当于调用过一次srand（1），因此程序每次执行时，捋得到同一套随机数。

不要在同一个程序每次生成随机数之前都重新调用一次srand。有的初学者抱怨“rand（）产生的随机数根本不随机，每次都相同”，就是因为误解了srand的作用。再次强调，请只在程序开头调用一次srand，而不要在同一个程序中多次调用。

可以用cstdlib中的srand函数初始化随机数种子。如果需要程序每次执行时使用一个不同的种子，可以用ctime中的time（NULL）为参数调用srand。一般来说，只在程序执行的开头调用一次srand。

“同一套随机数”可能是好事也可能是坏事。例如，若要反复测试程序对不同随机数据的响应，需要每次得到的随机数不同。一个简单的方法是使用当前时间time（NULL）（在ctime中）作为参数调用srand。由于时间是不断变化的，每次运行时，一般会得到一套不同的随机数。之所以说“一般会”，是因为time函数返回的是自UTC时间1970年1月1日0点以来经过的“秒数”，因此每秒才变化一次。如果你的程序是由操作系统自动批量执行的，可能因为每次运行的间隔时间过短，导致在相邻若干次执行时time的返回值全部相同。一个解决办法是在测试程序的主函数中设置一个循环，做足够多次测试后再退出。

另一方面，如果发现某程序对于一组随机数据报错，就需要在调试时“重现”这组数据。这时，“每次相同的随机序列”就显得十分重要了。不同的编译器计算随机数的方法可能不同。如果是不同编译器编译出来的程序，即使是用相同的参数调用srand（），也可能得到不同的随机序列。

下面可以编写随机程序了：

void fill_random_int(vector<int>& v,int cnt){
	v.clear();
	for(int i=0;i<cnt;i++)
		v.push_back(rand());
}

注意srand函数是在主程序开始时调用，而不是每次测试时调用。参数是vector的引用。为什么不把这个v作为返回值，而要写到参数里呢？答案是：避免不必要的值被复制。
如果这样写：

vector<int> fill_random_int(int cnt){
	vector<int> v;
	for(int i=0;i<cnt;i++)
		v.push_back(rand());
	return v;
}

实际上函数内的局部变量v中的元素需要逐个复制给调用者。而用传引用的方式调用，就避免了这些复制过程。

提示：把vector作为参数或者返回值时，应尽量改成用引用方式传递参数，以避免不必要的值被复制。

这两个函数可以同时存在于一份代码中，因为C++支持函数重载，即函数名相同但参数不同的两个函数可以同时存在。这样，编译器可以根据函数调用时参数类型的不同判断应该调用哪个函数。如果两个函数的参数相同10只是返回值不同，是不能重载的。
提示：C++支持函数重载，但函数的参数类型必须不同（不能只有返回值类型不同）。

写完了随机数发生器之后，就可以正式测试sort函数了，程序如下：

void test_sort(vector<int>& v){
	sort(v.begin(),v.end());
	for(int i=0;i<v.size()-1;i++)
		assert(v[i]<=v[i+1]);
}

新内容是上面的asert宏，其用法是assert（表达式），作用是：当表达式为真时无变化，但当表达式为假时强行终止程序，并且给出错误提示。当然，上述程序也可以写成if（vi]>v[i+1]）{printf（"Error:v[i]>v[i+1]！n"）；abort（）；}，但assert更简洁，而且可以知道是由代码中的哪一行引起的，所以在测试时常常使用它。

和刚才一样，给参数v加上引用符的原因是为了避免vector复制，但函数执行完毕之后v会被sort改变。如果调用者不希望这个v被改变，就应该去掉“&”符号（即参数改成vector<int>v），改回传值的方式。

下面是主程序，请注意srand函数的调用位置。顺便我们还测试了sort的时间效率，发现给10⁶个整数排序几乎不需要时间。

int main(){
	vector<int> v;
	fill_random_int(v,1000000);
	test_sort(v);
	return 0;
}

vector、set和map都很快，其中vector的速度接近数组（但仍有差距），而set和map的速度也远远超过了“用一个vector保存所有值，然后逐个元素进行查找”时的速度。set和map每次插入、查找和删除时间和元素个数的对数呈线性关系，其具体含义将在第8章中详细讨论。尽管如此，在一些对时间要求非常高的题目中，STL有时会成为性能瓶颈，请读者注意。

最后

以上就是酷酷花卷为你收集整理的紫书C++STL初步例题笔记1. 排序与检索2. 不定长数组：vector3. 集合：set4. 映射：map5. 栈、队列和优先队列测试STL的全部内容，希望文章能够帮你解决紫书C++STL初步例题笔记1. 排序与检索2. 不定长数组：vector3. 集合：set4. 映射：map5. 栈、队列和优先队列测试STL所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。