由于本科期间几乎只写java和前端，对STL一些常用容器不熟悉，经常刷题刷着刷着需要去查各种容器用法。于是此处记录一些常用的容器及相关语法

set/unordered_set性能分析和基本操作

set是基于红黑树实现的，内部元素有序。常用的操作如下：

#include<set>
using namespace std;

int main(){
    set<int> st;
    
    //插入元素 O(log n)
    st.insert(1);
    st.insert(2);
    ...

    //查找元素 O(log n)
    st.find(1);//查找1，如果找到，返回其迭代器
    st.find(3);//查找3，如果没找到，返回st.end()

    //删除元素 O(log n)
    st.erase(1);
    
    //foreach遍历
    for(auto &a : mp){
        cout << a << endl;
    }
    //迭代器遍历
    for(auto it = st.begin(); it != st.end(); it++){
        cout << *it<<endl;    
    }
}

unordered_set就是java中的HashSet，而C++中的Hash冲突默认采用哈希链表法(哈希桶)，因此时间复杂度在不同情况下并不一样。如果Hash函数能够均匀地分布元素，unordered_set各操作的时间复杂度基本都是O(1)；而如果堆集现象比较严重，极端情况下可能退化至O(n)。各操作语法和set基本一致

map/unordered_map性能分析和基本操作

和set一样，map底层同样基于红黑树，常用操作如下：

#include<map>
using namespace std;

int main(){
    map<int,string> mp;
    
    //插入元素 O(log n)
    mp.insert(make_pair(1,"aaa"));
    mp.insert(make_pair(2,"bbb"));
    ...

    //查找元素 O(log n)
    mp.find(1);//查找键为1的元素，如果找到，返回其迭代器
    mp.find(3);//查找键为3的元素，如果没找到，返回mp.end()

    //删除元素 O(log n)
    mp.erase(1);//删除键为1的元素

    //快速取元素
    cout << mp[1] << endl;//预期输出"aaa"

//foreach遍历
    for(auto &a : mp){
        cout << a.first << " " << a.second << endl;
    }
    //迭代器遍历
    for(auto it = mp.begin(); it != mp.end(); it++){
        cout << *it.first << " " << *it.second << endl;   
    }
}

unordered_map就是java中的HashMap，后端开发使用频率极高的数据结构。性能情况和unordered_set几乎一致

stack基本操作

stack所有操作时间复杂度均为O(1)，常用操作如下：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;

    // 检查栈是否为空
    std::cout << myStack.empty() << std::endl;

    // 压入元素
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 获取栈的大小
    std::cout << myStack.size() << std::endl;

    // 访问栈顶元素
    // 注意，栈为空时使用stack.top()会报错，因此使用前应先使用stack.empty()检查
    std::cout << myStack.top() << std::endl;

    // 弹出元素
    myStack.pop();

    return 0;
}

queue基本操作

queue所有操作时间复杂度均为O(1)，常用操作如下：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    // 检查队列是否为空
    std::cout << myQueue.empty() << std::endl;

    // 入队操作（push）：时间复杂度 O(1)
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // 获取队列大小（size）：时间复杂度 O(1)
    std::cout <<  myQueue.size() << std::endl;
    
    //front()和back()同样不能在队空时使用
    
    // 访问队首元素（front）：时间复杂度 O(1)
    std::cout << myQueue.front() << std::endl;

    // 访问队尾元素（back）：时间复杂度 O(1)
    std::cout << myQueue.back() << std::endl;

    // 出队操作（pop）：时间复杂度 O(1)
    myQueue.pop();

    return 0;
}

这里要注意的是，stack和queue中获取长度的size()时间复杂度是O(1)，因为它们内部时刻记录了容器长度

string基本操作和性能分析

1. 构造字符串

支持下列构造方式，时间复杂度O(n)

string str1 = "Hello";  // 从C字符串构造
string str2(5, 'a');    // 重复字符构造：aaaaa
string str3(str1);      // 复制构造

2. 赋值操作/字符串拼接

C++中的string支持直接修改，并且修改方式非常直观(重载运算符+)

str3 = "World";  // 赋值操作
string str4 = str1 + " " + str3; //拼接

3. 查找子串find()

find()函数有多个重载版本

首先说明会被频繁使用的size_t类型。size_t是一种无符号整数类型，通常是unsigned int或unsigned long的别名，用于标识字符在字符串中的位置。string::npos是一个常量，如果find()返回这个常量表示本次查找失败

size_t了解即可，实际上可以直接写成int

对于find(char ch) 或find(string str) ，默认从字符的起始位置开始查找：

string str = "Hello, world!";

