基础算法

快速排序


xxxxxxxxxx
13
1
void quick_sort(int q[],int l,int r)
2
{
3
    if(l>=r) return;
4
    int x=q[l],i=l-1,j=r+1;
5
    while(i<j)
6
    {
7
        do i++; while(q[i]<x);
8
        do j--; while(q[j]>x);
9
        if(i<j) swap(q[i],q[j]);
10
    } 
11
    quick_sort(q,l,j);
12
    quick_sort(q,j+1,r);
13
}

高精度


xxxxxxxxxx
14
1
vector<int> add(vector<int> &A,vector<int> &B)
2
{
3
    vector<int> C ;
4
    int t=0;//t表示进位
5
    for(int i=0;i<A.size()||i<B.size();i++)
6
    {
7
        if(i<A.size()) t+=A[i];
8
        if(i<B.size()) t+=B[i];
9
        C.push_back(t%10);
10
        t/=10;
11
    }
12
    if(t) C.push_back(1);
13
    return C;
14
}

前缀和

一维前缀和


xxxxxxxxxx
24
1
#include <iostream>
2
using namespace std;
3

4
const int N=100010;
5

6
int n,m;
7
int a[N],s[N];
8

9
int main(){
10
    // ios::sync_with_stdio(false);//提高cin读取速度
11
    
12
    scanf("%d%d",&n,&m);
13
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
14
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//前缀和初始化
15
    
16
    while(m--)
17
    {
18
        int l,r;
19
        scanf("%d%d",&l,&r);
20
        printf("%d\n",s[r]-s[l-1]);//区间和的计算
21
    }
22
    
23
    return 0;
24
}//前缀和主要记住推导公式，一维和二维同理

二维前缀和


xxxxxxxxxx
29
1
#include <iostream>
2
using namespace std;
3

4
const int N=1010;
5

6
int n,m,q;
7
int a[N][N],s[N][N];
8

9
int main(){
10
    // ios::sync_with_stdio(false);//提高cin读取速度
11
    
12
    scanf("%d%d%d",&n,&m,&q);
13
    for(int i=1;i<=n;i++)
14
        for(int j=1;j<=m;j++)
15
            scanf("%d",&a[i][j]);
16
    
17
    for(int i=1;i<=n;i++)
18
        for(int j=1;j<=m;j++)
19
           s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//求前缀和
20
    
21
    while(q--)
22
    {
23
        int x1,y1,x2,y2;
24
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
25
        printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);//算子矩阵的和
26
    }
27
    
28
    return 0;
29
}//前缀和主要记住推导公式，一维和二维同理

双指针


xxxxxxxxxx
41
1
//所有双指针算法的复杂度都是可以优化到O(n)的
2
/*核心思想：
3
  for(int i=1;i<n;i++)
4
     for(int j=0;j<n;j++)
5
        O(n^2)
6
*/
7
//一个简单案例
8

9
#include <iostream>
10
#include <vector>
11
#include <algorithm> // for std::max
12
using namespace std;
13

14
const int N = 100010;
15

16
int main() {
17
    int n;
18
    cin >> n;
19
    
20
    vector<int> a(n); // 使用vector代替动态数组
21
    vector<int> s(N, 0); // 初始化s数组
22
    
23
    for (int i = 0; i < n; i++) {
24
        cin >> a[i]; // 读取输入
25
    }
26
    
27
    int res = 0; // 初始化res
28
    
29
    for (int i = 0, j = 0; i < n; i++) {
30
        s[a[i]]++; // a[i]对应指针滑动
31
        while (s[a[i]] > 1) {
32
            s[a[j]]--; // 当出现重复数据时，a[j]对应指针向后滑动
33
            j++;
34
        }
35
        res = max(res, i - j + 1);
36
    }
37
    
38
    cout << res << endl;
39
    
40
    return 0;
41
}

位运算


xxxxxxxxxx
7
1
/*n的二进制表示中第k位是几
2
1.先把第k位移到最后一位 n>>k（右移）
3
2.看个位是几（二进制时的个位  n>>k&个位数字）
4
*/
5

6
//lowbit(x):返回x的最后一位1及其最后几个0
7
//表达式 x & -x 用于获取整数 x 的最低有效位（Least Significant Bit, LSB），即二进制表示中最右边的 1。

离散化


