参考文章：

C++ STL详解超全总结(快速入门STL)-CSDN博客

1. vector

1.1 介绍

vector为可变长数组（动态数组），定义的vector数组可以随时添加数值和删除元素。

注意：在局部区域中（比如局部函数里面）开vector数组，是在堆空间里面开的。

在局部区域开数组是在栈空间开的，而栈空间比较小，如果开了非常长的数组就会发生爆栈。

故局部区域不可以开大长度数组，但是可以开大长度vector。

头文件：

1
#include <vector>

  • 一维初始化

    1
    2
    3
    vector<int> a; // 定义了一个名为a的一维数组,数组存储int类型数据
    vector<double> b;// 定义了一个名为b的一维数组，数组存储double类型数据
    vector<node> c;// 定义了一个名为c的一维数组，数组存储结构体类型数据，node是结构体类型

    指定长度和初始值的初始化

    1
    2
    3
    vector<int> v(n);// 定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1]
    vector<int> v(n, 1);// v[0] 到 v[n - 1]所有的元素初始值均为1
    // 注意：指定数组长度之后（指定长度后的数组就相当于正常的数组了）

    初始化中有多个元素

    1
    vector<int> a{1, 2, 3, 4, 5};// 数组a中有五个元素，数组长度就为5

    拷贝初始化

    1
    2
    3
    vector<int> a(n + 1, 0);
    vector<int> b(a); // 两个数组中的类型必须相同,a和b都是长度为n+1，初始值都为0的数组
    vector<int> c = a; // 也是拷贝初始化,c和a是完全一样的数组

  • 二维初始化
    定义第一维固定长度为5，第二维可变化的二维数组

    1
    2
    3
    vector<int> v[5];// 定义可变长二维数组
    // 注意：行不可变（只有5行）, 而列可变,可以在指定行添加元素
    // 第一维固定长度为5，第二维长度可以改变

    vector<int> v[5]可以这样理解：长度为5的v数组，数组中存储的是vector<int>数据类型，而该类型就是数组形式，故v为二维数组。其中每个数组元素均为空，因为没有指定长度，所以第二维可变长。可以进行下述操作：

    1
    2
    v[1].push_back(2);
    v[2].push_back(3);

    行列均可变

    1
    2
    // 初始化二维均可变长数组
    vector<vector<int>> v;// 定义一个行和列均可变的二维数组

    应用：可以在v数组里面装多个数组

    1
    2
    3
    4
    5
    vector<int> t1{1, 2, 3, 4};
    vector<int> t2{2, 3, 4, 5};
    v.push_back(t1);
    v.push_back(t2);
    v.push_back({3, 4, 5, 6}) // {3, 4, 5, 6}可以作为vector的初始化,相当于一个无名vector

    行列长度均固定 n + 1 行 m + 1 列初始值为0

    1
    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));

    c++17或者c++20支持的形式（不常用），与上面相同的初始化

    1
    vector a(n + 1, vector(m + 1, 0));

1.2 方法函数

知道了如何定义初始化可变数组，下面就需要知道如何添加，删除，修改数据。

c指定为数组名称，含义中会注明算法复杂度。

代码 含义 时间复杂度
c.front() 返回第一个数据 O(1)
c.back() 返回数组中的最后一个数据 O(1)
c.pop_back() 删除最后一个数据 O(1)
c.push_back(element) 在尾部加一个数据 O(1)
c.size() 返回实际数据个数（unsigned类型） O(1)
c.clear() 清除元素个数 O(N)
c.resize(n, v) 改变数组大小为n，n个空间数值赋为v，如果没有默认赋值为0 -
c.insert(it, x) 向任意迭代器it插入一个元素x，例如：c.insert(c.begin() + 2,-1)将-1插入c[2]的位置 O(N)
c.erase(first,last) 删除[first,last)的所有元素 O(N)
c.begin() 返回首元素的迭代器（通俗来说就是地址） O(1)
c.end() 返回最后一个元素后一个位置的迭代器（地址） O(1)
c.empty() 判断是否为空，为空返回真，反之返回假 O(1)

注意：

  • end()返回的是最后一个元素的后一个位置的地址，不是最后一个元素的地址，所有STL容器均是如此

  • 使用 vi.resize(n, v) 函数时，若 vi 之前指定过大小为 pre

    • pre > n ：即数组大小变小了，数组会保存前 n 个元素，前 n 个元素值为原来的值，不是都为 v
    • pre < n ：即数组大小变大了，数组会在后面插入 n - pre 个值为 v 的元素

    也就是说，这个初始值 v 只对新插入的元素生效。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>

using namespace std;
void out(vector<int> &a) { for (auto &x: a) cout << x << " "; cout << "\n"; }
int main() {
    vector<int> a(5, 1);
    out(a); // 1 1 1 1 1
    a.resize(10, 2);
    out(a); // 1 1 1 1 1 2 2 2 2 2
    a.resize(3, 3);
    out(a); // 1 1 1
    return 0;
}

排序

使用sort排序要： sort(c.begin(), c.end());

sort()为STL函数，请参考本文最后面STL函数系列。

对所有元素进行排序，如果要对指定区间进行排序，可以对sort()里面的参数进行加减改动。

1
2
vector<int> a(n + 1);
sort(a.begin() + 1, a.end()); // 对[1, n]区间进行从小到大排序

1.3 访问