// 查找字符 'o'  输出 'o' found at position: 4
int pos1 = str.find('o');
if (pos1 != string::npos) {
    cout << "'o' found at position: " << pos1 << std::endl;
} else {
    cout << "'o' not found" << std::endl;
}

// 查找子字符串 "world"  输出 "world" found at position: 7
int pos2 = str.find("world");
if (pos2 != string::npos) {
    cout << "\"world\" found at position: " << pos2 << std::endl;
} else {
    cout << "\"world\" not found" << std::endl;
}

对于find(char ch,size_t pos) 或find(string str, size_t pos) ，将从下标为pos的字符开始往后查找：

string str = "Hello, world!";

// 从下标为5的字符往后查找字符 'o'  输出 'o' found at position: 8
int pos1 = str.find('o',5);
if (pos1 != string::npos) {
    cout << "'o' found at position: " << pos1 << std::endl;
} else {
    cout << "'o' not found" << std::endl;
}

基于此，可以循环查找字符串内的所有子串：

string str = "Hello, world! otesto";

// 查找str中所有'o'的位置，输出 4 8 14 19
string str = "Hello, world! otesto";
int pos = str.find('o');
while(pos != string::npos){
    cout << pos << " ";
    pos = str.find('o',pos+1);
}

find()的时间复杂度在现代编译器中已经被各种混合策略优化的很好了，基本上接近O(n)。

4. 替换子串replace()/提取子串substr()

分别用于替换和提取指定位置开始长度为k的子串：

// 替换子串（时间复杂度：O(n)）
text.replace(pos, 6, "example");

// 提取子串（时间复杂度：O(m)）
string sub = text.substr(8, 7);  // 提取从索引8开始的7个字符

deque基本操作

deque是STL中的双端队列，或者可以看作操作更灵活的vector。它允许在两端push和pop的同时还支持以下标随机访问，不仅可以完全替代queue和stack，在手动实现一些C++不支持的数据结构(比如单调队列)时也会用到它

deque<int> dq;

dq.push_back(10); // 尾部插入
dq.push_front(5); // 头部插入

dq.pop_front(); // 删除头部
dq.pop_back();  // 删除尾部

dq.front(); // 访问头部
dq.back(); // 访问尾部

dq[0]; // 按下标访问，此时dq[0] == dq.front()

dq.insert(1,10); // 按下标插入
dq.erase(dq.begin()) // 按迭代器删除

priority_queue基本操作

C++提供的优先队列，默认大根堆。虽然名字叫队列，但是STL提供的接口操作方式却更像栈：

1. 基本操作

priority_queue<int> pq; // 创建优先队列

pq.push(10); // 插入元素
pq.top(); // 获取队头元素(堆顶)
pq.pop()；// 弹出队头元素(堆顶)

2. 自定义比较函数

priority_queue最恶心的就是自定义比较函数，比sort的写法麻烦很多，下面是需要自定义比较函数时的标准写法：

priority_queue<T, Container, Compare>

必须指明container，随便什么都行，一般用vector。

这里的Compare不能像sort一样简单传入一个比较函数，它有如下两种写法：

//第一种写法，不推荐使用，太麻烦了

struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
};

// 自定义比较函数
struct ComparePerson {
    bool operator()(const Person& a, const Person& b) {
        return a.age > b.age; // 按年龄从小到大排序
    }
};
priority_queue<Person, vector<Person>, ComparePerson> pq;

//第二种写法，函数指针
bool cmp(Person& a, Person& b){
    return a.age >= b.age;
}
priority_queue<Person, std::vector<Person>, decltype(&cmp)> pq(&cmp);

如果只是要改变常规类型的排序方向，可以用自带的比较器：

priority_queue<int, vector<int>, greater<int>> pq; //创建一个小根堆

greater<int>是返回a > b的比较器，因为小根堆用于降序排序。对应的还有less<int>。

make_heap及相关操作

C++STL容器支持make_heap()来将一个容器转换成堆，以支持其他堆操作：

这里注意，make_heap()中第三个参数是传递一个比较器实例，而priority_queue创建时第三个参数是模板参数。因此make_heap()第三个参数需要加括号，而priority_queue不能加括号

//创建堆
vector<int> vec = {10, 5, 20, 3, 7};
make_heap(vec.begin(), vec.end(),less<int>()); //将vec转换为一个大根堆

//插入堆
vec.push_back(15); // 插入新元素
push_heap(vec.begin(), vec.end());

//弹出堆顶
pop_heap(vec.begin(), vec.end()); // 将堆顶元素移至末尾
vec.pop_back(); // 移除堆顶元素(也可以不管，在之后的操作将迭代器写为vec.end()-1即可)

//堆排序
sort_heap(vec.begin(), vec.end()); // 将 vec 排序，顺序取决于make_heap时指定的顺序