STL

字符串：string

字符串是一个字符序列，可以方便地进行字符串的操作。

字符串基本操作：

1.字符串的初始化

string s1 = "hello"; // 创建一个字符串对象s1，初始化为"hello"
string s2("world"); // 创建一个字符串对象s2，初始化为"world"
string s3(5, 'a'); // 创建一个字符串对象s3，初始化为"aaaaa"

2.字符串的拼接

string s1 = "hello";
string s2 = "world";
string s3 = s1 + s2; // 字符串拼接

3.字符串的长度

string s = "hello";
int len = s.length(); // 获取字符串s的长度

4.字符串的遍历

string s = "hello";
for (int i = 0; i < s.length(); i++) // 遍历字符串s
{
    cout << s[i] << " "; // 输出字符串s的每个字符
}
cout << endl;

5.字符串的查找

string s = "hello";
int pos = s.find("ll"); // 查找字符串s中是否包含"ll"，返回位置
if (pos != string::npos) // 如果找到了"ll"
{
    cout << "found" << endl; // 输出"found"
}
else // 如果没有找到"ll"
{
    cout << "not found" << endl; // 输出"not found"
}

6.字符串的替换

string s = "hello";
s.replace(2, 3, "123"); // 替换字符串s中位置2开始的3个字符为"123"
cout << s << endl; // 输出替换后的字符串s

7.字符串的截取

string s = "hello";
string t = s.substr(2, 3); // 截取字符串s中位置2开始的3个字符
cout << t << endl; // 输出截取后的字符串t

8.字符串的转换

string s = "123";
int n = stoi(s); // 将字符串s转换为整数n
cout << n << endl; // 输出整数n

9.字符串的比较

string s1 = "hello";
string s2 = "world";
if (s1 < s2) // 比较字符串s1和s2的大小
{
    cout << "s1 < s2" << endl; // 输出"s1 < s2"
}
else
{
    cout << "s1 >= s2" << endl; // 输出"s1 >= s2"
}

10.字符串的反转

string s = "hello";
reverse(s.begin(), s.end()); // 反转字符串s
cout << s << endl; // 输出反转后的字符串s

11.字符串的去重

string s = "hello";
sort(s.begin(), s.end()); // 对字符串s进行排序
s.erase(unique(s.begin(), s.end()), s.end()); // 去重
cout << s << endl; // 输出去重后的字符串s

---

字符串的一些注意事项

字符串的赋值：

string s1 = "hello"; // 创建一个字符串对象s1，初始化为"hello"
string s2 = s1; // 创建一个字符串对象s2，将s1赋值给s2

👆可以直接把一个string赋值给另一个string，为拷贝构造

char str[] = "world"; // 创建一个字符数组str
string s = str; // 创建一个字符串对象s，将字符数组str赋值给s

👆也可以直接把一个字符数组赋值给一个string，为拷贝构造

---

队列：queue

队列在蓝桥杯中主要用于广度优先搜索算法，用于存储待访问的节点。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    queue<int> q; // 创建一个整型队列对象q
    q.push(1); // 将元素1插入队列q的末尾
    q.push(2); // 将元素2插入队列q的末尾
    q.push(3); // 将元素3插入队列q的末尾
    cout << q.front() << endl; // 输出队列q的头元素，即1
    q.pop(); // 移除队列q的头元素
    cout << q.front() << endl; // 输出队列q的新的头元素，即2
    return 0;
}

---

栈：stack

栈在蓝桥杯中主要用于深度优先搜索算法，用于存储待访问的节点。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    stack<int> s; // 创建一个整型栈对象s
    s.push(1); // 将元素1插入栈s的顶部
    s.push(2); // 将元素2插入栈s的顶部
    s.push(3); // 将元素3插入栈s的顶部
    cout << s.top() << endl; // 输出栈s的顶部元素，即3
    s.pop(); // 移除栈s的顶部元素
    cout << s.top() << endl; // 输出栈s的新的顶部元素，即2
    return 0;
}

---

动态数组：vector