共三种方法：

  • 下标法 ： 和普通数组一样
    注意：一维数组的下标是从 0 到 v.size()-1 ，访问之外的数会出现越界错误

  • 迭代器法 ： 类似指针一样的访问 ，首先需要声明迭代器变量，和声明指针变量一样，可以根据代码进行理解（附有注释）。

    1
    2
    vector<int> vi; // 定义一个vi数组
    vector<int>::iterator it = vi.begin();// 声明一个迭代器指向vi的初始位置

  • 使用auto ：非常简便，但是会访问数组的所有元素（特别注意0位置元素也会访问到）

1.3.1 下标访问

直接和普通数组一样进行访问即可。

1
2
3
4
5
6
7
8
// 添加元素
for(int i = 0; i < 5; i++)
    vi.push_back(i);
    
// 下标访问 
for(int i = 0; i < 5; i++)
    cout << vi[i] << " ";
cout << "\n";

1.3.2 迭代器访问

类似指针，迭代器就是充当指针的作用。

1
2
3
4
5
vector<int> vi{1, 2, 3, 4, 5};
// 迭代器访问
vector<int>::iterator it;   
// 相当于声明了一个迭代器类型的变量it
// 通俗来说就是声明了一个指针变量

  • 方式一：

    1
    2
    3
    4
    vector<int>::iterator it = vi.begin(); 
    for(int i = 0; i < 5; i++)
        cout << *(it + i) << " ";
    cout << "\n";

  • 方式二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vector<int>::iterator it;
    for(it = vi.begin(); it != vi.end();it ++)
        cout << *it << " ";
    // vi.end()指向尾元素地址的下一个地址

    // 或者
    auto it = vi.begin();
    while (it != vi.end()) {
        cout << *it << "\n";
        it++;
    }

1.3.3 智能指针

只能遍历完数组，如果要指定的内容进行遍历，需要另选方法。

auto 能够自动识别并获取类型。

1
2
3
4
5
6
7
8
9
10
11
12
// 1. 输入
vector<int> a(n);
for (auto &x: a) {
    cin >> x; // 可以进行输入，注意加引用
}
// 2. 输出
vector<int> v;
v.push_back(12);
v.push_back(241);
for(auto val : v) {
    cout << val << " "; // 12 241
}

vector注意：

vi[i] 和 *(vi.begin() + i) 等价，与指针类似。

vector和string的STL容器支持*(it + i)的元素访问，其它容器可能也可以支持这种方式访问，但用的不多，可自行尝试。




2. stack

2.1 介绍

栈为数据结构的一种，是STL中实现的一个先进后出，后进先出的容器。

//头文件需要添加

1
2
3
4
5
6
#include<stack>

// 声明
stack<int> s;
stack<string> s;
stack<node> s;// node是结构体类型

2.2 方法函数

代码 含义 时间复杂度
s.push(ele) 元素ele入栈，增加元素 O(1)
s.pop() 移除栈顶元素 O(1)
s.top() 取得栈顶元素（但不删除） O(1)
s.empty() 检测栈内是否为空，空为真 O(1)
s.size() 返回栈内元素的个数 O(1)

2.3 栈遍历

2.3.1 栈遍历

栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中

1
2
3
4
5
6
stack<int> st;
for (int i = 0; i < 10; ++i) st.push(i);
while (!st.empty()) {
    int tp = st.top(); // 栈顶元素
    st.pop();
}

2.3.2 数组模拟栈进行遍历

通过一个数组对栈进行模拟，一个存放下标的变量top模拟指向栈顶的指针。

一般来说单调栈和单调队列写法均可使用额外变量 tt 或 hh 来进行模拟

特点： 比STL的stack速度更快，遍历元素方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int s[100]; // 栈 从左至右为栈底到栈顶
int tt = -1; // tt 代表栈顶指针,初始栈内无元素，tt为-1

for(int i = 0; i <= 5; ++i) {
    //入栈 
    s[++tt] = i;
}
// 出栈
int top_element = s[tt--]; 

// 入栈操作示意
//  0  1  2  3  4  5  
//                tt
// 出栈后示意
//  0  1  2  3  4 
//              tt



3. queue

3.1 介绍

队列是一种先进先出的数据结构。

1
2
3
4
5
6
// 头文件

#include<queue>

// 定义初始化
queue<int> q;

3.2 方法函数

代码 含义 时间复杂度
q.front() 返回队首元素 O(1)
q.back() 返回队尾元素 O(1)
q.push(element) 尾部添加一个元素element进队 O(1)
q.pop() 删除第一个元素，出队 O(1)
q.size() 返回队列中元素个数，返回值类型unsigned int O(1)
q.empty() 判断是否为空，队列为空，返回true O(1)

3.3 队列模拟

使用q[]数组模拟队列

hh表示队首元素的下标，初始值为0

tt表示队尾元素的下标，初始值为-1，表示刚开始队列为空

一般来说单调栈和单调队列写法均可使用额外变量 tt 或 hh 来进行模拟

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;
const int N = 1e5 + 5;
int q[N];

int main() {
    int hh = 0,tt = -1;
    // 入队 
    q[++tt] = 1;
    q[++tt] = 2; 
    // 将所有元素出队 
    while(hh <= tt) {
        int t = q[hh++];
        printf("%d ",t);
    }
    return 0;
 }



4. deque




5. priority_queue

5.1 介绍

优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。

可以实现每次从优先队列中取出的元素都是队列中优先级最大的一个。

它的底层是通过堆来实现的。

1
2
3
4
//头文件
#include<queue>
//初始化定义
priority_queue<int> q;

5.2 函数方法

代码 含义 时间复杂度
q.top() 访问队首元素 O(1)
q.push() 入队 O(logN)
q.pop() 堆顶（队首）元素出队 O(logN)
q.size() 队列元素个数 O(1)
q.empty() 是否为空 O(1)

