算法入门笔记 #2 STL标准库

STL (Standard Template Library) 标准模板库，是一个具有工业强度的，高效的 C++ 程序库。文章开头先附上一个 STL 常用模板，方便取用：

#include<bits/stdc++.h> // 万能头文件
using namespace std; 	// 大部分的 STL 保留字位于 std 命名空间

#define pb push_back
#define mp make_pair
#define x first
#define y second  		// 结合 pair 用

typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii; // 常用于坐标系

vector<int> a;
a.pb(1);

vector<pii> p;
p.pb(mp(1,1)); // 支持 C++ 11 及以上的平台 mp 可以用 {} 代替

Algorithm 算法库

头文件 #include<algorithm> 定义了 STL 中基础的算法，大部分方法可以在容器中找到对应函数，例如不修改内容的 find、count 等操作，修改内容的 remove、replace、swap 等操作，以及排序、二分查找、两数取最大最小、交换两数等算法。

这里列出常用的几个操作：

• __gcd(1024, 256);：求最大公约数，在 C++ 17 后也可以用 gcd(1024, 256);。
  • 利用该函数可以实现求最小公倍数：a * b / __gcd(a, b)
• min({a, b, c, d})：返回多个数的最值，需要用大括号包围（C++11 以上）。
• sort(a,a+n)：采用快速排序，除了数组指针也支持迭代器 sort(v.begin(), v.end())。
  • 如果要自定义比较函数 cmp，遵循以下模板：bool cmp(T &a,T &b){return a<b;}，在力扣刷题时要在函数前加上 static。
  • 也可以直接用 Lambda 函数作为比较函数，sort(v.begin(), v.end(), [](auto &a, auto &b){ return a < b;}); 这里返回的是「a 必须排在 b 前面的判断条件」。
  • 默认是升序排列，如果要降序排列则用 sort(v.begin(), v.end(), greater<int>());
• stable_sort(a,a+n)：采用归并排序，不改变相等元素的相对位置，用法和前者相同。
• is_sorted(v.begin(), v.end())：判断容器内部是否有序，返回布尔值。
• reverse(v.begin(),v.end())：翻转 vector 容器，也可以用于 string 字符串的翻转。
• lower_bound(a,a+n,x)：返回升序数组中可以插入元素 x 的最低位置，也就是大于等于 x 的第一个数的地址；
• upper_bound(a,a+n,x)：返回升序数组中可以插入元素 x 的最高位置，也就是大于 x 的第一个数的地址；
  • 简记：假设有一个数组 1 1 2 2 2 3 3，如果 x 选 2，则可以插在第一个 2 的位置，也可以插在第一个 3 的位置，此时其他元素后移，不会改变升序。
  • 将得到地址减去数组的起始地址就可以得到下标：pos = lower_bound(a,a+n,x) - a;
  • 此方法在前两个参数构成的前闭后开区间内查找，如果不存在满足的元素（x 比所有元素都大）则返回 end()，如果数组是降序的，则需要加上参数 greater<int>()。
  • 也可以自定义 Lambda 函数作为比较函数，需要注意第一个项是目标的类型，第二个项才是序列的类型：upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {return b < a[0]; });
• binary_search(a,a+n,x)：二分查找升序数组中是否存在元素 x，返回布尔值。
• auto [l, r] = equal_range(v.begin(),v.end(),x)：返回升序数组中元素 x 出现的第一个位置和最后一个位置 + 1，其实就是封装了上述两个二分查找函数。
  • 如果返回值 l==r，说明元素 x 不存在，二者都指向了第一个大于 x 的位置。
• nth_element(first，kth，end)：将第 k 小元素放到它该放的位置上，左边元素都小于等于它，右边元素都大于等于它。这是一个原地算法，会改变原数组，复杂度 \(O(n)\)。
  • 除了数组指针也支持迭代器 nth_element(v.begin(), v.begin() + k, v.end())。
  • 如果要选择第 k 大元素，可以使用 nth_element(v.begin(), v.begin() + k, v.end(), greater<int>())。
