C++ STL快速上手

最近在准备一个机试，就火速入门了C++ STL，来快速解决一些经典问题。在此做简单记录，目的是今后能用这篇文章快速捡起STL的最基本用法。笔记几乎全部来自《算法笔记》，题目来自codeup和pat。

1 vector

变长数组

1.1 定义

#include<vector>
using namespace std;
vector<int> name;
vector<node> name;	// 节点数组
vector<vector<int> > name;	//二维数组
vector<int> vi[100];	//vector数组，长度100，每个vector变长

1.2 元素访问

vector可以用下标和迭代器访问。

vector<int> vname;
vname.push_back(1);
vname.push_back(1);
vname.push_back(1);
vname.push_back(1);

int x = vname[0];	// 下标访问

vector<int>::iterator it = vname.begin();
int x = *it;	// 迭代器访问
int y = *(it+3);

在常用STL容器里，只有在vector和string中，允许使用 name.begin()+3 这种迭代器加整数的访问方式。

1.3 常用函数

push_back(x)：容器尾插入元素
pop_back()：容器尾部移除元素
size()
clear()
insert(it, x)：在迭代器处插入元素
erase(it)：删除迭代器处元素
erase(first, last)：删除[first, last)元素

1.4 vector常见用途

代替数组
用邻接表存储图

2 set

自动排序、不含重复元素的容器

2.1 定义

#include<set>
using namespace std;
set<int> name;
set<node> name;
set<int> a[100];	//100个set容器组成的数组

2.2 元素访问

与vector不同，set只能用迭代器访问。

set<int> name;
set.insert(3);

set<int>::iterator it = name.begin();
int x = *it;	// 迭代器访问

2.3 常用函数

insert(x)：插入元素
find(value)：返回set中对应值为value的迭代器
size()
clear()
erase(it)：删除迭代器处元素
erase(value)：删除值为value的元素
erase(first, last)：删除[first, last)内所有元素

2.4 set常见用途

自动去重并按升序排序

3 string

字符串

3.1 定义

#include<set>
using namespace std;
string str1;
string str2 = "abc";

3.2 元素访问

string容器可以用下标或迭代器访问。

string str = "abcd";
for(int i=0;i<str.length();i++){
	c = str[i];	// 下标访问
}
for(string::iterator it = str.begin();it!=str.end();it++){
	c = *it;	//迭代器访问。一般用不到，但erase()和insert()要求以迭代器作为参数。
}

输出方式

// 读入和输出整个字符串，只能用cin和cout
cin>>str;
cout<<str;
// c_str()将字符串转换成字符数组，用于printf输出
printf("%s", str.c_str());

3.3 常用函数

加法运算符：+ 和 +=
比较运算符：=、!=、<、>=等。”aa”<”aaa”，”b”>”a”
size()或length()
clear()
insert(pos, string)：在pos位置插入string，pos是下标
insert(it, it2, it3)：把字符串[it2, it3)插入到it位置
erase(it)：删除迭代器处字符
erase(first, last)：删除[first, last)内所有字符
erase(pos, length)：删除pos开始length个字符
substr(pos, len)：返回从pos开始length长度的子串
find(str)：如果str是字符串的子串，返回其第一次出现的位置。如果不是子串，返回string::npos。
string::npos:作为find函数失配时的返回值
replace(pos, len, str2)：从pos位置开始len长度的子串替换为str2
replace(it1, it2, str2)：[it1, it2)子串替换为str2

4 map

映射

4.1 定义

#include<map>
using namespace std;
map<string, int> mp;	// string到int的映射
map<set<int>, string> mp;	// set到string的映射

4.2 元素访问

用下标访问map，可以参考数组（int到int的映射）的访问的格式。

map<char, int> mp;
mp['c'] = 20;
c = mp['c'];	// 用下标访问

用迭代器访问map，通过一个it访问键和值两个元素。it->first访问键，it->second访问值。

map<char, int> mp;
mp['b'] = 120;
mp['a'] = 100;
mp['c'] = 140;
for(map<char, int>::iterator it = mp.begin(); it!= mp.end(); it++){
	printf("%c %d\n",it->first, it->second);
}

输出结果：

a 100
b 120
c 140
map内部会以键值从小到大自动排序。map和set内部都是使用红黑树实现的。

4.3 常用函数

find(key)：返回键为key的迭代器 mp.find('a')
查找：if(mp.find(key)!=mp.end())
size()
clear()
erase(it)：删除迭代器处元素
erase(key)：删除值key为键的元素
erase(first, last)：删除[first, last)内所有元素

