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

本文最后更新于:2023年3月17日 晚上

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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 中基础的算法,大部分方法可以在容器中找到对应函数,例如不修改内容的 findcount 等操作,修改内容的 removereplaceswap 等操作,以及排序、二分查找、两数取最大最小、交换两数等算法。

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

  • __gcd(1024, 256);:求最大公约数,在 C++ 17 后也可以用 gcd(1024, 256);
  • 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.nposs.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 操作:
1
2
3
4
#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() 返回第一个和最后一个元素的引用

    • 迭代访问:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      // 声明迭代器,此时的 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 作为函数的参数或者返回值时,必须用 & 传引用调用
    • double Distance(vector<int> &a, vector<int> &b)
    • 注意普通数组传引用调用时需要带个数(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 进行接收:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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。

    • 迭代访问:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      // 声明迭代器,此时的 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+1mp.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"];

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

  • 迭代访问(较少用):

    1
    2
    3
    4
    5
    6
    7
    8
    // 声明迭代器,此时的 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 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
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),返回指向特定结构体的迭代器指针。

    • 迭代访问:

      1
      2
      3
      4
      5
      6
      7
      // 声明迭代器,此时的 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 而言有时候会改变其排序的方式,也可能引入结构体,因此需要用到自定义比较函数:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 元素不是结构体,重载 () 运算符
    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<类型>

1
2
3
4
5
6
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 进行类型自动推断(转为仿函数):

1
2
3
4
static bool comp(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() 返回指向第一个和最后一个元素的迭代器

算法入门笔记 #2 STL标准库
https://hwcoder.top/Algo-Note-2
作者
Wei He
发布于
2022年8月27日
许可协议