注意没有clear()！ 不提供该方法
优先队列只能通过top()访问队首元素（优先级最高的元素）


5.3 设置优先级

5.3.1 基本数据类型的优先级

1
2
priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int>> q; // 小根堆, 每次取出的元素是队列中的最小值

参数解释：

  • 第一个参数：就是优先队列中存储的数据类型

  • 第二个参数：

    vector<int> 是用来承载底层数据结构堆的容器，若优先队列中存放的是double型数据，就要填vector< double >
    总之存的是什么类型的数据，就相应的填写对应类型。同时也要改动第三个参数里面的对应类型。

  • 第三个参数：
    less<int> 表示数字大的优先级大，堆顶为最大的数字
    greater<int> 表示数字小的优先级大，堆顶为最小的数字
    int代表的是数据类型，也要填优先队列中存储的数据类型

下面介绍基础数据类型优先级设置的写法：

  1. 基础写法（非常常用）：

    1
    2
    3
    4
    priority_queue<int> q1; // 默认大根堆, 即每次取出的元素是队列中的最大值
    priority_queue<int, vector<int>, less<int> > q2; // 大根堆, 每次取出的元素是队列中的最大值，同第一行

    priority_queue<int, vector<int>, greater<int> > q3; // 小根堆, 每次取出的元素是队列中的最小值

  2. 自定义排序（不常见，主要是写着麻烦）：
    下面的代码比较长，基础类型优先级写着太麻烦，用第一种即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct cmp1 {
        bool operator()(int x, int y) {
            return x > y;
        }
    };
    struct cmp2 {
        bool operator()(const int x, const int y) {
            return x < y;
        }
    };
    priority_queue<int, vector<int>, cmp1> q1; // 小根堆
    priority_queue<int, vector<int>, cmp2> q2; // 大根堆

5.3.2 高级数据类型(结构体)优先级

即优先队列中存储结构体类型，必须要设置优先级，即结构体的比较运算（因为优先队列的堆中要比较大小，才能将对应最大或者最小元素移到堆顶）。

优先级设置可以定义在结构体内进行小于号重载，也可以定义在结构体外。

1
2
3
4
// 要排序的结构体（存储在优先队列里面的）
struct Point {
    int x, y;
};

  • 版本一：自定义全局比较规则

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //定义的比较结构体
    //注意：cmp是个结构体 
    struct cmp {//自定义堆的排序规则 
        bool operator()(const Point& a,const Point& b) {
            return a.x < b.x;
        }
    };

    //初始化定义， 
    priority_queue<Point, vector<Point>, cmp> q; // x大的在堆顶

  • 版本二：直接在结构体里面写

    因为是在结构体内部自定义的规则，一旦需要比较结构体，自动调用结构体内部重载运算符规则。

    结构体内部有两种方式：

    优先队列的定义：

    1
    priority_queue<Point> q;

    方式一 ：

    1
    2
    3
    4
    5
    6
    struct node {
        int x, y;
        friend bool operator < (Point a, Point b) {//为两个结构体参数，结构体调用一定要写上friend
            return a.x < b.x;//按x从小到大排，x大的在堆顶
        }
    };

    方式二 ：（推荐此种）

    1
    2
    3
    4
    5
    6
    struct node {
        int x, y;
        bool operator < (const Point &a) const {//直接传入一个参数，不必要写friend
            return x < a.x;//按x升序排列，x大的在堆顶
        }
    };

    注意： 优先队列自定义排序规则和sort()函数定义cmp函数很相似，但是最后返回的情况是相反的。即相同的符号，最后定义的排列顺序是完全相反的。
    所以只需要记住sort的排序规则和优先队列的排序规则是相反的就可以了。

    当理解了堆的原理就会发现，堆调整时比较顺序是孩子和父亲节点进行比较，如果是 > ，那么孩子节点要大于父亲节点，堆顶自然是最小值。


5.4 存储特殊类型的优先级

5.4.1 存储pair类型

  • 排序规则：
    默认先对pair的first进行降序排序，然后再对second降序排序
    对first先排序，大的排在前面，如果first元素相同，再对second元素排序，保持大的在前面。
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main() {
    priority_queue<pair<int, int> >q;
    q.push({7, 8});
    q.push({7, 9});
    q.push(make_pair(8, 7));
    while(!q.empty()) {
        cout << q.top().first << " " << q.top().second << "\n";
        q.pop();
    }
    return 0;
}
查看输出 
1
2
3
8 7
7 9
7 8



6. map

6.1 介绍

映射类似于函数的对应关系，每个x对应一个y，而map是每个键对应一个值。会python的朋友学习后就会知道这和python的字典非常类似。

比如说：学习 对应 看书，学习 是键，看书 是值。
学习->看书
玩耍 对应 打游戏，玩耍 是键，打游戏 是值。
玩耍->打游戏

1
2
3
4
5
6
//头文件
#include<map>
//初始化定义
map<string, string> mp;
map<string, int> mp;
map<int, node> mp;//node是结构体类型

map特性：map会按照键的顺序从小到大自动排序，键的类型必须可以比较大小


6.2 函数方法

6.2.1 函数方法