4.4 map常见用途

需要建立映射的场合
判断大整数或其他类型数据是否存在，可以把map当成bool数组使用

5 queue

队列

5.1 定义

#include<queue>
using namespace std;
queue<int> name;

5.2 元素访问

只能通过front()来访问队首元素，或者back()访问队尾元素。

queue<int> q;
q.push(1);
q.push(2);
q.push(3);
printf("%d %d", q.front(), q.back());

输出结果

1 3

比较好记：谁先来排队，谁就站在队头。

5.3 常用函数

push(x)：x入队
front(), back()：返回队首和队尾元素
pop()：队首元素出队
empty()：检测是否为空
size()

5.4 queue常见用途

广度优先搜索
注意：使用front()和pop()函数前，先用empty()判断非空。

6 priority_queue

内部按照优先级排序的队列

6.1 定义

#include<queue>
using namespace std;
priority_queue<typename> name;

6.2 元素访问

优先队列没有front()函数和back()函数，只能通过top()函数访问队首元素（也可以称为堆顶元素），也就是优先级最高的元素。

printf("%d", name.top());

6.3 常用函数

name.push(x);将x入队，复杂度O(logN)
name.pop();队首元素出队，复杂度O(logN)
typename x = name.top();获得队首元素，复杂度O(1)
name.empty();
name.size()

6.4 元素优先级设置

6.4.1 基本数据类型的优先级设置

对于int型、double型、char型，优先队列的默认设置是数字越大优先级越高。

也可以在定义过程中设置优先队列的优先级:

priority_queue<int, vector<int>, greater<int> > pq;

其中vector<int>填写的是来承载底层数据结构heap的容器；第三个参数greater<int>则是对第一个参数的比较类，less<int>表示数字大的优先级大，greater<int>表示数字小的优先级大。

6.4.2 结构体的优先级设置

struct Student{
    string name;
    int score;
    friend bool operator < (Student s1, Student s2){
        return s1.score < s2.score;
    }
};

定义友元函数，重载“<”运算符（重载大于号会编译错误，其他符号可以由小于号代替，即s1 > s2等价于判断s2 < s1，s1 == s2等价于判断!(s1 < s2)&&!(s2 < s1))。

函数内部“return s1.score < s2.score”，重载后小于号还是小于号的作用。此时Student类型的优先队列，内部是分数高的学生优先级高。

priority_queue<Student> pq;

同理，如果想要低分优先级高，把return中的小于号改为大于号即可。

6.4.3 与sort()的比较

优先队列的重载和排序函数类似，都是由两个变量作为参数，return了true或false作为大小关系。

效果上，大小规则是相反的。在sort()中，如果return s1.score>s2.score，是按照分数由大到小排列；在优先队列中，则是把小的分数元素放到队首。原因在于：优先队列默认规则是大的数优先级高，重载小于号为相反（s1.score>s2.score），只是把默认的规则反向了一下。

有没有办法跟sort()中的cmp函数那样写在结构体外面呢?

struct Student{
    string name;
    int score;
};
struct cmp{
    bool operator () (Student s1, Student s2){
        return s1.score > s2.score;
    }
};

在这种情况下，使用第二种定义方法定义优先队列：

priority_queue<Student, vector<Student>, cmp> pq;

即便是基本数据类型或者其他STL容器（如set），也可以通过以上方法定义优先级。

6.4.4 引用

最后，如果结构体内的数据较为庞大（例如出现了数组、字符串），可以使用引用来提高效率。

struct Student{
    string name;
    int score;
    friend bool operator < (const Student &s1, const Student &s2){
        return s1.score > s2.score;
    }
};
priority_queue<Student> pq;

或

struct Student{
    string name;
    int score;
};
struct cmp{
    bool operator () (const Student &s1, const Student &s2){
        return s1.score > s2.score;
    }
};
priority_queue<Student, vector<Student>, cmp> pq;

6.4.5 priority_queue常见用途

解决一些贪心问题
对Dijkstra算法进行优化（优先队列本质是堆）。
注意：使用top()前必须用empty()判断队列非空。

7 stack

后进先出的STL容器

7.1 定义

#include<stack>
using namespace std;
stack<int> name;

7.2 元素访问

栈只能通过top()函数访问栈顶元素。

printf("%d", name.top());

7.3 常用函数

name.push(x);将x入栈，复杂度O(1)
name.pop();栈顶元素出栈，复杂度O(1)
typename x = name.top();获得队首元素，复杂度O(1)
name.empty();
name.size()

