【算法笔记】1. C++ 常用 STL

2021-02-12 2024-04-15 约 3000 字预计阅读 6 分钟

使用 C++ 进行算法刷题，实际用到的 C++ 特性很少，可以认为是 C plus STL。日常刷题需要熟练使用 STL，提高效率。本文简单小结常用的STL，详细内容看官方文档。

Data Structure

pair

pair 定义在 utility 库中，通常直接引入 iostream 即可

pair 排序先比较 first，在 first 相等时自动比较 second

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include<iostream>
/* 声明 */
pair<int,string> p;
pair<int, pair<int, int>> p;

/* 初始化 */
p = make_pair(1, "test");
p = {1, "test"};    // C++ 11

/* 取值 */
pair<TreeNode*, int> PTI;
stack<PTI> stk;
PTI p = stk.top(); stk.pop();
p.first;
p.second;
// 结构化绑定，将一个复合类型的元素解构为其各个成员变量 C++17
auto [t, color] = stk.top(); stk.pop();

char/string

char 类型判断

1
2
3
4
5


#include <iostream>
bool flag = isalnum(c)  // 判断字母和数字 alphanumeric 
bool flag = isalpha(c)  // 判断字母 alphabetic
bool flag = isdigit(c)  // 判断十进制数字 decimal digit
char low = tolower(c)   // 转换成小写

string 类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <iostream>
#include <cstring>
using namespace std;

int main() {
	// string str(5, 'A'); // 重复字符构造函数
    string s = "test";
    s += "-hello";
    s += '!'; 、// 添加一个字符

    s.size();
    s.length();
    s.front();
    s.back();

    s.append("zzz");
    s.append(10, 'x');  // 追加 10 个 x

    // 找到的第一个字符下标
    cout << s.find('-') << endl;        

    // 子串(起始位置, 长度) 长度默认到字符串结尾
    cout << s.substr(1, 3) << endl;
    cout << s.substr(1) << endl;

    // 逆序(本地修改)
    reverse(s.begin(), s.end());

    // 转成 const char * (第一个字符的地址)
    const char *p = s.c_str();
    cout << p << endl;
}

string、char*、int 转换

1
2
3
4
5
6
7
8
9


- int/float/double → string
	- to_string()
- string → int
    - stoi(str)
- char* → int
    - atoi(char *)
    - sscanf(str, "%d", &x);
- string → char*
	- c_str()

字符串分割

1
2
3
4
5
6
7
8
9


vector<string> split(const string str, const char delim) {
    vector<string> res;
    stringstream ss(str);
    string tmp;
    while (getline(ss, tmp, delim)) {
        res.push_back(tmp);
    }
    return res;
}

array/vector

数组（C++ 数组文档）

1
2
3
4
5
6
7
8


// 初始化
int dp[100][100][100];
memset(dp, 0, sizeof dp);

// 复制
bool dp[target+1];   
bool pre[target+1];
memcpy(pre, dp, sizeof dp);

vector

memset 无法初始化 vector，因为 memset 是内存块的初始化函数，适用于原始数据类型，如字符数组或整数数组

emplace_back 允许就地构造元素，避免了额外的复制或移动操作，面对自定义类型数据比 push_back 更高效

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


// 赋值-初始化
vector<int> arr = {1, 2, 3, 4, 5};

// 构造函数-初始化(设置大小)
vector<vector<int>> arr(row + 1, vector<int>(col + 1, 0));
vector f(m, vector(n, inf));

// 单独声明再赋值
vector<vector<int>> arr;
arr = vector<vector<int>>(m, vector<int>(n))
arr.resize(m, vector<int>(n));        // resize 设置大小
arr.resize(m, vector<int>(n, value)); // 可在 resize 中直接赋值
for (int i = 0; i < m; i++) {
	fill(arr.begin(), arr.end(), 0);
}

// 复制
vector<vector<double>> dp(N,vector<double>(N,0)); 
vector<vector<double>> pre;   //记录前一个step
pre = dp;

// 添加元素
std::vector<int> nums;
nums.push_back(0);
nums.emplace_back(1, 2, 3);  // 变长参数列表，可一次传入多个元素

// 清空
nums.clear();

// 遍历
for(int i = 0; i < nums.size(); i++) cout << nums[i] << " ";