• max_element(a,a+n)：遍历并返回数组最大值的位置，可以直接 *max_element() 获取最大值。
• next_permutation(a,a+n)、next_permutation(v.begin(), v.end())：原地算法，改变原数组、向量、字符串为按字典序的全排列中的下一排列，返回 bool 值为 0 时表示结束。
• accumulate(a,a+n,0)、accumulate(v.begin(), v.end(), 0)：用加法运算符求出元素序列的和，第三个参数是和的初值。该方法也可以自定义加法运算符，作为第四个参数输入。
  • accumulate() 返回值的类型由第三个数确定，如果输入 0 则最大值为 INT_MAX。在某些场景可能会溢出，需要改成 0LL。
• unique(a,a+n)：去除数组中相邻的重复元素（配合排序使用），返回去重后的尾地址。这里的去除并非真正意义的 erase，而是将重复的元素放到容器的末尾。
  • 将尾地址减去数组的起始地址就能得到去重后的个数：n = unique(a,a+n) - a;，然后遍历。
  • 结合向量的批量删除操作真正去掉重复：v.erase(unique(v.begin(), v.end()), v.end());，之后用 n = v.size() 就能得到去重后的个数。

字符串 | string

string 是 C++ 特有的字符串变量类型。

基础操作

• 头文件 #include<string>
• 声明 string 变量：
  • 直接声明并等号赋值：string str="12345678";
  • 声明一个副本：string s(str);
  • 声明一个字符串数组的复制品：char ch[]="12345678"; string s(ch);
  • 利用迭代器复制区间：string s(str.begin(),str.end()-2);
  • 将 int 变量转 string：string strNum=to_string(intNum);
• 运算符（重载后）：
  • 比较运算符 == > < >= <= != 用法参考 strcmp
  • 加法运算符 + += 用于连接两个字符串
  • 下标运算符 [] 用于获取特定位置
• 特性函数：
  • 返回当前容量，即不必挪动就能存放的字符数：s.capacity();
  • 返回经过挪动后能存放的最大容量：s.max_size();
  • 返回当前在内存空间中的大小（字节数），不计终止符：s.size(); 或 s.length();
  • 判断当前字符串是否为空：s.empty();
  • 返回当前 string 对应的字符数组的头指针：printf("%s", s.c_str());
• 查找运算：
  • 返回 str 在 s 中第一次出现的位置（整型下标值），没找到就返回 s.npos ：s.find(str);
  • 同上，从下标为 index 处开始查找：s.find(str,idx);
  • 同上，查找对象换成字符：s.find('x');
  • 返回 str 在 s 中最后一次出现的位置：s.find_last_of(str);
• 其他运算：
  • 在下标 p 位置插入，原有的后移，但不能插在结束符后的空间：s.insert(p, "hello");
  • 在末尾插入一个字符：s.push_back('a');（和 vector 很相似）
  • 删除 p 开始的所有字符：s.erase(p);
  • 交换当前字符串与 str 的值：s.swap(str);
  • 返回从下标 i 开始到末尾的子串：s.substr(i)
  • 返回从下标 i 开始连续 n 个字符的子串：s.substr(i,n)，如果超过总长度则输出到末尾的子串
  • 将 string 变量转 int：int num = stoi(s); 注意该方法不进行溢出判断，处理整数翻转时容易溢出！
  • 将 string 变量转 long long：ll num = stoll(s); 该方法同样不进行溢出判断，但范围更广。

特殊性质

• string 拥有一个特殊的输入输出流库：#include<sstream>，可以将任意类型的变量输出到流中，再以字符串的形式读出。如 int 转 string 操作：

#inlcude<sstream>
stringstream ss;
ss << intNum;
string strNum = ss.str(); //.str()是<sstream>库中的函数

• 由于 string 也是容器，因此支持迭代器和下标两种访问操作，通常用下标方便处理更复杂的输出。

易混淆的库

• cstring：与 C 兼容的字符串处理库，使用字符串数组、指针操作
  • strcpy(a,b)：将 b 字符串拷贝到 a 处，遇到 '\0' 停止，可能溢出
  • strcat(a,b)： 将 b 字符串连接到 a 处，可能溢出
  • strcmp(a,b)：比较 a,b 字符串，直到遇到不相同的字符或者 '\0'，都相同返回 0，首个不同字符 a<b 则返回负数，否则返回正数
  • strlen(a)：返回 a 字符串的长度，不含 '\0'
  • strstr(a,b)：在 a 中查找 b 字符串，返回第一次出现位置的指针
  • memset(a,'x',n)：将 a 指向的内存空间，逐字节地赋值为字符 x，此处也可替换成 0-255 的十进制或十六进制数字
  • memcpy(a,b,n)：将 b 指向的内存空间拷贝 n 个字节到 a，可能溢出
  • memcmp(a,b,n)：比较两个内存空间的前 n 个字节
