由于自己之前并不常用 STL 库，而 STL 库在很多算法中能够节省很多自己手打数据结构的时间，故这里开一个笔记来重新学习一下，也方便自己之后能够复习。

# Vector 的常见用法详解

【简介】vector 翻译为向量，我觉得用‘变长数组’来解释他更为合适。利用 vector 可以避免超内存等情况，节省空间。也可以用邻接表的方式来存储图。 使用 vector 头文件是 vector 需要 include.
1，vector 定义
单独定义一个 vector:

1
vector<typename> name;

上面这个定义其实相当于定义了一个一维数组 name [SIZE]，只不过其长度可以根据需要进行变化。 这里的 typename 可以是任何数据类型。
如果 typename 也是 vector

1
vector<vector<typename>> name;

这里很容易联想到二维数组的定义，我们可以认为其是两个维度都可变长的二维数组。
然后是 vector 数组 的方法:

1
vector<typename> Arrayname[arraysize];

这样 Arrayname [0] ~ Arrayname [arraysize-1] 都是一个 vector 容器。 这里是一个维度固定的二维数组。
2，vector 容器内元素的访问

  • 通过下标访问。
    和访问普通数组一样，对于 vector<typename> vi; 直接通过 vi [index 访问即可。这里的下标是从 0 到 vi.size ()-1 访问这个范围外的元素可能会出错。

  • 通过迭代器访问。
    迭代器 (iterator) 可以理解是一种类似指针的东西，其定义是:

    1
    vector<typename>::iterator it;

    这样得到了迭代器 it, 并且可以通过 * it 来访问 vector 的元素。
    例如，这里有一个 vector 容器：

    1
    2
    3
    4
    vector<int> v1;
    for(int i = 1;i <= 5; i++){
     vi.push_back(i);
    }

    可以通过下面的方式进行访问容器内的元素

    1
    2
    3
    4
    vector<int>::iterator it = vi.begin();
    for(int i=0;i < 5; i++){
    	printf("%d ",*(it + i)); //输出 vi[i]
    }

    从这里可以看出 vi [i] 和 *(vi.begin ()+ i ) 是等价的。
    这里 begin () 是取 vector 头元素的地址，这里引出 end() 这里需要注意 end() 是取 vector 末尾元素地址的下一个地址，不存储任何元素。故这里有了另一种遍历 vector 的方法。

    1
    2
    3
    for(vector<int>::iterator it = vi.begin(); it != vi.end() ; it++){
    	printf("%d ", *it);
    }

    最后需要指出，在常用的 STL 容器中，只有 vector 和 string 中，才允许使用 vi.begin ()+3 这种迭代器加上整数的写法。
    3，vector 常用函数实例解析
    （1）push_back
    顾名思义，push_back (x) 就是在 vector 尾元素添加一个元素 x, 时间复杂度 O (1)。
    （2）pop_back
    即删除 vector 的尾元素。
    （3）size()
    用来获取 vector 中元素的个数。返回 unsigned 类型。
    （4）clear()
    用来清空 vector 中的所有元素。
    （5）insert()
    insert (it,x) 用来向 vector 的任意迭代器 it 处插入一个元素 x。
    （6）erase()
    两种用法：删除单个元素，删除一个区间的所有元素。
    ①删除单个元素。 erase (it) 即删除迭代器为 it 处的元素。
    ②删除一个区间所有的元素，erase (first,end), 删除 [first,last) 内的所有元素。
    4，vector 的常见用途
    （1）存储数据
    （2）用邻接表存储图

# set 的常见用法详解

【简介】set 翻译为集合，是指一个内部自动有序且不含重复元素的容器。考试中，有可能出现需要去掉重复元素的情况，这时候就可以用 set 来保留元素本身不考虑其个数。使用 set 需要添加 <set>。
1，set 的定义
单独定义一个 set

1
set<typename> name;

这里的写法和 vector 基本一样，或者说大部分的 STL 都是这样定义的，typename 可以是任何基本类型。 这里不再介绍各个数组之类的定义方式，和 vector 基本一样。
2，set 容器内元素的访问
set 只能通过迭代器 (iterator) 访问。定义方式和 vector 的迭代器定义方式一样。由于除了 vector 和 stirng 之外的迭代器都不只除 *(it + i) 的访问方式，因此只能按照下面方式枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
\#include<stdio.h>
\#include<set>
using namespace std;
int main(){
	set<int> st;
	st.insert(3);
	st.insert(5);
	st.insert(2);
	st.insert(3);
	for(set<int>::iterator it = st.begin();it != st.end(); it++){
		printf("%d ", *it );
	}
	return 0;
}

这里的输出结果为 2 3 5。
3,set 常用函数实例解析
（1） insert ()
insert (x) 可将 x 插入 set 容器中，并自动递增排序和去重。
（2）find()
find (value) 返回 set 中对应值为 value 的迭代器。
（3）erase()
erase 也有两种用法：删除单个元素，删除区间内元素
①删除单个，st.erase (it)，it 为所要删除元素的迭代器。可以结合 find () 函数来表示
st.erase (value),value 为所要删除的元素的值。
②删除一个区间的所有元素。 st.erase (first,last) 可以删除一个区间所有的元素，first 和 last 为迭代器形式，注意删除为 [first,last) 左闭右开。
（4）size()
用来获得 set 内元素的个数。
（5）clear()
clear () 用来清空 set 中所有的元素。
3,set 的常见用途
主要作用是自动去重并按照升序进行排序。

# string 的常见用法详解

【简介】在 C 语言中，一般用字符串数组 char str [] 来存放字符串。使用 string 会更加的方便。如果要使用 string，需要包含 string 头文件，注意 string.h 和 string 是不一样的头文件。
1，string 的定义
定义 string 的方式和基本数据类型相同，只需要在 string 上跟上变量名（可进行初始化）即可：

1
2
string str;
string str = "abcd";

2，string 中内容的访问
（1）通过下标访问
一般来说，可以直接像字符数组那样去访问 string:

1
2
3
for(int i=0;i < str.length(); i++){
	printf("%c ",str[i]);
}

输出结果就是 abcd 。
如果要读入或者输出整个字符串，则只能用 cin 和 cout：(如果想用 printf 输出 string，需要利用 c_str () 函数将 string 类型转换为字符数组来进行输出)

1
2
3
4
string str;
cin>>str;
cout<<str;
printf("%s\n",str.c_str());

（2）通过迭代器访问
因为有些函数如 insert () 和 erase () 要求迭代器为参数，因此还是需要学习一个 string 迭代器的用法。
由于 string 不像其他 STL 容器需要参数，故可以这样定义迭代器。

1
string::iterator it;

这样就得到了迭代器 it，并且可以通过 * 来访问 string 的每一位。

1
2
3
4
string str = "abcd";
for(string::iterator it = str.begin(); it != str.end(); it++){
	printf("%c ", *it);
}

3,string 常用函数实例解析
string 的函数有很多，这里只调出几个主要的。
（1）operator+=
这是 string 的加法，可以直接将两个 string 拼接起来。

1
2
string str1 = "abc", str2 = "xyz";
str1 += str2; //将str2直接拼接到str1上

（2）compare operator
两个 string 类型可以用 ==，!= , <, <= ,> , >= 进行比较大小，比较规则是字典序。
（3）length()/size()
length () 返回 stirng 的长度，即存放的字符数。size () 和 length () 基本相同。
（4） insert()
string 的 insert () 函数有很多写法，这里给出几个常用的写法。
①insert (pos,string)，在 pos 号位置中插入字符串 string。
②insert (it,it2,it3)，it 为字符串的欲插入位置，it2 和 it3 为待插入字符串的首尾迭代器，用来表示串 [it2,it3) 将被插入在 it 的位置上。
（5）erase()
erase () 有两种用法：删除单个元素，删除一个区间的所有元素。
①删除单个元素：erase (it) 用于删除单个元素，it 为所需要删除的元素的迭代器。
②删除一个区间所有元素，erase (first,last)，同理，删除 [first,last)，first 和 last 为相应的迭代器。这里还有一种用法，str.erase (pos,length)，pos 为需要开始删除的起始位置，length 为删除的字符个数。
（6）clear()
clear () 用于清空 string 的数据。
（7）substr()
substr (pos,len) 返回从 pos 号位开始，长度为 len 的字串
（8）string::npos
string::npos 是一个常数，其本身的值为 - 1，但是由于是 unsigned_int 类型，因此实际上也可以认为其是 unsigned_int 类型最大值，string::npos 用以作为 find 函数匹配失败的返回值。
（9）find()
str.find (str2)，当 str2 是 str 的子串时，返回其在 str 中第一次出现的位置，如果 str2 不是 str 的子串，返回 string::npos。
str.find (str2,pos)，从 str 的 pos 号位开始匹配 str2，返回值和上相同。
（10）replace()
str.replace (pos,len,str2) 把 str 从 pos 号位开始，长度为 len 的子串替换为 str2。
str.replace (it1,it2,str2) 把 str 的迭代器 [it1,it2) 范围的子串替换为 str2。

# map 的常用用法详解

【简介】 map 翻译为映射。在定义数组时 (int array [100])，其实是定义了一个从 int 型到 int 型的映射，比如 array [0] = 25,array [4] =36 就分别是将 0 映射到 25，将 4 映射到 36. 一个 double 型数组则是将 int 映射到 double 型，这里不再介绍。这样，当我们需要其他类型作为关键字来作映射，会显得不太方便。这时可以用到 map，因为 map 可以将任何基本类型（包括 STL 的容器）映射到任意基本类型。
1，map 的定义
单独定义一个 map

1
2
3
map<typename1,typename2> mp;
map<string,int> map;  //字符串映射int型 必须用string
map<set<int>,string> mp;  //可以让STL容器作为键

上述代码中，第一个是键的类型，第二个是值得类型。注意如果是字符串到整型得映射，必须用 string 而不能用 char 数组。
2，map 容器内元素得访问
map 有两种访问方式：下标和迭代器

  • 通过下标访问
    和普通数组一样，例如对于 map<char,int> mp 得 map 来说，可以使用 mp [‘c’] 来访问对应对应得整数。当建立映射时，可以用 mp [‘c’] = 20 这样和普通数组一样得方式。但是要注意的是，map 中得键是唯一的。
  • 通过迭代器访问
    map 得迭代器定义和其他得 STL 容器迭代器定义得方式一样 
    1
    map<typename1,typename2>::iterator it;
    typename1 和 typename2 就是定义 map 时填写得类型，这样就得到了迭代器 it。
    map 迭代器得使用方式和其他 STL 容器得迭代器不同，因为 map 得每一对映射都有两个 typename，这决定了必须能通过一个 it 来同时访问键和值。事实上，map 可以使用 it->first 来访问键，使用 it->second 来访问值。 
    1
    2
    3
    4
    5
    6
    7
    map<char,int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char,int>::iterator it = mp.begin(); it != mp.end(); it++){
    	printf("%c %d\n", it->first, it->second);
    }
    结果： 
    1
    2
    3
    a 40
    m 20
    r 30
    这里似乎有一个很神奇的现象：map 会以键从小到大的顺序自动排序，这是由于 map 内部使用红黑树实现的 (set 也是)，在建立映射会自动实现从小到大的排序功能。
    3，map 常用函数实例解析
    （1）find ()
    find (key) 返回键为 key 的映射的迭代器。
    （2）erase()
    有两种用法：删除单个元素，删除一个区间额你的所有元素。
    ①删除单个元素：map.erase (it)，it 为需要删除的元素的迭代器。
    示例如下:
1
2
3
4
5
6
map<char,int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;  
map<char,int>::iterator it = mp.find('b');
mp.erase(it);  //这里删除了 b 2

第二种方式，mp.erase (key),key 为欲删除的映射的键。
②删除一个区间的所有元素。mp.erase (first,last)，其中 first 为需要删除的区间的起始迭代器，而 last 则为需要删除的区间的末尾迭代器的一个地址，也为左闭右开的区间 [first,last)。
（3）size()
size () 用来获取 map 中映射的对数。
（4）clear()
clear () 用来清空 map 中的所有元素。
4,map 的常见用途
感觉 map 能用到的地方应该算是比较多的。

  • 需要建立字符和整数之间映射的题目。
  • 判断大整数或其他数据是否存在的题目，吧 map 当 bool 数组使用。
  • 字符串和字符串的映射也可能会遇到。
    ** 扩展:mao 的键和值是唯一的，如果一个键需要对应多个值，只能用 multimap。另外，C++11 还加了 unordered_map，以散列代替 map 内部的红黑树实现，使其可以用来处理只映射而不按 key 排序的需求，速度会很快。

# queue 的常见用法详解

【定义】queue 翻译为队列，是一种很常见的数据结构。STL 实现了一个先进先出的容器。使用时需要添加 queue 的头文件。
1，queue 的定义

