C++ STL常用方法归纳

概述

STL（Standard Template Library，标准模板库）是C++提供的一个重要的组件，涵盖了一些常用的数据结构和容器，以及一些基础算法的封装形式。STL对于解决算法问题无疑是十分有力的工具，可以无需像C语言那样从头开始实现较为复杂的数据结构。STL的很多数据结构和算法形式上都能在Java中找到影子。

接下来的内容将分为三部分，第一部分以表格形式对比Vector, String, Set, Map四种容器，第二部分简单介绍Queue, Deque, Priority_queue和Pair四种模板，第三部分介绍一些封装的算法。

Vector, String, Set and Map

之所以将它们并列到一起，是因为这四种容器都是可以进行遍历的数据结构，可以使用Iterator作为迭代器，如Vector的迭代器就可以如下定义，其它容器的迭代器类似。

#include <vector>
using namespace std;

vector<double> vct; //定义一个double类型的向量
vector<double>::iterator it = vct.begin() //定义一个double类型的向量迭代器，并使其指向vct开头
for(; it != vct.end(); it++) ; //迭代器以for循环进行遍历

当然，四种同期也各有特点，比如Vector实现的是类似于变长数组的功能，String显然是字符串，Set是数学意义上的集合的实现，而Map则类似于python中的字典。我们将它们常用的一些方法列成下面的表格进行对比：

表格规模较大，如果视觉效果不佳，请在右下角设置按钮打开“阅读模式”查看，或者点击这里查看图片版。

	Vector	String	Set	Map
`size()`	元素个数，返回值类型为`unsigned int` 时间复杂度为 $O(1)$	同Vector，还支持`length()`等价写法	同Vector	同Vector
`clear()`	清空所有元素；时间复杂度为 $O(N)$ ， $N$ 为元素个数	同Vector	同Vector	同Vector
`insert()`	`insert(it, x)`：在迭代器`it`处插入元素`x`；时间复杂度为 $O(N)$	`insert(pos, str)`：在下标为`pos`处插入一个字符串`str`； `insert(it, it2, it3)`：将迭代器`[it2, it3])`间的字符串插入至迭代器`it`处；时间复杂度为 $O(N)$	`insert(x)`：将元素`x`插入容器，并自动递增排序和去重；时间复杂度为 $O(logN)$	-
其它增加元素的方式	`push_back(x)`：在最后添加一个元素； `pop_back()`：删除尾部元素	-	-	直接使用`map[key] = value`的方式建立映射，键自动去重并排序
`erase()`	`erase(it)`：删除迭代器`it`处的元素； `erase(left, right)`：删除 [left, right) 区间内的所有元素，两个参数均为迭代器；时间复杂度为 $O(N)$	`erase(it)`：删除迭代器`it`处的元素； `erase(left, right)`：删除 [left, right) 区间内的所有元素，两个参数均为迭代器； `erase(pos, len)`：从`pos`位置开始删除`len`个字符；时间复杂度为 $O(N)$	`erase(it)`：删除迭代器`it`处的元素，时间复杂度为 $O(1)$ ； `erase(value)`：删除值为`value`的元素，时间复杂度为 $O(logN)$ ； `erase(left, right)`：删除 [left, right) 区间内的所有元素，两个参数均为迭代器，时间复杂度为 $O(right-left)$ ；	`erase(it)`：删除迭代器`it`处的元素，时间复杂度为 $O(1)$ ； `erase(key)`：删除键为`key`的键值对，时间复杂度为 $O(logN)$ ， $N$ 为容器中键值对的数目； `erase(left, right)`：删除 [left, right) 区间内的所有元素，两个参数均为迭代器，时间复杂度为 $O(right-left)$ ；
访问方式	下标、迭代器（支持与常数组合）	下标、迭代器（支持与常数组合）	迭代器（不支持与常数组合）	下标（与key配合），迭代器（key和value同时访问）
`find()`	-	-	`find(value)`：返回容器中值为`value`的迭代器；时间复杂度为 $O(logN)$	`find(value)`：返回容器中键为`key`的键值对的迭代器；时间复杂度为 $O(logN)$
其它	-	`+/+=`：字符串的拼接； `==/!=/</<=/>/>=`：按照字典序进行字符串的比较；	C++11新增`unorderd_set`，用法类似，但不自动排序	C++11新增`unorderd_map`，用法类似，但不自动排序

Pair