• cctype：用于字符类型的判别与处理
  • isalnum()：如果参数是字母数字，即字母或者数字，函数返回 true
  • isalpha()：如果参数是字母，函数返回 true
  • isdigit()：如果参数是数字（0－9），函数返回 true
  • isgraph()：如果参数是除空格之外的打印字符，函数返回 true
  • islower()：如果参数是小写字母，函数返回 true
  • isprint()：如果参数是打印字符（包括空格），函数返回 true
  • isupper()：如果参数是大写字母，函数返回 true
  • isxdigit()：如果参数是十六进制数字，即 0－9、a－f、A－F，函数返回 true
  • tolower()：如果参数是大写字符，返回其小写，否则返回该参数
  • toupper()：如果参数是小写字符，返回其大写，否则返回该参数

向量 | vector

vector 是一个能够存放任意类型的动态数组，能够增加和压缩数据，是同一种类型的对象的集合，每个对象都有一个对应的整数索引值。

向量中的元素按照严格的线性顺序排序，可以通过元素在序列中的位置访问对应的元素。使用一个内存分配器对象来动态地处理它的存储需求。

基础操作

• 头文件 #include<vector>

• 创建 vector 对象：

  • 直接创建：vector<int> v;（实际中通常会 typedef vector<int> vi;）
  • 直接创建并初始化（类似数组）：vector<int> v={1,2,3};
  • 拷贝一个副本：vector<int> v_b(v_a);，深拷贝，两个向量都会保留
  • 迁移对象：vector<int> v_b = move(v_a)，速度最快，只操作指针，但会导致 v_a 无法访问
  • 创建含有 n 个元素 a 的对象：vector<int> v(n,a);
  • 创建含有 n 个元素且全 0 的对象：vector<int> v(n);
  • 创建二维对象：vector<vector<int>> dp(n, vector<int>(n));

• 插入、删除元素：

  • 尾部插入元素：v.push_back(a);
  • 尾部生成元素：v.emplaceback(a);，效率比前者更高。
  • 尾部删除元素：v.pop_back();，无返回值。
  • 任意位置插入元素：v.insert(v.begin()+i, a)，在下标 i 的元素前面插入 a。
  • 删除元素：v.erase(v.begin()+2)，删除下标 2 的元素。
  • 批量删除：v.erase(v.begin()+i, v.begin()+j)，删除左闭右开区间。

• 特性函数：

  • 向量大小：v.size()
  • 内存中向量能包含的最大元素个数：v.max_size()
  • 清空：v.clear();
  • 判断空：v.empty()

• 访问元素：

  • 随机访问成员：v.at(i)，返回元素的引用

  • 数组运算符：v[i]，返回元素的引用

  • 特定元素访问：v.front() 和 v.back() 返回第一个和最后一个元素的引用

  • 迭代访问：

    // 声明迭代器，此时的 it 类似指针
    vector<int>::iterator it; 	// 这里可以换成 auto
    for(it=vec.begin(); it!=vec.end(); it++)
        cout<<*it<<endl;  		// 访问指针指向的元素，有 *
    
    // C++11 新语法，此时的 item 为元素本身
    for(auto item:vec)
        cout<<item<<endl;  	// 不需要 *，且此时修改不会影响原数组（深拷贝）
    for(auto &item:vec)
        item++;	 		   	// 如果带有 & 就可以修改元素（浅拷贝）
    
    // 不用迭代器直接用下标索引遍历
    for(int i = 0; i < vec.size(); i++)
        cout<<vec[i]<<endl;

特殊性质

• v.begin() 与 v.end() 返回的是指针，指向第一个元素和最后一个元素的下一个位置（无意义），只能赋值给迭代器。
  • 与普通指针相同，*(v.begin()+i) 可以访问下标 i 的元素。
  • 与普通数组相同，使用 sort 排序时，必须要用 sort(v.begin(),v.end());