1
queue<typename> name;

2，queue 容器内元素的访问
由于队列本身是一种先进先出的限制性数据结构，因此再 STL 中只能用 front () 来访问队首元素，或者是 back () 来访问队尾元素。
3，queue 常用函数实例解析
（1）push ()
push (x) 将 x 进行入队。
（2）front(),back()
front 和 back 分别获取队首元素和队尾元素。
（3）pop()
pop () 令队首元素出队。
（4）empty()
empty () 检测 queue 是否为空。
（5）size()
size () 返回 queue 内元素的个数。
4,queue 的常见用途
当需要进行 BFS 时，可以直接用 queue 进行代替
有一点可能需要注意，再使用 front () 和 back () 之前，先用 empty () 判断队列是否为空，否则可能会出现错误。

# priority_queue 的常见用法详解

【简介】 priority_queue 又称为优先队列，其底层是用堆来实现的。在优先队列中，队首元素一定是当前队列中优先级最高的哪一个。如队列有如下元素，且定义好了优先级：

1
2
3
桃子 (优先级3)
梨子 (优先级4)
苹果 (优先级1)

那么出队顺序为梨子 -> 桃子 -> 苹果。
当然，可以在任何时候往优先队列加入元素，而优先队列底层的数据结构堆 (heap) 会随时调整结构，使得每次的队首元素都是优先级最大的。
1，priority_queue
要使用优先队列，应该添加头文件 queue。 其定义写法也和其他 STL 容器相同。