vector是一个动态数组，可以方便地进行插入和删除操作。

int main()
{
    vector<int> v; // 创建一个整型动态数组对象v
    v.push_back(1); // 将元素1插入数组v的末尾
    v.push_back(2); // 将元素2插入数组v的末尾
    v.push_back(3); // 将元素3插入数组v的末尾
    cout << v[0] << endl; // 输出数组v的第一个元素，即1
    cout << v[1] << endl; // 输出数组v的第二个元素，即2
    cout << v[2] << endl; // 输出数组v的第三个元素，即3
    return 0;
}

vector的初始化：

方式1：

vector<int> v1 = {1, 2, 3}; // 创建一个整型动态数组对象v1，初始化为{1, 2, 3}
vector<int> v2(5); // 创建一个整型动态数组对象v2，大小为5
vector<int> v3(5, 1); // 创建一个整型动态数组对象v3，大小为5，所有元素初始化为1

方式2：

vector<int> v; // 创建一个整型动态数组对象v
v.push_back(1); // 将元素1插入数组v的末尾
v.push_back(2); // 将元素2插入数组v的末尾
v.push_back(3); // 将元素3插入数组v的末尾

注意：

vector在使用时，需要注意初始化大小，否则不能直接用下标访问。

以下代码是错误的：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> v; // 这里没有初始化大小，所以不能直接用下标访问
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    for (int i = 0; i < n; i++)
    {
        cout << v[i];
    }

    return 0;
}

正确的写法：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> v(n); // 这里初始化了大小为n
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    for (int i = 0; i < n; i++)
    {
        cout << v[i];
    }

    return 0;
}

二维动态数组：

方式1：

vector<vector<int>> v; // 创建一个二维整型动态数组对象v
v.push_back({1, 2, 3}); // 将{1, 2, 3}插入数组v的末尾
v.push_back({4, 5, 6}); // 将{4, 5, 6}插入数组v的末尾

方式2：

vector<vector<int>> v(2, vector<int>(3)); // 创建一个二维整型动态数组对象v，大小为2x3

vector的遍历：

vector<int> v = {1, 2, 3}; // 创建一个整型动态数组对象v
for (int i = 0; i < v.size(); i++) // 遍历数组v
{
    cout << v[i] << " "; // 输出数组v的元素
}
cout << endl;

vector的排序：

vector<int> v = {3, 1, 2}; // 创建一个整型动态数组对象v
sort(v.begin(), v.end()); // 对数组v进行排序
for (int i = 0; i < v.size(); i++) // 遍历数组v
{
    cout << v[i] << " "; // 输出数组v的元素
}
cout << endl;

vector的查找：

vector<int> v = {1, 2, 3}; // 创建一个整型动态数组对象v
vector<int>::iterator it = find(v.begin(), v.end(), 2); // 查找数组v中是否存在值为2的元素
if (it != v.end()) // 如果找到了元素2
{
    cout << "found" << endl; // 输出"found"
}
else // 如果没有找到元素2
{
    cout << "not found" << endl; // 输出"not found"
}

vector的去重：

vector<int> v = {1, 2, 2, 3}; // 创建一个整型动态数组对象v
sort(v.begin(), v.end()); // 对数组v进行排序
v.erase(unique(v.begin(), v.end()), v.end()); // 去重
for (int i = 0; i < v.size(); i++) // 遍历数组v
{
    cout << v[i] << " "; // 输出去重后的数组v的元素
}
cout << endl;

---

集合：set

set在蓝桥杯中主要用于去重操作，可以方便地判断元素是否存在。
蓝桥杯202题：确定字符串是否包含唯一字符

int main()
{
    set<int> s; // 创建一个整型集合对象s
    s.insert(1); // 将元素1插入集合s
    s.insert(2); // 将元素2插入集合s
    s.insert(3); // 将元素3插入集合s
    cout << s.count(2) << endl; // 输出集合s中元素2的个数，即1
    s.erase(2); // 移除集合s中的元素2
    cout << s.count(2) << endl; // 输出集合s中元素2的个数，即0
    return 0;
}