• v.front() 与 v.back() 返回的是元素的引用，可以赋值给别名变量（浅拷贝）或普通变量（深拷贝）。
  • 引用是 C++ 特有的语法，声明引用变量 int &a=v.front(); 时，共享同一内存单元。
  • 类似的还有随机访问 v.at(i) 和数组运算符 v[i]，也可以赋值给别名变量或普通变量。
• vector 作为函数的参数或者返回值时，必须用 & 传引用调用：
  • vector<int>& Func(vector<int> &v){return v;}
  • 注意普通数组传引用调用时需要带个数：(int (&a)[10])，传指针不需要：(int *a) 或 (int a[])
• 能够存放任意类型，意味着可以嵌套其他数据结构：
  • 定义二维动态数组：vector<vector<int>> v;
  • 定义静态数组内一维动态数组：vector<int> a[100];，可用于邻接表。
  • 定义结构体数组：vector<Student> v;，结构体需要全局定义。
  • 两个存放相同类型元素的向量可以使用比较运算符，依据字典序逐个比较。
• vector 的 push_back() 代价虽然是均摊的 O(1)，但是当数据量大的时候会很慢。所以如果需要使用的话，可以用 vector<int> v(n); 初始化再赋值。
• 批量赋递增值：iota(v.begin(), v.end(), 0);，其中 0 代表首个元素值，赋值后的向量元素为 \(\{0, 1, 2,\cdots\}\)。常用于不改变原数组顺序的伪排序。
  • sort(idx.begin(), idx.end(), [&](int i, int j) { return nums[i] < nums[j]; });
• 在 Class 中初始化成员变量定长 vector 时，如果用 vector<int> v(5); 会报错，编译器无法识别语句是成员变量声明还是成员函数声明。必须用赋值构造函数 vector<int> v = vector<int> (10005, 0);。
  • 如果想要动态设置数组节省空间，且不用到 malloc 分配，可以先在 Class 中直接创建 vector<int> v;，再到函数内重设大小 v.resize(nums.size())。
  • 最好的办法是使用全局静态变量声明数组，static const int N = 1e5 + 6; int a[N];，这句话如果放到 Class 里面则数组是随机初始化，必须 memset(a, 0, sizeof(a));。

配对 | pair

pair 可以将两个任意类型的元素绑定成一组元素，其内部实现就是一个 template<class T1,class T2> 的结构体。可以用来组成更高级的映射 map，也可以用来表示坐标等双元素的结构体。当一个函数需要返回两个数据的时候，可以选择 pair。

基础操作

• 头文件 #include<utility>
• 创建 pair 对象：
  • 直接创建：pair<int,int> p;（实际中通常会 typedef pair<int,int> pii;）
  • 创建并赋值：pair<int,int> p(3,4);
  • 使用 C++ 括号运算符赋值：pair<int,int> p = {3，4};
  • 先创建后赋值：p = make_pair(3,4);
• 访问对象：
  • 等价于结构体变量：cout << p.first << ' ' << p.second;（注意不是指针）
• 嵌套：
  • 三元 pair：pair<int, pair<int, int>> p(1,{2,3});
  • 其他容器：vector<pair<int, int>>（实际中通常会 vector<pii> v）

特殊性质

• 在某些情况函数想要返回两个数据时，可以将 pair 对象作为返回值，此时函数外接收的对象可以是 pair，也可以直接通过 std::tie 进行接收：

  pair<string, int> getPreson() {
  	return make_pair("Steve", 25);
  }
  int main() {
  	string name; int ages;
  	tie(name, ages) = getPreson(); // 类似 Python 中的元组解包
  	cout << "name: " << name << ", ages: " << ages << endl;
  	return 0;
  }

元组 | tuple

C++11 引入的 tuple 可以将多个任意类型的元素绑定成一组元素，是泛化的 pair。通常将其当作一个简易的结构体使用，避免复杂的声明，用法与 pair 非常类似。

基础操作

• 头文件 #include<tuple>
• 创建 tuple 对象：
  • 直接创建：tuple<int,int,int> tup;
  • 创建并赋值：tuple<int,int,int> tup(1, 2, 3);
  • 创建并使用函数赋值：tuple<int,int,int>tup = make_tuple(1, 2, 3); 和 pair 不同，这里的创建步骤不能省略！