7.4 stack常见用途

解决递归问题

7.5 练习-括号匹配

#include<cstdio>
#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main(){
	int n;
	scanf("%d",&n);
	getchar();
	string s;
	stack<char> st;
	while(n--){
		getline(cin,s);
		int len=s.size();
		bool flag=true;
		for(int i=0;i<len;i++){
			if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
				st.push(s[i]);
			}
			else if(s[i]==')' || s[i]==']' || s[i]=='}'){
				if(st.empty()==true){
					flag=false;	//单独的后括号 
					break;
				}
				char c = st.top();	//pop()是void类型，需要用top()返回栈顶元素 
				st.pop();
				if(c=='['&&s[i]==']' || c=='('&&s[i]==')' || c=='{'&&s[i]=='}'){
					continue;
				}
				else{
					flag=false;	//不匹配 
					break;
				}
			}
		}
		if(flag==true&&st.empty()==true){
			printf("yes\n");
		}
		else{
			printf("no\n");
		}
		while(st.empty()!=true){
			st.pop();
		}
		
	}
	return 0;
}
/*
有一种更好的方法：
使用map创建char到int的对应关系，
通过两个括号对应的int相加是否等于某一定值，
判断两个括号是否匹配。
如：
map<char> list;
list中依次存储：{ 1, ( 2, [ 3, ] 4, ) 5, } 6
判断相加是否为7
*/

8 pair

可以看作一个内部有两个元素的结构体

8.1 定义

#include<utility>
using namespace std;
pair<typename1, typename2> name;

由于map内部实现涉及pair，因此添加map头文件后会自动添加utility头文件。

在定义时初始化，如：
pair<string, int> p("str", 100);

在代码中临时构建一个pair，有以下两种方法：

p = pair<string, int>("str", 100)
p = make_pair("str", 100)

8.2 元素访问

pair中只有两个元素，分别是first和second。按正常结构体的方式访问即可。

pair<string, int> p;
p.first = "this is a pair";
p.second =  10;

p = make_pair("this is a pair", 10);

p = pair<string, int>("this is a pair", 10);

cout<<p.first<<' '<<p.second<<endl;

8.3 常用函数

比较操作数。先比较first大小，如果相同再比较second大小。

p1 = pair<int, int>(1,3);
p2 = pair<int, int>(1,2);
if(p1 >= p2){}
else if(p1 < p2){}

8.4 pair常见用途

用来代替二元结构体。不用自己写构造函数了。

作为map的键值对进行插入、迭代等操作。如：

#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
	map<string, int> mp;
	mp.insert(make_pair("this is a pair", 100));
	mp.insert(pair<string, int>("another pair", 200));
	for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
		cout << it->first << ' ' << it->second << endl;
	}
}

注意，用迭代器操作是it->first，用实体操作是p.first。可以把迭代器想成指针。

9 algorithm头文件下的常用函数

需要添加using namespace std;

9.1 max()、min()、abs()

max(x, y)和min(x, y)

x和y可以是浮点数，但类型必须相同。

abs(x)，x为整形。浮点数的绝对值使用cmath头文件下的fabs()函数。

9.2 swap()

swap(x, y)，交换x和y的值。

9.3 reverse()

reverse(it1, it2)可以将数组指针在[it1, it2)之间的元素或容器的迭代器在[it1, it2)范围内的元素进行反转。

例一：

int a[10] = { 1, 2, 3, 4, 5, 6 };
reverse(a, a+4);
for(int i=0;i<6;i++) printf("%d ",a[i]);

输出结果：

4 3 2 1 5 6

例二：

string str = "abcdefghi";
reverse(str.begin()+2, str.begin()+6);
printf("%s",str.c_str());

输出结果：

abfedcghi

9.4 next_permutation()

next_permutation()给出一个序列在全排列中的下一个序列。

int a[3] = {1, 2, 3};
do{
	printf("%d %d %d\n", a[0], a[1], a[2]);
}while(next_permutation(a, a+3));

输出结果：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

9.5 fill()

fill()可以把数组或容器中的某一段区间赋某个相同的值。和memset不同，这里的赋值可以是数组类型对应范围中的任意值。

参数写法依然是左闭右开。

int a[10] = { 1, 2, 3, 4, 5, 6 };
fill(a, a+4, 100);
for(int i=0;i<6;i++) printf("%d ",a[i]);

输出结果：

100 100 100 100 5 6

9.6 sort()