xxxxxxxxxx
91
1
//alls.erase(unique(alls.begin(),alls.end()),alls.end());去掉重复元素
2

3
vector<int> alls;//存储所有待离散化的值
4
sorts(alls.begin(),alls.end());//将所有值排序
5
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去掉重复元素
6

7
//二分求出x对应的离散化的值
8
int find(int x)//找到第一个大于等于x的位置
9
{
10
    int l=0;r=alls.size()-1;
11
    while(l<r){
12
        int mid =l+r>>1;
13
        if(alls[mid]>=x) r=mid;
14
        else l=mid+1;
15
    }
16
    return r+1;//映射到1，2......n
17
}
18

19

20
//离散化求区间和
21

22
#include <iostream>
23
#include <vector>
24
#include <algorithm>
25

26
using namespace std;
27

28
typedef pair<int, int> PII;
29

30
const int N = 300010;
31

32
int n, m;
33
int a[N], s[N];
34

35
vector<int> alls;
36
vector<PII> add, query;
37

38
// 找到第一个大于等于x的位置
39
int find(int x) {
40
    int l = 0, r = alls.size() - 1;
41
    while (l < r) {
42
        int mid = l + r >> 1;
43
        if (alls[mid] >= x) r = mid;
44
        else l = mid + 1;
45
    }
46
    return r + 1; // 映射到1, 2, ..., n
47
}
48

49
int main() {
50
    cin >> n >> m;
51
    
52
    // 处理插入操作
53
    for (int i = 0; i < n; i++) {
54
        int x, c;
55
        cin >> x >> c;
56
        add.push_back({x, c});
57
        alls.push_back(x);
58
    }
59
    
60
    // 处理查询操作
61
    for (int i = 0; i < m; i++) {
62
        int l, r;
63
        cin >> l >> r;
64
        query.push_back({l, r});
65
        alls.push_back(l);
66
        alls.push_back(r);
67
    }
68
    
69
    // 去重并排序
70
    sort(alls.begin(), alls.end());
71
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
72
    
73
    // 处理插入
74
    for (auto item : add) {
75
        int x = find(item.first);
76
        a[x] += item.second;
77
    }
78
    
79
    // 预处理前缀和
80
    for (int i = 1; i <= alls.size(); i++) {
81
        s[i] = s[i - 1] + a[i];
82
    }
83
    
84
    // 处理询问
85
    for (auto item : query) {
86
        int l = find(item.first), r = find(item.second);
87
        cout << s[r] - s[l - 1] << endl;
88
    }
89
    
90
    return 0;
91
}

区间合并


xxxxxxxxxx
46
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
typedef pair<int,int> PII;
8

9
const int N=100010;
10

11
int n;
12
vector<PII> segs;
13

14
void merge(vector<PII> &segs)
15
{
16
    vector<PII> res;
17
    sort(segs.begin(),segs.end());
18
    int st=-2e9,ed=-2e9;
19
    for(auto seg:segs)
20
        if(ed<seg.first)
21
        {
22
            if(st!=-2e9) res.push_back({st,ed});
23
            st=seg.first,ed=seg.second;
24
        }
25
        else ed=max(ed,seg.second);
26
    
27
    if(st!=-2e9) res.push_back({st,ed});
28
    
29
    segs=res;
30
}
31

32
int main()
33
{
34
    cin>>n;
35
    
36
    for(int i=0;i<n;i++)
37
    {
38
        int l,r;
39
        cin>>l>>r;
40
        segs.push_back({l,r});
41
    }
42
    
43
    merge(segs);
44
    
45
    cout<< segs.size()<<endl;
46
}

数据结构

Trie树


xxxxxxxxxx
46
1
//快速存储和查找字符串集合的数据结构
2
//Trie字符串插入和统计
3
#include<iostream>
4

5
using namespace std;
6

7
const int N=100010;
8

9
int son[N][26],cnt[N],idx;
10

11
void insert(char str[])
12
{
13
    int p=0;
14
    for(int i=0;str[i];i++)
15
    {
16
        int u=str[i]-'a';
17
        if(!son[p][u]) son[p][u]=++idx;
18
        p=son[p][u];
19
    }
20
    cnt[p]++;
21
}
22

23
int query(char str[])
24
{
25
    int p=0;
26
    for(int i=0;str[i];i++)
27
    {
28
        int u=str[i]-'a';
29
        if(!son[p][u]) return 0;
30
        p=son[p][u];
31
    }
32
    return cnt[p];
33
}
34