• 访问对象（注意不要漏掉括号）：
  • get 函数：cout << get<0>(tup) << ' '<< get<1>(tup);，返回的是元素的引用，因此可以修改
• 元组解包：
  • 主动声明变量：tie(a, b, c) = tup;
  • 自动声明变量：auto& [a, b, c] = tup; 如果某个元素不需要用到，可以用 _ 代替
• 嵌套到其他容器（以向量为例）：
  • 声明：vector<tuple<int, int, int>> tups;
  • 插入：tups.push_back(make_tuple(1, 2, 3)) 或 tups.emplace_back(1, 2, 3);

映射 | map

map 是一个存放一对一映射（pair）的关联容器，存储的关键字和值可以定义为任意类型，各个键值对的键互不相同且不允许被修改，但值可以相同。

map 的内部实现为红黑树（弱平衡二叉树），是二叉搜索树的升级版，具有对数据进行排序的功能。因此我们可以认为 map 内部所有键值对都是按 key 排序的，key 必须为可排序的类型（包括自定义类型）。

需要强调的是，map 中对元素增删改查的时间复杂度都是 \(O(\log n)\)，但使用迭代器遍历 map 的复杂度是 \(O(n)\)。

基础操作

• 头文件 #include<map>

• 创建 map 对象：

  • 直接创建：map<string,int> mp;
  • 创建并初始化：map<string,int> mp={{"A", 10}, {"B", 20}, {"C", 30}};

• 插入元素：

  • 用 insert 函数插入 pair：mp.insert(pair<string, int>("hw", 2001)); 通常会结合 typedef 简化；
  • 前者也可以用 make_pair 替换：mp.insert(make_pair("hw", 2001));
  • C++ 11 标准支持花括号初始化：mp.insert({"hw", 2001});
  • 用 insert 函数插入 value_type 数据：mp.insert(map<string, int>::value_type("hw", 2001));
  • 用数组运算符访问并插入（最常用）：mp[“hw”]=2001;，此时不受唯一性限制，可以覆盖已有的键值对；

• 删除元素（erase 函数）：

  • 删除迭代器指向元素：auto it=mp.find("hw"); mp.erase(it);
  • 删除关键字：bool flag = mp.erase("hw"); 如果找到并删除则返回 1，否则返回 0
  • 删除迭代器指向区间元素：mp.erase(++mp.begin(), mp.end());

• 特性函数：

  • 键值对数目：mp.size()
  • 清空：mp.clear();
  • 判断空：mp.empty()