sort(首元素地址, 尾元素的下一个地址, 比较函数(缺省则默认递增序))

sort()用的比较多，直接贴一下结构体排序的代码吧。

PAT_A1025

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct grade{
	char num[20];
	int score;
	int final_rank;
	int location_number;
	int local_rank;
	grade(){
	}
	grade(char _num[],int _score){
		strcpy(num,_num);
		score=_score;
	}
};
bool cmp(grade g1,grade g2){
	if(g1.score!=g2.score) return g1.score>g2.score;
	else return strcmp(g1.num,g2.num)<0;
}
int main(){
	int n,m;
	int i,j;
	grade stu[30010];
	char num[20];
	int score;
	int count=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&m);
		int temp=count;
		for(j=0;j<m;j++){
			scanf("%s%d",num,&score);
			stu[count]=grade(num,score);
			stu[count].location_number=i;
			count++;	
		}
		sort(stu+temp,stu+count,cmp);
		stu[0+temp].local_rank=1;
		for(j=1;j<m;j++){
			if(stu[j+temp].score<stu[j+temp-1].score){
				stu[j+temp].local_rank=j+1;
			}
			else{
				stu[j+temp].local_rank=stu[j+temp-1].local_rank;
			}
		}
	}
	
	sort(stu,stu+count,cmp);
	stu[0].final_rank=1;
	for(j=1;j<count;j++){
		if(stu[j].score<stu[j-1].score){
			stu[j].final_rank=j+1;
		}
		else{
			stu[j].final_rank=stu[j-1].final_rank;
		}
	}
	
	printf("%d\n",count);
	for(i=0;i<count;i++)
		printf("%s %d %d %d\n",stu[i].num,stu[i].final_rank,stu[i].location_number,stu[i].local_rank);
	return 0;
}

9.7 lower_bound()和upper_bound()

两个函数均用在有序数组或容器中。

lower_bound(first, last, val)用来寻找在数组或容器的[first, last)范围内第一个值大于等于val的元素的位置，返回指针或迭代器。

upper_bound(first, last, val)找的是第一个值大于val的元素的位置。

如果查不到则返回可以插入该元素的位置。

int a[10] = {1, 2, 3, 3, 3, 5, 5, 5, 5, 5};
// -1
int* lowerPos = lower_bound(a, a+10, -1);
int* upperPos = upper_bound(a, a+10, -1);
printf("%d %d\n", lowerPos - a, upperPos - a);
// 1
lowerPos = lower_bound(a, a+10, 1);
upperPos = upper_bound(a, a+10, 1);
printf("%d %d\n", lowerPos - a, upperPos - a);
// 3
lowerPos = lower_bound(a, a+10, 3);
upperPos = upper_bound(a, a+10, 3);
printf("%d %d\n", lowerPos - a, upperPos - a);
// 4
lowerPos = lower_bound(a, a+10, 4);
upperPos = upper_bound(a, a+10, 4);
printf("%d %d\n", lowerPos - a, upperPos - a);
// 6
lowerPos = lower_bound(a, a+10, 6);
upperPos = upper_bound(a, a+10, 6);
printf("%d %d\n", lowerPos - a, upperPos - a);

输出结果：

0 0
0 1
2 5
5 5
10 10

目录

1 vector

1.1 定义

1.2 元素访问

1.3 常用函数

1.4 vector常见用途

2 set

2.1 定义

2.2 元素访问

2.3 常用函数

2.4 set常见用途

3 string

3.1 定义

3.2 元素访问

3.3 常用函数

4 map

4.1 定义

4.2 元素访问

4.3 常用函数

4.4 map常见用途

5 queue

5.1 定义

5.2 元素访问

5.3 常用函数

5.4 queue常见用途

6 priority_queue

6.1 定义

6.2 元素访问

6.3 常用函数

6.4 元素优先级设置

6.4.1 基本数据类型的优先级设置

6.4.2 结构体的优先级设置

6.4.3 与sort()的比较

6.4.4 引用

6.4.5 priority_queue常见用途

7 stack

7.1 定义

7.2 元素访问

7.3 常用函数

7.4 stack常见用途

7.5 练习-括号匹配

8 pair

8.1 定义

8.2 元素访问

8.3 常用函数

8.4 pair常见用途

9 algorithm头文件下的常用函数

9.1 max()、min()、abs()

9.2 swap()

9.3 reverse()

9.4 next_permutation()

9.5 fill()

9.6 sort()

PAT_A1025

9.7 lower_bound()和upper_bound()