35
int main()
36
{
37
    int n;
38
    scanf("%d",&n);
39
    while(n--)
40
    {
41
        char op[2];
42
        scanf("%s%s",op,str);
43
        if(op[0]=='I') insert(str);
44
        else printf("%d\n",query(str));
45
    }
46
}

Hash表

存储结构


xxxxxxxxxx
99
1
//存储结构：开放寻址法（模的数取质数，且尽可能离2的幂远一些）；拉链法:k(下标)=(x%N+N)%N;
2
//字符串哈希方式
3
#include <iostream>
4
#include <list>
5
using namespace std;
6

7
// 定义哈希表的节点结构
8
struct HashNode {
9
    int key;
10
    int value;
11
    HashNode(int k, int v) : key(k), value(v) {}
12
};
13
class HashTable {
14
private:
15
    static const int TABLE_SIZE = 10; // 哈希表的大小
16
    list<HashNode> table[TABLE_SIZE]; // 使用链表数组存储哈希表的桶
17

18
    // 哈希函数，将键映射到哈希表的索引
19
    int hashFunction(int key) {
20
        return key % TABLE_SIZE;
21
    }
22

23
public:
24
    // 插入键值对
25
    void insert(int key, int value) {
26
        int index = hashFunction(key);
27
        for (auto& node : table[index]) {
28
            if (node.key == key) {
29
                node.value = value; // 如果键已存在，更新值
30
                return;
31
            }
32
        }
33
        table[index].push_back(HashNode(key, value)); // 否则，插入新节点
34
    }
35

36
    // 查找键对应的值
37
    int search(int key) {
38
        int index = hashFunction(key);
39
        for (auto& node : table[index]) {
40
            if (node.key == key) {
41
                return node.value; // 找到键，返回对应的值
42
            }
43
        }
44
        return -1; // 未找到键，返回-1
45
    }
46

47
    // 删除键值对
48
    void remove(int key) {
49
        int index = hashFunction(key);
50
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
51
            if (it->key == key) {
52
                table[index].erase(it); // 找到键，删除对应的节点
53
                return;
54
            }
55
        }
56
    }
57

58
    // 打印哈希表
59
    void printTable() {
60
        for (int i = 0; i < TABLE_SIZE; ++i) {
61
            cout << "Bucket " << i << ": ";
62
            for (auto& node : table[i]) {
63
                cout << "(" << node.key << ", " << node.value << ") ";
64
            }
65
            cout << endl;
66
        }
67
    }
68
};
69

70
int main() {
71
    HashTable ht;
72

73
    // 插入键值对
74
    ht.insert(1, 100);
75
    ht.insert(2, 200);
76
    ht.insert(11, 1100); // 11和1会哈希到同一个位置
77
    ht.insert(12, 1200); // 12和2会哈希到同一个位置
78

79
    // 打印哈希表
80
    ht.printTable();
81

82
    // 查找键
83
    cout << "Search key 1: " << ht.search(1) << endl;
84
    cout << "Search key 11: " << ht.search(11) << endl;
85

86
    // 删除键
87
    ht.remove(11);
88
    cout << "After removing key 11:" << endl;
89
    ht.printTable();
90

91
    return 0;
92
}
93
/*在 main 函数中，我们创建了一个 HashTable 对象，并插入了一些键值对。
94

95
打印哈希表的内容，可以看到键值对如何被分配到不同的桶中。
96

97
查找并打印某些键对应的值。
98

99
删除一个键后，再次打印哈希表，观察删除操作的效果。*/

字符串哈希方式