• 访问元素：

  • 随机访问成员：mp.at("hw")，返回元素的引用，如果访问到未知元素会抛出异常。

  • 数组运算符访问：cout << mp["hw”];，返回元素的引用，如果访问到未知元素会返回一个全零的空值！

  • 查找元素：auto it=mp.find("hw"); 返回指向元素的迭代器，如果没找到，则返回 mp.end()；此外，如果想判断一个元素是否存在，可以直接 mp.count("hw") != 0，该值在 map 和 set 中只能为 0 或 1。

  • 迭代访问：

    // 声明迭代器，此时的 it 类似结构体指针
    map<string,int>::iterator it; 				// 这里可以换成 auto
    for(it=mp.begin(); it!=mp.end(); it++)
        cout<<it->first<<' '<<it->second<<endl; // 不能直接 * 访问
    
    // C++11 新语法，此时的 item 类似结构体
    for(auto &item: mp)
        cout<<item.first<<' '<<item.second<<endl; // 结构体直接用 . 访问属性
    
    // 反向迭代访问
    map<string,int>::reverse_iterator it;
    for(it = mp.rbegin(); it != mp.rend(); it++)
        cout<<it->first<<' '<<it->second<<endl;

特殊性质

• map、set、multimap、multiset 的迭代器是没有加减法的，仅支持自增 it++、自减 it-- 的操作，不支持 it+1、mp.begin()+1 操作。这是因为这些容器采用了特殊的数据结构，没有「两个元素之距离」的概念。
• 采用迭代器遍历 map、set 的复杂度是 \(O(n)\)，这是因为二叉树的遍历是 \(O(E)\)，每一条边只会被自上而下、自下而上各访问一次。
• 由于内部有序，map 和 set 支持 mp.lower_bound(key) 、mp.upper_bound(key)、equal_range(key) 运算，返回指向特定结构体的迭代器指针。但是考虑到 map 和 set 中都不会有重复的 key，此方法在 multimap、multiset 更常用。
• map 和 set 的插入删除，并不会使已经赋值的 iterator 失效，这是因为插入删除不会改变内部的树结构，不需要进行内存拷贝和移动；但是对于 vector 而言，每次插入删除都可能使其失效，即使是调用 push_back 的尾部插入，除了因为连续存放导致的内存平移，还可能涉及到容量倍增等操作。牢记一个原则：不要使用过期的迭代器。
• map 的关键字可以是 pair，例如 map<pair<int, int>, int> m，但是 unordered_map 却不能使用 pair 当关键字，因为 C++ 没有给 pair 的哈希函数，强行使用会报错。

哈希表 | unordered_map

如果只是需要一个映射关系，而不需要其有序，可以用 unordered_map。和 map 容器相似，unordered_map 同样以键值对（pair）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。

无序映射的底层采用哈希表存储结构，根据键的 hash 值来判断元素是否相同，不具有对数据的排序功能，但可以实现 \(O(1)\) 查找、插入。由于无序，不支持 lower_bound() 和 upper_bound() 等方法。

常用的操作与 map 类似：

• 头文件 #include<unordered_map>

• 创建 unordered_map 对象：unordered_map<string,int> hash;

• \(O(1)\) 插入元素（最常用）：hash["ABC"]=5;

• \(O(1)\) 查询元素（最常用）：int n=hash["ABC"]; 或 it->second（前提是 it != hash.end()）

• 判断关键字是否存在：hash.count("ABC") != 0 或 hash.find("ABC") != hash.end()，前者更为常用。

• 迭代访问（较少用）：

  // 声明迭代器，此时的 it 为结构体指针
  unordered_map<string,int>::iterator it;
  for(it=hash.begin(); it!=hash.end(); it++)
      cout<<it->first<<' '<<it->second<<endl;
  
  // C++11 新语法，此时的 item 为结构体
  for(auto item: hash)
      cout<<item.first<<' '<<item.second<<endl;

如果想让自定义的 class 作为 key 来使用 unordered_map，则还自行需要实现：重载哈希函数、判断两个 class 变量是否相等的函数（重载等价运算符）。

关于重载哈希函数，有一个 CF 上的经典案例，由于 unordered_map 常数较大，且 hash 具有规律，有的人就专门根据 STL 的源码来造 hack 数据，导致单次复杂度退化为 \(O(n)\)。为此，可以重载哈希函数，让其与时间戳有关，就无法被 hack 了。

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		return x; 
	}
	size_t operator () (uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
		return splitmix64(x + FIXED_RANDOM);
	}
};
unordered_map<uint64_t, int, custom_hash> safe_map;

哈希集合 unordered_set 有时也会用到，方法类似，不再单独介绍。

multimap

具有和 map 相同的诸多特性，最主要的区别在于，multimap 容器中可以同时存储多个键相同的键值对。

和 map 相比，multimap 未提供 at() 成员方法，也没有重载 [] 运算符。这意味着，map 容器中通过指定键获取键值对的方式，将不再适用于 multimap 容器。其实这很好理解，因为 multimap 容器中指定的键可能对应多个键值对，而不再是 1 个。

值的一提的是，由于 multimap 可存储多个具有相同键的键值对，因此 lower_bound()、upper_bound()、equal_range() 以及 count() 方法会经常用到。

集合 | set

set 是一个存放同一类型元素的集合容器，满足数学定义上集合的互异性——即 set 中每个元素只能出现一次。其内部实现也为红黑树，因此能根据元素的值自动进行排序。

set 中对元素增删改查的时间复杂度都是 \(O(\log n)\)，但使用迭代器遍历 set 的复杂度是 \(O(n)\)。

基础操作

• 头文件 #include<set>

• 创建 set 对象：

  • 直接创建：set<int> st;
  • 创建并初始化：set<int> st={1, 2, 3, 4};
  • 创建并拷贝：set<int> new_st(st);