for(vector<int>::iterator it = nums.begin(); it != nums.end(); it++) cout << *it << " ";
for(auto it = nums.begin(); it != nums.end(); it++) cout << *it << " ";

// C++ 11 的新特性, for each 遍历
for(auto n : nums) cout << n << " ";

list

list 是顺序容器的一种，是一个双向链表。

1
2
3
4
5
6


push_back()
pop_back()
void push_front(const T & val)
void pop_front()
void remove (const T & val)
void unique()	                 // 删除所有和前一个元素相等的元素

queue

queue 的 pop() 弹出队头元素，返回 void 值

queue 没有 clear 函数，清空直接重新构造一个 q = queue<int>()

1
2
3
4
5
6


#include <queue>

queue<int> q;
q.push(x)
q.back();
int top = q.front(); q.pop();

deque

双端队列 deque 是由一系列连续的存储块（称为缓冲区或节点）构成的，每个存储块都包含多个元素。与 vector 不同，deque 允许在两端进行快速的插入和删除操作，不会导致存储块的重新分配和元素的移动，时间复杂度为常数时间 $O(1)$。

deque 支持随机访问，但访问和修改任意位置的元素的时间复杂度会稍微高一些。速度比较慢，使用较少。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <deque>

deque<int> deq;
deq.push_front(x);
deq.push_back(x);

int n = deq.front();            // 不会弹出数据
int n = deq.back();             // 不会弹出数据

deq.pop_front();
deq.pop_back();

deq.clear();

// 支持随机寻址，支持begin()和end()迭代器
deq[0];

priority_queue

优先队列 priority_queue 本质是个堆，定义如下：

1
2
3
4
5
6
7


#include <queue>    // 注意在头文件 queue 中

// 默认大根堆（默认 less 比较函数，但结果上是从大到小的排序）
priority_queue<int> q;
 
// 小根堆（需要手动添加参数）
priority_queue<int, vector<int>, greater<int>> heap;

使用自定义结构需要定义排序函数： 1）比较函数使用一个单独的结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


struct Node {
    int val;
    ListNode* ptr;
};
struct Cmp {
    // 默认使用 < 运算，表示大根堆
    bool operator ()(const Node &a, const Node &b) const {
        return a.val > b.val;     // 小根堆 (greater 比较)
    } 
};
priority_queue<Node, vector<Node>, Cmp> heap; 

2）把比较的定义放在数据结构体里，重写 < 运算

1
2
3
4
5
6
7
8
9


struct Node {
    int val;
    ListNode* ptr;
    // 默认使用 < 运算，表示大根堆
    bool operator < (const Node &w) const {
        return val > w.val;     // 小根堆 (使用相反的比较语义)
    }
};
priority_queue<Node> heap;

优先队列（堆）的基本操作

1
2
3


heap.push();
heap.top();    // 返回堆顶元素
heap.pop();    // 弹出堆顶元素

stack

1
2
3
4
5


#include <stack>
stack<int> stk;
stk.push(); // 压栈
stk.top();  // 返回栈顶
stk.pop();  // 弹出栈顶

set/map

set/map 有两种存储结构：

set，map，multiset，multimap

基于平衡二叉树（红黑树），动态维护有序序列。支持跟排序相关的操作（如 lower_bound/upper_bound），也支持迭代器的++和–，但增删改查的时间复杂度是 $O(logn)$。
unordered_set，unordered_map，unordered_multiset，unordered_multimap

基于哈希表，无序，不支持跟排序相关的操作，也不支持迭代器的++和–。增删改查的时间复杂度是 $O(1)$。使用需引入对应的头文件 #include <unordered_map>。

set 操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <set>

set<int> s;         // 不能有重复元素, 插入一个重复元素, 则这个操作会被忽略
multiset<int> ms;   // 可以有重复元素

insert(x);
find(x);
count(x);   // 返回某个数的个数, set 返回0或1, multiset 可能返回大于1
erase(x);   // 删除所有值为 x 的元素
erase(it);

lower_bound(x); // 返回 >=x 的最小的数的迭代器
upper_bound(x); // 返回 <x 的最小的数的迭代器

map 操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


#include <map>

// 声明
map<int, int> mp;
mp.clear();    //清除所有元素