代码 含义
mp.find(key) 返回键为key的映射的迭代器 O(log⁡N)O(\log N)。注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end()
mp.erase(it) 删除迭代器对应的键和值 O(1)O(1)
mp.erase(key) 根据映射的键删除键和值 O(log⁡N)O(\log N)
mp.erase(first,last) 删除左闭右开区间迭代器对应的键和值 O(last−first)O(\text{last} - \text{first})
mp.size() 返回映射的对数 O(1)O(1)
mp.clear() 清空map中的所有元素 O(N)O(N)
mp.insert() 插入元素，插入时要构造键值对
mp.empty() 如果map为空，返回true，否则返回false
mp.begin() 返回指向map第一个元素的迭代器（地址）
mp.end() 返回指向map尾部的迭代器（最后一个元素的下一个地址）
mp.rbegin() 返回指向map最后一个元素的迭代器（地址）
mp.rend() 返回指向map第一个元素前面(上一个）的逆向迭代器（地址）
mp.count(key) 查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0
mp.lower_bound() 返回一个迭代器，指向键值 >= key的第一个元素
mp.upper_bound() 返回一个迭代器，指向键值 > key的第一个元素
空间复杂度

在C++的标准模板库（STL）中，map是一种基于红黑树实现的关联容器，它存储键值对，其中每个键唯一，且键值对是按照键的顺序排序的。由于map是基于红黑树的，我们可以分析其空间复杂度。

空间复杂度分析：

  1. 红黑树节点：每个节点包含存储的键值对、颜色标记（通常是一个布尔值表示红或黑），以及指向其父节点、左子节点和右子节点的指针。因此，每个节点的空间复杂度是常数O(1)。

  2. 整体空间复杂度：由于每个键值对在map中由一个红黑树节点表示，因此map的总空间复杂度与其中存储的键值对数量成线性关系，即O(n)，其中n是键值对的数量。

附加因素：

  • 内存分配器：C++ STL允许使用自定义内存分配器，这可能会影响实际使用的内存量，但不改变总体空间复杂度。

  • 节点平衡信息：红黑树通过维持树的平衡来确保操作的效率，这需要额外的信息（即节点颜色），但同样不改变空间复杂度。

  • 指针和对齐：实际内存使用量会受到系统指针大小和数据对齐需求的影响。例如，在64位系统上，指针通常占8字节。这意味着每个节点的实际内存使用可能高于简单估计，但这依然是线性关系。

综上所述，STL中map的空间复杂度为O(n)，其中n是存储的键值对数量。这反映了在实际应用中使用map时应考虑的内存使用情况。

6.2.2 注意点

下面说明部分函数方法的注意点

注意：
查找元素是否存在时，可以使用
①mp.find() ② mp.count() ③ mp[key]
但是第三种情况，如果不存在对应的key时，会自动创建一个键值对（产生一个额外的键值对空间）
所以为了不增加额外的空间负担，最好使用前两种方法

6.2.3 迭代器进行正反向遍历

  • mp.begin()和mp.end()用法：
1
2
3
4
5
6
7
8
9
10
// 用于正向遍历map
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.begin();
while(it != mp.end()) {
    cout << it->first << " " << it->second << "\n";
    it ++;
}
查看输出 
1
2
3
4
1 2
2 3
3 4

  • mp.rbegin()和mp.rend()
1
2
3
4
5
6
7
8
9
10
// 用于逆向遍历map
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.rbegin();
while(it != mp.rend()) {
    cout << it->first << " " << it->second << "\n";
    it ++;
}
查看输出 
1
2
3
4
3 4
2 3
1 2


6.3 添加元素

1
2
//先声明
map<string, string> mp;

  • 方式一：

    1
    2
    mp["学习"] = "看书";
    mp["玩耍"] = "打游戏";

  • 方式二：插入元素构造键值对

    1
    mp.insert(make_pair("vegetable","蔬菜"));
    查看make_pair()

    在 C++ 中，make_pair 是一个非常有用的函数模板，它属于 <utility> 头文件。make_pair 用于创建一个 std::pair 对象，这种对象可以存储一对值，这对值可能属于相同的类型或者不同的类型。使用 make_pair 可以方便地生成 pair 对象，而不需要显式指定其中值的类型，因为这些类型可以通过函数参数自动推导得出。

    基本用法

    make_pair 的基本语法如下：

    1
    std::pair<T1, T2> make_pair(T1 value1, T2 value2);

    其中 T1 和 T2 是 pair 第一个和第二个值的类型，分别对应 value1 和 value2 这两个参数。make_pair 返回一个新的 pair 对象，该对象的第一个元素类型为 T1，第二个元素类型为 T2。

    示例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <iostream>
    #include <utility> // For std::make_pair

    int main() {
        // 创建一个 pair，存储一个 int 和一个 double
        auto p1 = std::make_pair(42, 3.14);

        // 创建一个 pair，存储两个 string
        auto p2 = std::make_pair("Hello", "World");

        std::cout << "p1: " << p1.first << ", " << p1.second << std::endl;
        std::cout << "p2: " << p2.first << ", " << p2.second << std::endl;

        return 0;
    }

    在这个例子中，使用 make_pair 创建了两个 pair 对象：p1 存储了一个 int 和一个 double，p2 存储了两个 string。注意，我们使用了 auto 关键字让编译器自动推断 pair 对象的完整类型，这是使用 make_pair 的常见做法，因为它简化了代码并使其更加清晰。

    优点

    • 类型推导： 最大的优点是不需要手动指定类型，make_pair 会自动推导参数的类型。
    • 代码简洁： 使用 make_pair 可以使得代码更简洁、更易读。

    使用场景

    make_pair 在需要创建 pair 对象时非常有用，特别是当用作其他容器（如 map、set 中的元素或者作为函数返回值）时。例如，在 std::map 中插入元素时，经常会用到 make_pair 来生成键值对。

  • 方式三：

    1
    mp.insert(pair<string,string>("fruit","水果"));

  • 方式四:

    1
    mp.insert({"hahaha","wawawa"});

6.4 访问元素

6.4.1 下标访问

(大部分情况用于访问单个元素)

1
2
mp["菜哇菜"] = "强哇强";
cout << mp["菜哇菜"] << "\n";//只是简写的一个例子，程序并不完整

6.4.2 遍历访问

  • 方式一：迭代器访问

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
      map<string,string>::iterator it;
      for(it = mp.begin(); it != mp.end(); it++) {
          //      键                 值 
          // it是结构体指针访问所以要用 -> 访问
          cout << it->first << " " << it->second << "\n";
          //*it是结构体变量 访问要用 . 访问
          //cout<<(*it).first<<" "<<(*it).second;
      }

    - 方式二：智能指针访问

      ```c++
      for(auto i : mp)
      cout << i.first << " " << i.second << endl;//键，值

  • 方式三：对指定单个元素访问

    1
    2
    map<char,int>::iterator it = mp.find('a');
    cout << it -> first << " " <<  it->second << "\n";

  • 方式四：c++17特性才具有

    1
    2
    3
    for(auto [x, y] : mp)
        cout << x << " " << y << "\n";
    //x,y对应键和值

6.5 与unordered_map的比较

这里就不单开一个大目录讲unordered_map了，直接在map里面讲了。

6.5.1 内部实现原理

map：内部用红黑树实现，具有自动排序（按键从小到大）功能。

unordered_map：内部用哈希表实现，内部元素无序杂乱。

6.5.2 效率比较

map：

优点：内部用红黑树实现，内部元素具有有序性，查询删除等操作复杂度为O(logN)O(logN)

缺点：占用空间，红黑树里每个节点需要保存父子节点和红黑性质等信息，空间占用较大。

unordered_map：

优点：内部用哈希表实现，查找速度非常快（适用于大量的查询操作）。
缺点：建立哈希表比较耗时。

两者方法函数基本一样，差别不大。

注意：

随着内部元素越来越多，两种容器的插入删除查询操作的时间都会逐渐变大，效率逐渐变低。

使用[]查找元素时，如果元素不存在，两种容器都是创建一个空的元素；如果存在，会正常索引对应的值。所以如果查询过多的不存在的元素值，容器内部会创建大量的空的键值对，后续查询创建删除效率会大大降低。

查询容器内部元素的最优方法是：先判断存在与否，再索引对应值（适用于这两种容器）

1
2
3
4
5
// 以 map 为例
map<int, int> mp;
int x = 999999999;
if(mp.count(x)) // 此处判断是否存在x这个键
    cout << mp[x] << "\n";   // 只有存在才会索引对应的值，避免不存在x时多余空元素的创建

另外：

还有一种映射：multimap
键可以重复，即一个键对应多个值，如要了解，可以自行搜索。




7. set

7.1 介绍

set容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且set容器里的元素自动从小到大排序。

即：set里面的元素不重复 且有序

1
2
3
4
//头文件
#include<set>
//初始化定义
set<int> s;

7.2 函数方法

代码 含义
s.begin() 返回set容器的第一个元素的地址（迭代器）O(1)O(1)
s.end() 返回set容器的最后一个元素的下一个地址（迭代器）O(1)O(1)
s.rbegin() 返回逆序迭代器，指向容器元素最后一个位置 O(1)O(1)
s.rend() 返回逆序迭代器，指向容器第一个元素前面的位置 O(1)O(1)
s.clear() 删除set容器中的所有的元素,返回unsigned int类型 O(N)O(N)
s.empty() 判断set容器是否为空 O(1)O(1)
s.insert() 插入一个元素
s.size() 返回当前set容器中的元素个数 O(1)O(1)
erase(iterator) 删除定位器iterator指向的值
erase(first,second) 删除定位器first和second之间的值
erase(key_value) 删除键值key_value的值
查找
s.find(element) 查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器
s.count(element) 查找set中的元素出现的个数，由于set中元素唯一，此函数相当于查询element是否出现
s.lower_bound(k) 返回大于等于k的第一个元素的迭代器 O(log⁡N)O(\log N)
s.upper_bound(k) 返回大于k的第一个元素的迭代器 O(log⁡N)O(\log N)

7.3 访问

  • 迭代器访问
1
2
for(set<int>::iterator it = s.begin(); it != s.end(); it++)
    cout << *it << " ";
  • 智能指针
1
2
for(auto i : s)
    cout << i << endl;
  • 访问最后一个元素
1
2
3
4
5
6
7
8
9
10
// 第一种
cout << *s.rbegin() << endl;

 // 第二种
set<int>::iterator iter = s.end();
iter--;
cout << (*iter) << endl; //打印2;

//第三种
cout << *(--s.end()) << endl;

7.4 重载<运算符

  • 基础数据类型

方式一：改变set排序规则，set中默认使用less比较器，即从小到大排序。（常用）

1
2
set<int> s1; // 默认从小到大排序
set<int, greater<int> > s2; // 从大到小排序

方式二：重载运算符。（很麻烦，不太常用，没必要）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//重载 < 运算符
struct cmp {
    bool operator () (const int& u, const int& v) const {
       // return + 返回条件
       return u > v;
    }
};
set<int, cmp> s; 

for(int i = 1; i <= 10; i++)
    s.insert(i);
for(auto i : s)
    cout << i << " ";
// 10 9 8 7 6 5 4 3 2 1

方式三：初始化时使用匿名函数定义比较规则

1
2
3
4
5
6
7
set<int, function<bool(int, int)>> s([&](int i, int j){
    return i > j; // 从大到小
});
for(int i = 1; i <= 10; i++)
    s.insert(i);
for(auto x : s)
    cout << x << " ";
  • 高级数据类型（结构体）

直接重载结构体运算符即可，让结构体可以比较。

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
struct Point {
    int x, y;
    bool operator < (const Point &p) const {
        // 按照点的横坐标从小到大排序,如果横坐标相同,纵坐标从小到大
        if(x == p.x)
            return y < p.y;
        return x < p.x;
    }
};

set<Point> s;
for(int i = 1; i <= 5; i++) {
    int x, y;
    cin >> x >> y;
    s.insert({x, y});
}    
/* 输入
5 4
5 2
3 7
3 5
4 8
*/

for(auto i : s)
    cout << i.x << " " << i.y << "\n";
/* 输出
3 5
3 7
4 8
5 2
5 4
*/

7.5 其它set

multiset: 元素可以重复，且元素有序

unordered_set ：元素无序且只能出现一次

unordered_multiset ： 元素无序可以出现多次




8. pair




9. string

9.1 介绍

string是一个字符串类，和char型字符串类似。

可以把string理解为一个字符串类型，像int一样可以定义


9.2 初始化及定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//头文件
#include<string>

//1.
string str1; //生成空字符串

//2.
string str2("123456789"); //生成"1234456789"的复制品 

//3.
string str3("12345", 0, 3);//结果为"123" ，从0位置开始，长度为3

//4.
string str4("123456", 5); //结果为"12345" ，长度为5

//5.
string str5(5, '2'); //结果为"22222" ,构造5个字符'2'连接而成的字符串

//6.
string str6(str2, 2); //结果为"3456789"，截取第三个元素（2对应第三位）到最后

简单使用

  • 访问单个字符：
1
2
3
4
5
6
7
8
9
#include<iostream>
#include<string>
using namespace std;
int main() {
    string s = "xing ma qi!!!";
    for(int i = 0; i < s.size(); i++)
        cout << s[i] << " ";
    return 0;
}
  • string数组使用：
1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
#include<string>
using namespace std;
int main() {
    string s[10];
    for(int i = 1; i < 10; i++) {
        s[i] = "loading...  " ;
        cout << s[i] << i << "\n";
    } 
    return 0;
}
查看输出 
1
2
3
4
5
6
7
8
9
10
loading...  1
loading...  2
loading...  3
loading...  4
loading...  5
loading...  6
loading...  7
loading...  8
loading...  9


9.3 string 特性

  • 支持比较运算符
    string字符串支持常见的比较操作符（>,>=,<,<=,==,!=），支持string与C-string的比较（如 str < "hello"）。
    在使用>,>=,<,<=这些操作符的时候是根据“当前字符特性”将字符按 字典顺序 进行逐一得 比较。字典排序靠前的字符小， 比较的顺序是从前向后比较，遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小（前面减后面）。

  • 支持+运算符，代表拼接字符串
    string字符串可以拼接，通过"+"运算符进行拼接。

    1
    2
    3
    4
    string s1 = "123";
    string s2 = "456";
    string s = s1 + s2;
    cout << s;   //123456

9.4 读入详解

读入字符串，遇空格，回车结束

1
2
string s;
cin >> s;

读入一行字符串（包括空格），遇回车结束

1
2
string s;
getline(cin, s);

注意: getline(cin, s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()

查看实例

cin与cin.getline()混用

cin输入完后，回车，cin遇到回车结束输入，但回车还在输入流中，cin并不会清除，导致getline()读取回车，结束。
需要在cin后面加cin.ignore()；主动删除输入流中的换行符。（不常用）

错误读取：

1
2
3
4
int n;
string s;
cin >> n;
getline(cin, s); //此时读取相当于读取了前一个回车字符

正确读取：

1
2
3
4
5
int n;
string s;
cin >> n;
getchar(); //cin.get()
getline(cin, s);//可正确读入下一行的输入

cin和cout解锁

代码（写在main函数开头）：

1
2
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

为什么要进行cin和cout的解锁，原因是：

在一些题目中，读入的数据量很大，往往超过了1e5（105）的数据量,而cin和cout的读入输出的速度很慢（是因为cin和cout为了兼容C语言的读入输出在性能上做了妥协），远不如scanf和printf的速度，具体原因可以搜索相关的博客进行了解。

所以对cin和cout进行解锁使cin和cout的速度几乎接近scanf和printf，避免输入输出超时。

注意：cin cout解锁使用时，不能与 scanf,getchar, printf,cin.getline()混用，一定要注意，会出错。

string与C语言字符串（C-string）的区别

string
是C++的一个类，专门实现字符串的相关操作。具有丰富的操作方法，数据类型为string，字符串结尾没有\0字符
C-string
C语言中的字符串，用char数组实现，类型为const char *,字符串结尾以\0结尾

一般来说string向char数组转换会出现一些问题，所以为了能够实现转换，string有一个方法c_str()实现string向char数组的转换。

1
2
string s = "xing ma qi";
char s2[] = s.c_str();

9.5 函数方法

  • 获取字符串长度
代码 含义
s.size()和s.length() 返回string对象的字符个数，他们执行效果相同。
s.max_size() 返回string对象最多包含的字符数，超出会抛出length_error异常
s.capacity() 重新分配内存之前，string对象能包含的最大字符数
  • 插入
代码 含义
s.push_back() 在末尾插入
例：s.push_back('a') 末尾插入一个字符a
s.insert(pos,element) 在pos位置插入element
例：s.insert(s.begin(),'1') 在第一个位置插入1字符
s.append(str) 在s字符串结尾添加str字符串
例：s.append("abc") 在s字符串末尾添加字符串“abc”
  • 删除
代码 含义
erase(iterator p) 删除字符串中p所指的字符
erase(iterator first, iterator last) 删除字符串中迭代器区间[first,last)上所有字符
erase(pos, len) 删除字符串中从索引位置pos开始的len个字符
clear() 删除字符串中所有字符
  • 字符替换
代码 含义
s.replace(pos,n,str) 把当前字符串从索引pos开始的n个字符替换为str
s.replace(pos,n,n1,c) 把当前字符串从索引pos开始的n个字符替换为n1个字符c
s.replace(it1,it2,str) 把当前字符串[it1,it2)区间替换为str。it1, it2为迭代器
  • 大小写转换

法一：

代码 含义
tolower(s[i]) 转换s[i]为小写
toupper(s[i]) 转换s[i]为大写

法二：

通过stl的transform算法配合tolower 和toupper 实现。
有4个参数，前2个指定要转换的容器的起止范围，第3个参数是结果存放容器的起始位置，第4个参数是一元运算。

1
2
3
string s;
transform(s.begin(),s.end(),s.begin(),::tolower); // 转换小写
transform(s.begin(),s.end(),s.begin(),::toupper); // 转换大写
  • 分割
代码 含义
s.substr(pos,n) 截取从pos索引开始的n个字符
  • 查找
代码 含义
s.find(str, pos) 在当前字符串的pos索引位置（默认为0）开始，查找子串str，返回找到的位置索引，-1表示查找不到子串
s.find(c, pos) 在当前字符串的pos索引位置（默认为0）开始，查找字符c，返回找到的位置索引，-1表示查找不到字符
s.rfind(str, pos) 在当前字符串的pos索引位置开始，反向查找子串s，返回找到的位置索引，-1表示查找不到子串
s.rfind(c,pos) 在当前字符串的pos索引位置开始，反向查找字符c，返回找到的位置索引，-1表示查找不到字符
s.find_first_of(str, pos) 在当前字符串的pos索引位置（默认为0）开始，查找子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_first_not_of(str,pos) 在当前字符串的pos索引位置（默认为0）开始，查找第一个不位于子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_last_of(str, pos) 在当前字符串的pos索引位置开始，查找最后一个位于子串s的字符，返回找到的位置索引，-1表示查找不到字符
s.find_last_not_of(str, pos) 在当前字符串的pos索引位置开始，查找最后一个不位于子串s的字符，返回找到的位置索引，-1表示查找不到子串 
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
#include<string>
#include<iostream>
int main() {
    string s("dog bird chicken bird cat");
// 字符串查找-----找到后返回首字母在字符串中的下标
// 1. 查找一个字符串
    cout << s.find("chicken") << endl;// 结果是：9
    
// 2. 从下标为6开始找字符'i'，返回找到的第一个i的下标
    cout << s.find('i',6) << endl;// 结果是：11
    
// 3. 从字符串的末尾开始查找字符串，返回的还是首字母在字符串中的下标
    cout << s.rfind("chicken") << endl;// 结果是：9
    
// 4. 从字符串的末尾开始查找字符
    cout << s.rfind('i') << endl;// 结果是：18因为是从末尾开始查找，所以返回第一次找到的字符
    
// 5. 在该字符串中查找第一个属于字符串s的字符
    cout << s.find_first_of("13br98") << endl;// 结果是：4---b
    
// 6. 在该字符串中查找第一个不属于字符串s的字符------先匹配dog，然后bird匹配不到，所以打印4
    cout << s.find_first_not_of("hello dog 2006") << endl; // 结果是：4
    cout << s.find_first_not_of("dog bird 2006") << endl;  // 结果是：9
    
// 7. 在该字符串最后中查找第一个属于字符串s的字符
    cout << s.find_last_of("13r98") << endl;// 结果是：19

// 8. 在该字符串最后中查找第一个不属于字符串s的字符------先匹配t--a---c，然后空格匹配不到，所以打印21
    cout << s.find_last_not_of("teac") << endl;// 结果是：21
}
  • 排序
1
sort(s.begin(),s.end());  // 按ASCII码排序




其他STL函数

sort()

C++标准模板库（STL）中的sort()函数是一个非常强大的算法，用于对容器内的元素进行排序。它被定义在<algorithm>头文件中，可以对几乎所有类型的容器进行排序，包括数组、向量（vector）、列表（list）等，只要容器的元素可以比较大小。

  • 基本用法：

sort()函数最简单的形式只需要两个参数，即要排序的范围的开始和结束迭代器。这种情况下，它会默认使用元素类型的<运算符来比较元素大小，因此被排序的元素类型必须支持这个运算符。

1
2
3
4
5
6
7
8
9
10
11
#include <algorithm> // sort()函数所在的头文件
#include <vector>

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};

    // 使用默认比较（小到大排序）
    std::sort(vec.begin(), vec.end());

    return 0;
}
  • 使用greater和less

在C++中，你可以使用std::sort函数结合std::greater<>或std::less<>来实现降序或自定义排序。std::greater<>和std::less<>是定义在头文件<functional>中的比较函数对象。

使用std::greater<>实现降序排序

当你想对一个数组或向量进行降序排序时，可以传递std::greater<>作为std::sort的第三个参数。

对数组进行降序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm> // 用于sort
#include <functional> // 用于greater

int main() {
    int arr[] = {5, 2, 4, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::sort(arr, arr + n, std::greater<int>()); // 使用greater<int>对数组进行降序排序

    // 输出排序后的数组
    for(int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

对向量进行降序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <algorithm> // 用于sort
#include <functional> // 用于greater

int main() {
    std::vector<int> vec = {5, 2, 4, 3, 1};

    std::sort(vec.begin(), vec.end(), std::greater<int>()); // 使用greater<int>对向量进行降序排序

    // 输出排序后的向量
    for(int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

使用std::less<>进行升序排序

实际上，std::sort默认就是使用std::less<>进行升序排序的，所以通常你不需要显式地指定它。但是如果你想要明确表示出来，或者使用自定义类型进行排序时指定排序规则，可以这样做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <algorithm> // 用于sort
#include <functional> // 用于less

int main() {
    std::vector<int> vec = {5, 2, 4, 3, 1};

    std::sort(vec.begin(), vec.end(), std::less<int>()); // 显式使用less<int>对向量进行升序排序

    // 输出排序后的向量
    for(int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

使用std::less<>和std::greater<>可以让代码的意图更加明显，尤其是在涉及复杂类型或自定义排序逻辑的情况下。

  • 自定义比较函数：

sort()也支持自定义比较函数，这使得我们可以控制排序的具体行为，比如实现降序排序或根据对象的某个特定字段进行排序。

自定义比较函数可以是普通函数，也可以是lambda表达式。这个函数需要接收两个待比较的元素作为参数，并返回一个布尔值，表示第一个参数是否应该排在第二个参数之前。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>

bool compare(int a, int b) {
    return a > b; // 降序排序
}

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};

    // 使用自定义比较函数
    std::sort(vec.begin(), vec.end(), compare);

    // 使用lambda表达式进行自定义排序（例如，按绝对值升序排序）
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return abs(a) < abs(b);
    });

    return 0;
}

正确使用自定义比较函数

自定义比较函数应当确保对于任意的元素a和b，如果a应排在b之前，则返回true；否则返回false。这通常意味着你应该使用<（或>，取决于你想要升序还是降序排序）来比较元素。
如果你真的需要使用<=或>=逻辑，可能是因为你想要实现某种特殊的排序逻辑，那么你需要非常小心，确保这种比较逻辑不会违反排序算法要求的性质。

  • 重载运算符

如果不使用自定义比较函数，你可以通过为你的类或结构体重载运算符来实现排序。这种方法尤其适合当你需要频繁对某个自定义类型的对象进行排序，或者你想要为对象的默认排序行为提供一个明确的规则。最常见的是重载<运算符，这样sort()函数就可以直接使用这个运算符来比较类的实例。

重载<运算符的例子

假设你有一个Student类，其中包含姓名（name）和分数（score），你想要根据分数来排序学生，分数高的排在前面。你可以这样重载<运算符：

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
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

class Student {
public:
    std::string name;
    int score;

    Student(std::string n, int s) : name(n), score(s) {}

    // 重载<运算符，根据分数进行比较（降序）
    bool operator < (const Student& other) const {
        return score > other.score; // 注意这里用的是>, 因为我们想要分数高的在前
    }
};

int main() {
    std::vector<Student> students = {
        {"Alice", 88}, {"Bob", 95}, {"Charlie", 92}
    };

    // 直接使用sort()，不需要自定义比较函数
    std::sort(students.begin(), students.end());

    // 输出排序后的学生信息
    for (const auto& student : students) {
        std::cout << student.name << ": " << student.score << std::endl;
    }

    return 0;
}

注意事项

  • 当你重载比较运算符来为sort()提供排序逻辑时，同样需要确保你的比较逻辑满足严格弱序的要求。在上面的例子中，通过使用>运算符来比较分数，我们确保了分数较高的学生会被视为较小（即在排序数组中排在前面），这是因为sort()默认执行升序排序。
  • 重载运算符应该提供一致且预期内的行为，避免在不同上下文中产生混淆或误解。特别是当与标准库算法一起使用时，需要确保重载的运算符行为符合算法的预期。
  • 重载运算符的类或结构体需要被设计为可以被排序算法访问，这通常意味着重载的运算符需要是公有的（public）。
  • 经典案例

排序结构体或类的对象：

当我们需要对一组自定义类型的对象进行排序时，可以通过提供自定义比较函数来实现。

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
#include <algorithm>
#include <vector>
#include <string>

struct Student {
    std::string name;
    int score;

    // 构造函数
    Student(std::string n, int s) : name(n), score(s) {}
};

// 按成绩降序排序
bool compareStudent(Student a, Student b) {
    return a.score > b.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 88}, {"Bob", 95}, {"Charlie", 92}
    };

    // 使用自定义比较函数对学生对象进行排序
    std::sort(students.begin(), students.end(), compareStudent);

    return 0;
}

这种方式让sort()算法变得极其灵活和强大，几乎可以应用于任何排序场景。不过，需要注意的是，sort()默认实现的是不稳定排序，即相等元素的原始顺序可能会改变。如果需要稳定排序，可以考虑使用std::stable_sort()。

数字 和 字符串互转

C++标准模板库（STL）提供了多种方式来实现字符串和数字之间的转换。

  1. 使用std::stoi、std::stol、std::stod等函数将字符串转换为数字： 这些函数分别用于将字符串转换为int、long、double等类型的数字。它们是C++11引入的，位于<string>头文件中。
    • std::stoi("123")将字符串"123"转换为整数123。
    • std::stod("123.45")将字符串"123.45"转换为双精度浮点数123.45。
  2. 使用std::to_string函数将数字转换为字符串： std::to_string函数可以接受基本数字类型（如int、long、float、double等）作为参数，并将它们转换为字符串。这个函数也是C++11新增的，位于<string>头文件中。
    • std::to_string(123)将整数123转换为字符串"123"。
    • std::to_string(123.45)将双精度浮点数123.45转换为字符串"123.450000"。