简而言之，Pair就是两个任意类型数据的组合结构体。前面所述的Map在底层实现中用到了Pair，因此在使用Pair之前引用的头文件与Map相同。Pair的要点有三处：定义、访问、比较。

定义：使用pair<type1, type2> p{val1, val2}初始化，或先定义再使用make_pair(val1, val2)赋值；
访问：分别用p.first和p.second访问第一个和第二个元素，也可以进行赋值；
比较：可以像字符串那样使用比较运算符进行比较，依据是"先first后second"。

双端队列：Deque

Deque从字面意义上来讲是Queue的一种变体，但实际上其特性与Vector更加类似。Deque与Vector一点关键的不同是提供了在开头插入和删除元素的接口push_front(x)和pop_front()，并且这两个端口可以实现 $O(1)$ 的时间复杂度。除此之外，Deque与Vector的各种接口基本都是一致的。

然而，在底层的实现原理上，Deque与Vector又大不一样。由于Deque分配的内存空间可能是不连续的，因此如果不是对两端元素进出有刚性需求，还是应当优先使用Vector，以提高遍历等操作的效率。

使用Deque之前需要在文件头部添加引用#include <deque>。

Queue, Priority_queue and Stack

这三种容器的特征与上面的四种有着较大的差异，而它们之间又有着较大的相似性，因此拿到一起来介绍。

顾名思义，Queue实现的是队列，Deque是双端队列，Priority_queue是用堆实现的优先队列，Stack是栈。队列和栈都是笔者大一数据结构课程的重点，也曾经用C手动实现过。从复杂度来讲，这些数据结构的功能相对也要简单一些，相似性也更大一些。

队列和栈的表格类比

这里我们列一个简单的“功能-接口”表来做比较。其中Deque由于较为复杂，将与Pair一起在后面单独介绍：

	头文件	添加元素	弹出元素	访问边界元素	判空	元素个数
Queue Priority_queue Stack	`<queue>` `<queue>` `<stack>`	`push(x)`	`pop()`	`front()&back()` `top()` `top()`	`empty()`	`size()`

Priority_queue优先级的设定

对于基本数据类型，默认使用数值降序/字典序来确定优先级。如果要颠倒顺序，应当采取下面的定义方式：

#include <queue>
using namespace std;

priority_queue<int, vector<int>, less<int> > q; //默认的降序
priority_queue<int, vector<int>, greater<int> > q; //这将使队列将数值低的放在堆顶

对于结构体等自定义类型，要对"<"运算符进行重载或定义类似qsort的cmp函数，来规定优先级。比如下面的代码就在结构体fruit内部规定以价格升序确定优先级：

#include <queue>
using namespace std;
struct fruit {
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2) {	//运算符重载函数
        return f1.price > f2.price;
    }
}

另一种写法可以将重载函数单独拿出来，不依赖其它结构体而存在：

#include <queue>
using namespace std;
struct fruit {
    string name;
    int price;
};
struct cmp {
    bool operator () (fruit f1, fruit f2) {		//运算符重载函数
        return f1.price > f2.price;
    }
};
priority_queue<fruit, vector<fruit>, cmp > q;	//定义方式相应地进行调整

算法封装

这里简单介绍一下常用算法的封装形式和主要功能，不做太详细的阐述。使用这些算法之前，都需要在预处理部分加入头文件<algorithm>。

max(a, b)和min(a, b)：在两个元素之间返回最大值或最小值；
abs(x)：返回整数x的绝对值；
swap(a, b)：交换参数a和b的值，无返回值；
reverse(it1, it2)：参数it1和it2可以是数组的指针或者STL容器的迭代器，这个函数将[it1, it2)范围内的元素进行翻转；
fill(it1, it2, x)：将数组或容器中[it1, it2)范围内元素均赋值x，x需与数组/容器本身数据类型对应；

sort(it1, it2, [cmp])：将数组或容器中[it1, it2)范围内的元素进行排序，对于基本数据类型默认为升序，如果需要降序或使用自定义数据类型，需要提供cmp函数以确定排序规则。比如，对于一个结构体的二级排序可以这样写：

#include <algorithm>
using namespace std;
struct node {
  int x, y;
}
bool cmp(node n1, node n2) {
  if (n1.x != n2.x)
      return n1.x > n2.x;    //如果x属性不相等，则按照从大到小的顺序排列；
  else
      return n1.y < n2.y;    //如果x属性相等，则按照y从小到大的顺序排列；
}