1
priority_queue<typename> name;

2,priority_queue 容器内元素的访问
和队列不一样的是，优先对立而没有了 front () 和 back () 函数，而只能通过 top () 函数来访问队首元素，也就是优先级最高的元素。
3,priority_queue 常用函数实例解析
（1）push ()
push (X) 将 X 入队，时间复杂度 O (logN)，其中 N 为当前优先队列中的元素个数。
（2）top()
获取队首（堆顶）的元素。
（3）pop()
使队首（堆顶）的元素出队。
（4）empty()
检测优先队列是否为空。
（5）size()
size () 返回优先队列元素的个数。
4，priority_queue 内元素优先级的设置
下面来介绍下优先级的设置方法。
（1）基本数据类型的优先级设置
此处指的是 int,double,char 等可以直接使用的数据类型，对他们的游戏那寄设置一般使数字大的优先级越高，因此队首元素就是优先队列元素中最大的那个 (char 类型则是字典序最大的)。对基本数据类型来说，下面两种定义是等价的。

1
2
priority_queue<int> q;
priority_queue<int,vector<int>,less<int>> q;

可以发现，第二种定义方式的尖括号多出了两个参数：一个是 vector<int>，另一个是 less<int>。其中第二个参数填写的是承载底层数据结构堆的容器，如果第一个参数是 double 或 char 型，则此处只需要填写 vector<double > 或 vector<char>; 而第三个参数 less<int > 则是对第一个参数的比较类，less<int > 表示数字大的优先级大，而 greater<int > 表示数字小的优先级大。
（2）结构体的优先级设置
这里以开头举得水果的例子

1
2
3
4
5
6
7
8
struct fruit{
	string name;
	int price;
	friend bool operator < (const fruit &f1,const fruit &f2){
		return f1.price < f2.price;
	}
}
priority_queue<fruit> q;   //这里就像sort的cmp函数一样， 这里是正常的 这里是以价格高的水果优先

现在如果希望水果的价格高作为优先级高，就需要重载小于号 "<"。重载是指对已有的运算符重新定义。见上代码块。可以看到在结构体增加了一个友元函数。 这里可以记一下， 优先对了的这个函数和 sort 的 cmp 函数的效果是相反的。
5,priority_qeue 的常见用途
可以解决一些贪心问题，也可以对 Dijkstra 算法进行优化。

# stack 的常见用法解析

【简介】stack 翻译为栈，是 STL 种实现一个后进先出的容器。
1，stack 的定义
需要添加头文件 stack，用法依然和其他 STL 容器一样。

1
stack<typename> name;

2，stack 容器内元素的访问
由于 stack 是一种后进先出的数据结构，在 STL 的 stack 只能通过 top () 来访问栈顶元素。
3，stack 常用函数实例解析
（1）push ()
将 x 入栈。
（2）top()
获得栈顶元素。
（3）pop()
弹出栈顶元素。
（4）empty()
判断 stack 是否为空。
（5）size()
返回 stack 内元素的个数。
4,stack 的常见用途
stack 一般用来模拟实现一些递归，防止程序堆栈内存的限制而导致程序运行出错。一般来说，程序的栈内存空间很小。

# pair 的常见用法解析

【简介】pair 是一个很实用的 "小玩意"，当想要将两个元素绑在一起作为一个合成元素，又不想定义结构体时，可以用 pair。其可以看作时一个内部有两个元素的结构体。

1
2
3
4
struct pair{
	typename1 first;
	typename2 second;
}

1，pair 的定义
要使用 pair，需要添加头文件 utility。注意：由于 map 实现过程中设计 pair，因此添加 map 头文件会自动添加 utility 头文件，故添加 map 头文件即可。

1
2
pair<typename1,typeName2> name;
pair<string,int> p("haha",5);

如果想初始化，只需要加个括号里面添加初始化的内容即可。如果想要临时构建一个 pair，有下面两种方法。

1
2
pair<string,int>("haha",5)
make_pair("haha",5)

2，pair 中元素的访问
pair 中只有两个元素，分别是 first 和 second，只需要按照正常结构体方式去访问即可。
3，pair 的使用函数解析
这里只需注意比较操作数，是先比较 first，first 相等时采取判别 second 的大小。
4，pair 的常见用途

  • 用来代替二元结构体和其构造函数，可以节省编码时间。
  • 作为 map 的键值来进行插入。