• 插入、删除元素：

  • 插入一个元素：st.insert(3);
  • 删除一个元素：st.erase(3);
  • 删除迭代器指向元素：auto it=st.find(3); st.erase(it);
  • 删除区间内的元素：st.erase(++st.begin(), st.end());

• 特性函数：

  • 元素个数：st.size();
  • 清空集合：st.clear();
  • 判断空：st.empty();

• 访问元素：

  • 查找元素：auto it=st.find("hw"); 返回指向元素的迭代器，如果没找到，则返回 st.end()；此外，如果想判断一个元素是否存在，可以直接 st.count("hw") != 0，该值在 map 和 set 中只能为 0 或 1。

  • 有序性：st.lower_bound(2)、st.upper_bound(2)，返回指向特定结构体的迭代器指针。

  • 迭代访问：

    // 声明迭代器，此时的 it 类似指针
    for(auto it=st.begin(); it!=st.end(); it++)
        cout<<*it<<endl; 	// 访问指针指向的元素，有 *
    
    // C++11 新语法，此时的 item 为元素本身
    for(auto &item: st)
        cout<<item<<endl; 	// 不需要 *

特殊性质

• map 和 set 本身都是以升序排列，但是对于 set 而言有时候会改变其排序的方式，也可能引入结构体，因此需要用到自定义比较函数：

  // 元素不是结构体，重载 () 运算符
  struct cmp{
  	bool operator()(const T &a, const T &b){
  		return a.data > b.data;
      }
  }
  set<T, cmp> st;
  
  // 元素是结构体，直接将比较函数写在结构体内
  struct Info{
  	string name;
  	float score;
  	// 重载 < 操作符，自定义排序规则	
      bool operator < (const Info &a) const{
  		// 按 score 从大到小排列
          return a.score < score;
      }
  }
  set<Info> s;

multiset

multiset 使用频率相对较低，其和 set 的区别在于，multiset 容器中可以同时存储多个相同的元素，不再有互异性。

但是由于 set 结构的有序性，当我们需要一个「时刻有序的数组」时，支持 \(O(\log n)\) 地插入、删除、修改数组元素后依然保持有序，multiset 就会派上用场。经常结合 lower_bound()、upper_bound() 使用。

栈 | stack

从一段进栈，从同一端出栈，满足后进先出（LIFO）。

基础操作

• 头文件 include<stack>
• 创建 stack 对象：stack<int> s;
• 操作元素：
  • 栈顶压入元素：s.push(x);
  • 栈顶弹出元素：s.pop();，注意此时没有返回值；
  • 返回栈顶元素：s.top()，返回元素的引用，因此可以直接修改。
• 特性函数：
  • 栈长度：s.size()
  • 判断栈空：s.empty()
  • 注意队列和栈都没有 clear 函数，想要清空只能重新初始化：q = queue<int> ();

特殊性质

• 当栈为空的时候，如果调用 s.top() 则出现数组越界报错，解决办法是在使用该方法前加一个栈空判断：!s.empty() && s.top()。该方法同样适用于队列、向量等容器。
• C++11 新增 s.emplace(x) 操作，用于在栈顶生成元素，参数为直接对象时相当于 s.push(x)，区别在于当参数为构造函数对象时，例如 s.push(data(x,y)) 和 s.emplace(data(x,y)) 时，此时后者可以简化为 s.emplace(x,y)。

队列 | queue

从一端入队，从另一端出队，满足先进先出（FIFO）的结构。普通的队列基于链表结构实现，而优先队列基于堆结构实现。

基础操作

• 头文件 #include<queue>
• 创建 queue 对象：queue<int> q;
• 操作元素：
  • 队尾插入元素：q.push();
  • 队首弹出元素：q.pop();，注意此时没有返回值；
  • 返回队首元素：q.front()，返回元素的引用，因此可以直接修改；
  • 返回队尾元素：q.back()，返回元素的引用，因此可以直接修改。
• 特性函数：
  • 队列长度：q.size();
  • 判断队空：q.empty();
  • 注意队列和栈都没有 clear 函数，想要清空只能重新初始化：q = queue<int> ();

优先队列 | priority_queue