// 插入，更新，删除
mp.insert(make_pair(room_id, hot_value));   // 插入，避免更新现有键值对
mp[room_id] = hot_value;    // 更新（插入）
mp.erase(room_id);          // 删除，通过 key
mp.erase(pos);              // 删除 pos 迭代器所指的元素，返回下一个元素的迭代器
mp.erase(pos1, pos2);       // 删除区间 [pos1, pos2) 的所有元素，返回下一个元素的迭代器

// 查找
mp.find(a) != mp.end()      // 返回迭代器
mp.count(a) == 1            // 返回 0 1

// 遍历
for (auto& elem: mp) {
    cout << elem.first << ": " << elem.second;
}

// 结构化绑定 C++17
for (const auto& [key, val]: mp) {
    cout << key << ": " << val << endl;
}

// 迭代器遍历
for (map<int,int>::iterator it = count.begin(); it != count.end(); it++){
    if (it->second > Max){
        Max = it->second;
        k = it->first;
    }
}

Algorithm

sort

pair 排序在 first 相等时自动比较 second，vector 先比较第一个元素，相等则依次向后比较

默认排序顺序从小到大，也可以自定义排序策略

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


vector<int> nums = {5, 2, 9, 1, 3};

// 递增
sort(nums.begin(), nums.end());

// 递减
sort(nums.begin(), nums.end(), greater<int>());

// 自定义比较函数
bool cmp(int a, int b) {
    return a > b;
}

// class 中需要定义 static
class Solution {
public:
    static bool greatCmp (string a, string b) {
        return a + b > b + a;
    }
    // ...
};

sort(nums.begin(), nums.end(), cmp);
sort(nums.begin(), nums.end(), [](int a, int b) {
	return a > b;
});

vector 自定义排序示例

1
2
3
4
5
6
7
8
9


vector<vector<int>> nums;
// 按第一个数递减，第二个数递增
bool cmp(const vector<int>& a, vector<int>& b) {
	return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
}
sort(nums.begin(), nums.end(), cmp);
sort(nums.begin(), nums.end(), [](const vector<int>& a, const vector<int>& b) {
	return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});

upper_bound

1

int j = upper_bound(a+i+1, a+N, (long long)a[i] * p) - a;

unique

unique 依次检查当前元素与下一个元素是否相等。如果相等，将下一个不相等的元素移动到当前元素的位置，覆盖重复的元素。重复执行相等性检查和元素移动的过程，直到遍历完整个序列。

最后返回一个指向新的 逻辑尾部（即去除重复元素后的序列的末尾位置的下一个位置）的迭代器。通过使用该迭代器，可以确定去除重复元素后的序列的大小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


nums = {1,2,2,3,3,3,1,2,2,2,3,4,4,5,6};
int n = nums.size();
for (int x: nums) cout << x << " ";
cout << "\n";

auto it = unique(nums.begin(), nums.end());
for (int x: nums) cout << x << " ";
cout << "\n";
cout << it - nums.begin();
cout << "\n";

nums.erase(it, nums.end());
for (int x: nums) cout << x << " ";
cout << "\n";
/*
1 2 2 3 3 3 1 2 2 2 3 4 4 5 6 
1 2 3 1 2 3 4 5 6|2 3 4 4 5 6 
9
1 2 3 1 2 3 4 5 6 
*/

unique 只能移除相邻的重复元素，不能移除非相邻位置的重复元素，如果需要移除整个序列中的重复元素，可以先 sort 使相同元素相邻。

unique 并不会改变容器的大小，逻辑尾部 后续的元素没有改变，可配合 erase 去除这部分多余元素。

1
2
3
4
5


for (...) {
	sort(solution.begin(), solution.end());
}
sort(solutions.begin(), solutions.end());
solutions.erase(unique(solutions.begin(), solutions.end()), solutions.end());

自己实现 unique 函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// myunique(alls) <==> unique(alls.begin(), alls.end())
vector<int>::iterator myunique(vector<int> &a) {
    int j = 0;
    for (int i = 0; i < a.size(); i++) {    // a[0] ~ a[j - 1] 所有a中不重复的数
        if (!i || a[i] != a[i - 1]) {
            a[j++] = a[i];
        }
    }
    return a.begin() + j;                   // 返回去重后数组的末尾
}

收录于合集・算法笔记 14

【算法笔记】0.开篇【算法笔记】2.数据结构