xxxxxxxxxx
34
1
//字符串前缀哈希法
2
/*字符串前缀哈希（Prefix Hash）是一种常用的字符串处理技术，用于快速计算字符串的任意子串的哈希值。通过预处理字符串的前缀哈希值，可以在常数时间内计算任意子串的哈希值，常用于字符串匹配、子串比较等场景。
3

4
核心思想
5
预处理前缀哈希：
6

7
计算字符串的每个前缀的哈希值，并存储在一个数组中。
8

9
例如，对于字符串 s = "abcde"，可以计算 h[0] 到 h[5]，其中 h[i] 表示字符串 s[0..i-1] 的哈希值。
10

11
计算子串哈希：
12

13
利用前缀哈希数组，通过数学公式快速计算任意子串的哈希值。
14

15
避免哈希冲突：
16

17
选择一个合适的哈希基数和模数，尽量减少哈希冲突。
18

19
实现步骤
20
1. 选择哈希参数
21
基数（Base）：通常选择一个质数，如 131、13331 等。(P)
22

23
模数（Modulus）：通常选择一个较大的质数，如 10的9次方+7 或 2的64次方（利用无符号整型的自然溢出）。(Q)
24
2. 计算前缀哈希
25
定义前缀哈希数组 h 和基数幂数组 p。
26
递推计算：
27
h[i]=(h[i−1]×base+s[i−1])mod mod
28
p[i]=(p[i−1]×base)mod mod
29

30
(a*P^n+b*P^(n-1)+....f*P^0) mod Q
31

32
3. 计算子串哈希
33
对于子串 s[l..r]，其哈希值为：
34
hash=(h[r]−h[l−1]×p[r−l+1])mod mod


xxxxxxxxxx
47
1
#include <iostream>
2
#include <string>
3
#include <vector>
4
using namespace std;
5

6
typedef unsigned long long ULL; // 使用 unsigned long long 自然溢出作为模数
7

8
class PrefixHash {
9
private:
10
    string s;          // 原始字符串
11
    vector<ULL> h;     // 前缀哈希数组
12
    vector<ULL> p;     // 基数幂数组
13
    ULL base;          // 哈希基数
14
    ULL mod;           // 哈希模数
15

16
public:
17
    // 构造函数，初始化前缀哈希
18
    PrefixHash(const string& str, ULL base = 131, ULL mod = 1e18) 
19
        : s(str), base(base), mod(mod) {
20
        int n = s.size();
21
        h.resize(n + 1, 0);
22
        p.resize(n + 1, 1);
23

24
        // 计算前缀哈希和基数幂
25
        for (int i = 1; i <= n; i++) {
26
            h[i] = (h[i-1] * base + s[i-1]) % mod;
27
            p[i] = (p[i-1] * base) % mod;
28
        }
29
    }
30

31
    // 获取子串 s[l..r] 的哈希值
32
    ULL getHash(int l, int r) {
33
        return (h[r] - h[l-1] * p[r-l+1] % mod + mod) % mod;
34
    }
35
};
36

37
int main() {
38
    string s = "abcde";
39
    PrefixHash ph(s);
40

41
    // 计算子串哈希
42
    cout << "Hash of 'abc': " << ph.getHash(1, 3) << endl; // 输出 'abc' 的哈希值
43
    cout << "Hash of 'bcd': " << ph.getHash(2, 4) << endl; // 输出 'bcd' 的哈希值
44
    cout << "Hash of 'cde': " << ph.getHash(3, 5) << endl; // 输出 'cde' 的哈希值
45

46
    return 0;
47
}


xxxxxxxxxx
35
1
应用场景
2
字符串匹配：
3

4
快速比较两个字符串的子串是否相等。
5

6
例如，KMP 算法的优化版本中可以使用前缀哈希。
7

8
回文子串检测：
9

10
结合反向前缀哈希，可以快速检测子串是否是回文。
11

12
最长公共子串：
13

14
结合二分搜索和前缀哈希，可以高效求解最长公共子串问题。
15

16
滚动哈希：
17

18
在滑动窗口算法中，使用前缀哈希可以快速计算窗口内的哈希值。
19

20
    
21
    
22
注意事项
23
哈希冲突：
24

25
虽然前缀哈希可以减少冲突，但在极端情况下仍可能发生冲突。可以通过双哈希（使用两个不同的基数和模数）进一步降低冲突概率。
26

27
边界条件：
28

29
在计算子串哈希时，注意下标从 1 开始还是从 0 开始。
30

31
性能：
32

33
预处理时间复杂度为 O(n)，查询子串哈希的时间复杂度为 O(1)，适合处理大量查询的场景。
34

35
通过前缀哈希，可以高效地处理字符串的哈希计算问题，是算法竞赛和工程开发中的常用技巧。

STL

一、STL 的核心组成

STL是 C++ 标准库的一部分，主要包括以下四大组件：

容器（Containers）
- 存储元素的 data structures。
- 常用容器：vector, list, set, map, unordered_map, deque, stack, queue 等。
算法（Algorithms）
- 在容器上执行操作的函数模板，如排序、查找、遍历等。
- 常用算法：sort(), find(), count(), lower_bound() 等。
迭代器（Iterators）
- 用于遍历容器中元素的指针抽象，类似指针但更通用。
- 分类：输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。
函数对象（Functors）
- 可重用的函数封装，可作为算法的参数传递。
- 常用函数对象：greater<int>(), less_equal<T>()，或通过 lambda 表达式实现。

二、容器详解

1. 线性容器（Linear Containers）

(1) vector

特点：动态数组支持随机访问。

示例：


xxxxxxxxxx
9
1
#include <vector>
2
using namespace std;
3

4
int main() {
5
    vector<int> v = {1, 2, 3};
6
    v.push_back(4); // 添加元素
7
    cout << v[0] << endl; // 随机访问
8
    return 0;
9
}

(2) list

特点：双向链表，插入删除高效，不支持随机访问。

示例：


xxxxxxxxxx
10
1
#include <list>
2
using namespace std;
3

4
int main() {
5
    list<int> l = {1, 2, 3};
6
    l.insert(l.begin(), 0); // 插入头部
7
    for (auto it = l.begin(); it != l.end(); ++it)
8
        cout << *it << " ";
9
    return 0;
10
}

(3) deque

特点：双端队列，支持前后插入删除和随机访问。

示例：


xxxxxxxxxx
13
1
#include <deque>
2
using namespace std;
3

4
int main() {
5
    deque<int> dq = {1, 2, 3};
6
    dq.push_front(0);
7
    dq.push_back(4);
8
    while (!dq.empty()) {
9
        cout << dq.front() << " ";
10
        dq.pop_front();
11
    }
12
    return 0;
13
}

2. 关联容器（Associative Containers）

(1) set

特点：有序集合，元素唯一，基于红黑树实现。

示例：


xxxxxxxxxx
11
1
#include <set>
2
using namespace std;
3

4
int main() {
5
    set<int> s = {3, 1, 4};
6
    s.insert(2); // 自动排序
7
    auto it = s.find(3);
8
    if (it != s.end())
9
        cout << *it << endl;
10
    return 0;
11
}

(2) map

特点：键值对有序集合，键唯一。

示例：


xxxxxxxxxx
10
1
#include <map>
2
using namespace std;
3

4
int main() {
5
    map<string, int> m;
6
    m["Alice"] = 25;
7
    m["Bob"] = 30;
8
    cout << m["Alice"] << endl; // 输出 25
9
    return 0;
10
}

(3) unordered_set/unordered_map

特点：哈希表实现，无序，插入删除 O(1) 平均时间复杂度。

三、算法详解

1. 常用算法

(1) 排序


xxxxxxxxxx
9
1
#include <algorithm>
2
using namespace std;
3

4
int main() {
5
    vector<int> v = {3, 1, 4, 1, 5};
6
    sort(v.begin(), v.end()); // 升序排序
7
    for (int x : v) cout<< x << " ";
8
    return 0;
9
}

(2) 查找


xxxxxxxxxx
9
1
#include <algorithm>
2
using namespace std;
3

4
int main() {
5
    vector<int> v = {1, 2, 3, 4, 5};
6
    auto pos = lower_bound(v.begin(), v.end(), 3); // 第一个 >=3 的位置
7
    cout << *pos << endl; // 输出 3
8
    return 0;
9
}

(3) 遍历


xxxxxxxxxx
10
1
#include <algorithm>
2
using namespace std;
3

4
int main() {
5
    vector<int> v = {1, 3, 5, 7, 9};
6
    for_each(v.begin(), v.end(), [](int x) {
7
        cout<< x << " ";
8
    });
9
    return 0;
10
}

四、迭代器使用

1. 遍历容器


xxxxxxxxxx
13
1
#include <vector>
2
using namespace std;
3

4
int main() {
5
    vector<int> v = {1, 2, 3, 4, 5};
6
    // 使用范围 for 循环（需 C++11 支持）
7
    for (auto x : v) cout<< x << " ";
8
    
9
    // 使用迭代器
10
    for (auto it = v.begin(); it != v.end(); ++it)
11
        cout << *it << " ";
12
    return 0;
13
}

2. 反向迭代器


xxxxxxxxxx
11
1
#include <vector>
2
#include <iostream>
3
using namespace std;
4

5
int main() {
6
    vector<int> v = {1, 2, 3, 4, 5};
7
    // 反向遍历
8
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit)
9
        cout << *rit << " ";
10
    return 0;
11
}

五、函数对象与Lambda表达式

1. 函数对象


xxxxxxxxxx
15
1
#include <algorithm>
2
using namespace std;
3

4
struct Compare {
5
    bool operator()(int a, int b) {
6
        return a > b; // 降序排列
7
    }
8
};
9

10
int main() {
11
    vector<int> v = {3, 1, 4, 1, 5};
12
    sort(v.begin(), v.end(), Compare());
13
    for (int x : v) cout<< x << " ";
14
    return 0;
15
}

2. Lambda表达式


xxxxxxxxxx
8
1
#include <algorithm>
2
using namespace std;
3

4
int main() {
5
    vector<int> v = {3, 1, 4, 1, 5};
6
    sort(v.begin(), v.end(), [](int a, int b) { return a < b; });
7
    return 0;
8
}

六、STL内存管理

1. allocator


xxxxxxxxxx
11
1
#include <memory>
2
using namespace std;
3

4
int main() {
5
    allocator<int> alloc;
6
    int* ptr = alloc.allocate(5); // 分配原始内存
7
    alloc.construct(ptr, 42);     // 构造对象
8
    alloc.destroy(ptr);           // 销毁对象
9
    alloc.deallocate(ptr, 5);     // 释放内存
10
    return 0;
11
}

七、STL实际开发技巧

auto 关键字


xxxxxxxxxx
1
1
auto it = v.begin(); // 推断类型

范围 for 循环


xxxxxxxxxx
1
1
for (auto& x : v) cin >> x; // 避免拷贝

移动语义


xxxxxxxxxx
1
1
vector<string> v2 = move(v); // 转移资源所有权

八、常见问题

vector 和 list 的区别？
- vector：动态数组，支持随机访问，尾部插入删除快，中间慢。
- list：双向链表，中间插入删除快，不支持随机访问。
为什么用迭代器而不是指针？
- 迭代器抽象了容器的访问方式，兼容不同容器（如 vector 和 list）。
容器是否线程安全?
- 不安全，多线程环境下需手动加锁保护共享数据。

九、容器详细介绍

一、线性容器（Linear Containers）

1. vector

特点：动态数组，支持快速随机访问。

核心操作：


xxxxxxxxxx
16
1
#include <vector>
2
using namespace std;
3

4
vector<int> v;
5
// 插入元素
6
v.push_back(1);       // 尾部插入
7
v.insert(v.begin(), 2); // 指定位置插入
8
// 访问元素
9
cout << v[0] << endl;   // 随机访问 O(1)
10
cout << v.front() << endl; // 头部元素
11
cout << v.back() << endl;  // 尾部元素
12
// 删除元素
13
v.pop_back();           // 删除尾部
14
v.erase(v.begin());     // 删除指定位置
15
// 遍历
16
for (int x : v) cout<< x << " ";

适用场景：需要快速随机访问和尾部插入删除的场景（如动态数组）。

2. list

特点：双向链表，插入删除高效，无随机访问。

核心操作：


xxxxxxxxxx
16
1
#include <list>
2
using namespace std;
3

4
list<int> l;
5
// 插入元素
6
l.push_front(1);       // 头部插入
7
l.insert(l.end(), 2);    // 尾部插入
8
// 访问元素
9
cout << l.front() << endl;
10
cout << l.back() << endl;
11
// 删除元素
12
l.pop_front();           // 删除头部
13
l.erase(l.find(3));      // 删除指定值
14
// 遍历
15
for (auto it = l.begin(); it != l.end(); ++it) 
16
    cout << *it << " ";

适用场景：频繁中间插入删除的场景（如链表操作）。

3. deque

特点：双端队列，支持前后插入删除和随机访问。

核心操作：


xxxxxxxxxx
15
1
#include <deque>
2
using namespace std;
3

4
deque<int> dq;
5
// 插入元素
6
dq.push_front(1);       // 头部插入
7
dq.push_back(2);        // 尾部插入
8
// 访问元素
9
cout << dq[0] << endl;   // 随机访问
10
cout << dq.front() << endl;
11
// 删除元素
12
dq.pop_front();           // 删除头部
13
dq.pop_back();            // 删除尾部
14
// 遍历
15
for (int x : dq) cout<< x << " ";

适用场景：需要双端操作的队列或栈（如滑动窗口）。

二、关联容器（Associative Containers）

1. set

特点：有序集合，元素唯一，基于红黑树实现。

核心操作：


xxxxxxxxxx
13
1
#include <set>
2
using namespace std;
3

4
set<int> s;
5
// 插入元素
6
s.insert(1);
7
s.insert(3);
8
// 查询元素
9
if (s.count(2)) cout << "存在" << endl;
10
// 遍历
11
for (int x : s) cout<< x << " "; // 输出 1 3
12
// 删除元素
13
s.erase(1);

适用场景：需要元素唯一且有序的场景（如去重后的排序）。

2. map

特点：键值对有序集合，键唯一，基于红黑树实现。

核心操作：


xxxxxxxxxx
14
1
#include <map>
2
using namespace std;
3

4
map<string, int> m;
5
// 插入键值对
6
m["Alice"] = 25;
7
m["Bob"] = 30;
8
// 查询值
9
cout << m["Alice"] << endl; // 输出 25
10
// 删除键值对
11
m.erase("Bob");
12
// 遍历
13
for (auto& [k, v] : m) 
14
    cout<< k << ": "<< v << endl;

适用场景：需要键值对且有序存储的场景（如配置表）。

3. unordered_set/unordered_map

特点：哈希表实现，无序，插入删除 O(1) 平均时间复杂度。

核心操作：


xxxxxxxxxx
8
1
#include <unordered_set>
2
using namespace std;
3

4
unordered_set<int> us;
5
us.insert(1);
6
us.insert(3);
7
// 查询是否存在
8
if (us.find(2) != us.end()) cout << "存在" << endl;

适用场景：需要快速插入、删除和查询的场景（如哈希表）。

三、容器适配器（Container Adapters）

1. stack

特点：后进先出（LIFO），基于其他容器实现（默认 deque）。

核心操作：


xxxxxxxxxx
9
1
#include <stack>
2
using namespace std;
3

4
stack<int> st;
5
st.push(1);
6
st.push(2);
7
cout << st.top() << endl; // 输出 2
8
st.pop();
9
cout << st.size() << endl; // 输出 1

2. queue

特点：先进先出（FIFO），基于其他容器实现（默认 deque）。

核心操作：


xxxxxxxxxx
9
1
#include <queue>
2
using namespace std;
3

4
queue<int> q;
5
q.push(1);
6
q.push(2);
7
cout << q.front() << endl; // 输出 1
8
q.pop();
9
cout << q.back() << endl;  // 输出 2

3. priority_queue

特点：大顶堆（默认），可自定义比较器。

核心操作：


xxxxxxxxxx
8
1
#include <queue>
2
using namespace std;
3

4
priority_queue<int> pq; // 大顶堆
5
pq.push(3);
6
pq.push(1);
7
cout << pq.top() << endl; // 输出 3
8
pq.pop();

四、其他容器

1. multiset/multimap

特点：允许重复元素的有序集合（multiset）或键值对（multimap）。

核心操作：


xxxxxxxxxx
8
1
#include <multiset>
2
using namespace std;
3

4
multiset<int> ms;
5
ms.insert(2);
6
ms.insert(2);
7
// 输出所有 2
8
for (int x : ms) cout<< x << " "; // 2 2

2. bitset

特点：固定大小的位集合，高效存储位操作。

核心操作：


xxxxxxxxxx
6
1
#include <bitset>
2
using namespace std;
3

4
bitset<4> b;
5
b.set(0); // 设置第0位为1
6
cout << b.to_string() << endl; // 输出 0001

五、容器选型指南

需求	推荐容器	原因
快速随机访问	`vector`	O(1) 时间复杂度
频繁中间插入删除	`list`	O(1) 时间复杂度
双端操作	`deque`	支持前后高效操作
元素唯一且有序	`set`	红黑树保证顺序
键值对且有序	`map`	基于红黑树的键值对存储
快速哈希查询	`unordered_set`/`unordered_map`	平均 O(1) 时间复杂度
后进先出	`stack`	适配器模式简化实现

六、常见陷阱

vector 中间插入删除：时间复杂度为 O(n)，避免频繁操作。
unordered_map 的哈希冲突：合理设计哈希函数或使用 std::unordered_map 的默认实现。
set的重复元素：set 不允许重复，需用 multiset 存储重复元素。