利用自带的优先队列可以实现最大堆和最小堆，其头文件和队列相同，特性函数也相同。此时优先级最高的先出队，默认情况下优先级就是「整数的大小」。出入队的复杂度为 \(O(\log n)\)，\(n\) 为队列的大小。下面介绍基础的用法：

• 创建 priority_queue 对象：
  • 优先队列有三个参数，其声明形式为：priority_queue<类型, vector<类型>, less<类型>>，后两个参数可以省略，第一个参数不能省略，三个 类型 保持一致。
  • 构建最大堆（大顶堆）：priority_queue<int> max_heap; 或 priority_queue<int,vector<int>,less<int>> max_heap;
  • 构建最小堆（小顶堆）：priority_queue<int,vector<int>,greater<int>> min_heap;
• 操作元素：
  • 在完全二叉树的底部插入元素，并上浮到相应位置：heap.push();
  • 从堆顶弹出元素，并填充二叉树底部元素，然后下滤到相应位置：heap.pop();
  • 返回堆顶元素：heap.top()，注意和普通队列的区别！

如果想自定义其他优先级，则需要在自定义结构体 cmp 中重载括号运算符 ()，使其变成仿函数（Functor），并替换 less<类型>：

struct cmp{
	bool operator()(const T &a, const T &b){
		return a.data < b.data;
    }
};
priority_queue<T, vector<T>, cmp> heap; 

或者在主函数外自定义比较函数 cmp（类似 sort 的写法），再用 decltype 进行类型自动推断（转为仿函数）：

static bool cmp(T &a, T &b){
	return a.data > b.data;
}
priority_queue<T ,vector<T>, decltype(&cmp)> heap(cmp);

双端队列 | deque

具备栈和队列的功能，但是操作要慢一点（常数级）。在实际使用中可以和 vector 类比，vector 的优势是对中间的操作速度快（例如索引遍历、迭代器遍历），deque 优势是对首端的操作速度快（例如删除头部）。在对尾端操作上（例如尾端插入），二者速度相仿。

在实际应用中，常用于实现单调队列、滑动窗口等算法。

基础操作

• 头文件 #include <deque>
• 创建 deque 对象：deque<int> dq;
• 操作元素：
  • 返回队首元素：dq.front();
  • 返回队尾元素：dq.back();
  • 队首插入一个元素：dq.push_front();
  • 队尾插入一个元素：dq.push_back();
  • 队首弹出一个元素：dq.pop_front();
  • 队尾弹出一个元素：dq.pop_back();
• 特性函数：
  • 双端队列长度：dq.size();
  • 判断队空：dq.empty();
  • 清空队列：dq.clear();
  • 返回指向第一个元素和最后一个元素的指针（只能赋值给迭代器）：v.begin()、 v.end()

双向链表 | list

非常少用的容器，底层采用双向链表的形式实现，元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。常配合哈希表存储链表节点指针，实现 \(O(1)\) 的插入、删除中间节点。

基础操作

• 头文件 #include <list>
• 创建 list 对象：
  • 直接创建：list<int> ls;
  • 创建含有 n 个元素且全 0 的对象：list<int> ls(n);
  • 创建含有 n 个元素 a 的对象：list<int> ls(n,a);
• 创建一个辅助哈希表：
  • unordered_map<int, list<int>::iterator> table;
• 插入、删除元素：
  • 尾部插入元素：ls.push_back(a); 或 ls.emplace_back(a);
  • 尾部删除元素：ls.pop_back();
  • 首部插入元素：ls.push_front(a); 或 ls.emplace_front(a);
  • 首部删除元素：ls.pop_front();
  • 在指定元素之前插入元素，插入后的元素就在该位置：ls.insert((ls.begin()+i, a)
  • 删除指定元素：ls.erase(ls.begin()+2)
• 迁移元素：
  • 从 ls2 中删除迭代器 it 所指的元素，并插入到 ls1 的首部：ls1.splice(ls1.begin(), ls2, it);
• 特性函数：
  • 链表长度：ls.size();
  • 判断空：ls.empty();
• 访问元素：
  • ls.front() 和 ls.back() 返回第一个和最后一个元素的引用
  • ls.begin() 和 ls.end() 返回指向第一个和最后一个元素的迭代器