无序集合：unordered_set

unordered_set是一个无序集合，可以方便地判断元素是否存在。

int main()
{
    unordered_set<int> s; // 创建一个整型无序集合对象s
    s.insert(1); // 将元素1插入集合s
    s.insert(2); // 将元素2插入集合s
    s.insert(3); // 将元素3插入集合s
    cout << s.count(2) << endl; // 输出集合s中元素2的个数，即1
    s.erase(2); // 移除集合s中的元素2
    cout << s.count(2) << endl; // 输出集合s中元素2的个数，即0
    return 0;
}

---

set与unordered_set的区别

set和unordered_set都是C++ STL中的关联容器，它们的区别在于底层实现的数据结构不同。
set是基于红黑树实现的，它的元素是有序的，而unordered_set是基于哈希表实现的，它的元素是无序的。
因此，set的查找、插入和删除操作的时间复杂度是O(logn)，而unordered_set的查找、插入和删除操作的时间复杂度是O(1)。
在实际应用中，如果需要元素有序，可以使用set；如果不需要元素有序，可以使用unordered_set。

---

映射：map

map在蓝桥杯中主要用于存储键值对，可以方便地查找和删除元素。
多用于BFS的记录路径。比如蓝桥杯102题：青蛙跳杯子

int main()
{
    map<string, int> m; // 创建一个从字符串到整数的映射对象m
    m["one"] = 1; // 插入键值对"one"->1
    m["two"] = 2; // 插入键值对"two"->2
    m["three"] = 3; // 插入键值对"three"->3
    cout << m["two"] << endl; // 输出映射m中键"two"对应的值，即2
    m.erase("two"); // 移除映射m中键"two"对应的键值对
    cout << m.count("two") << endl; // 输出映射m中键"two"的个数，即0
    return 0;
}

map的cmp函数

bool cmp(int a, int b)
{
    return a > b; // 降序排序，反之为升序排序
}

注意：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    map<string, int> m;
    cout << m["123"];

    return 0;
}

输出结果：

0

当map中不存在某个键时，会自动插入一个默认值，对于int类型，默认值为0。
所以在做类似于蓝桥杯1530题：费里的语言时，无需考虑map的初始化，直接使用即可。

---

无序集合：unordered_map

unordered_map是一个无序映射，可以方便地查找和删除元素。
蓝桥杯252题：查找两个总和为特定值的索引

int main()
{
    unordered_map<string, int> m; // 创建一个从字符串到整数的无序映射对象m
    m["one"] = 1; // 插入键值对"one"->1
    m["two"] = 2; // 插入键值对"two"->2
    m["three"] = 3; // 插入键值对"three"->3
    cout << m["two"] << endl; // 输出映射m中键"two"对应的值，即2
    m.erase("two"); // 移除映射m中键"two"对应的键值对
    cout << m.count("two") << endl; // 输出映射m中键"two"的个数，即0
    return 0;
}

map与unordered_map的区别

map和unordered_map都是C++ STL中的关联容器，它们的区别在于底层实现的数据结构不同。
map是基于红黑树实现的，它的元素是有序的，而unordered_map是基于哈希表实现的，它的元素是无序的。
因此，map的查找、插入和删除操作的时间复杂度是O(logn)，而unordered_map的查找、插入和删除操作的时间复杂度是O(1)。
在实际应用中，如果需要元素有序，可以使用map；如果不需要元素有序，可以使用unordered_map。

---

元组：tuple

元组是一个包含多个元素的对象，可以方便地访问其中的元素。

int main()
{
    tuple<int, string, bool> t(1, "hello", true); // 创建一个包含整数、字符串和布尔值的元组对象t
    cout << get<0>(t) << endl; // 输出元组t中第一个元素，即1
    cout << get<1>(t) << endl; // 输出元组t中第二个元素，即"hello"
    cout << get<2>(t) << endl; // 输出元组t中第三个元素，即true
    return 0;
}