STL库笔记

前言

Pigmaei gigantum humeris impositi plusquam ipsi gigantes vident (If I have seen further it is by standing on the shoulders of Giants.) —Isaac Newton

自己能够造轮子（明白排序、筛选、链表、二叉树等是具体如何实现）后，除非具体化、特例化的题目用自己的轮子比较快时，大多数情况可以使用stl库来简化代码。

STL库是C++标准库的一部分，它提供了许多有用的数据结构和算法，使得程序员可以更方便地编写高效、可维护的代码。STL库中的数据结构包括容器、迭代器、算法和函数对象等，它们可以用于处理各种数据类型和操作。

容器

容器是存储数据的基本单位，STL库提供了多种容器，包括：

• 序列容器：vector、deque、list
• 关联容器：set、map、multiset、multimap
• 容器适配器：stack、queue、priority_queue
• 无序关联容器：unordered_set、unordered_map、unordered_multiset、unordered_multimap

使用样例代码格式：

1. 声明变量：

{$容器名} <{$元素类型}> {$变量名};

例如：

• std::vector <int> a;
• std::set <std::string> strSet;
• std::map <int, std::string> mp_int_to_str;
• std::list<double> numList;

1. 使用函数：

{$变量名}.{$函数名}({参数});

例如：

• a.push_back(1);
• strSet.insert("hello");
• mp_int_to_str[1] = "world";
• numList.push_back(3.14);

以下使用容器都默认使用std::命名空间

vector数组

vector是一种动态数组，它可以自动调整大小以适应存储的数据。vector的元素按照顺序存储，可以通过索引访问元素。

使用样例代码格式：

声明变量：

vector <{$元素类型}> {$变量名};

使用案例代码格式：

{$变量名}.{$函数名}({参数});

例如：

• vector <int> a(5,1);声明一个一维数组，元素类型为int，变量名为a，初始大小为5，元素全为1
• vector <string> strVec;声明一个一维数组，元素类型为string，变量名为strVec
• vector <vector<int>> dp(7, vector<int> (5, 1));声明一个二维数组，元素类型为vector，变量名为dp，大小为7行5列的二维数组，元素全为1
• vector <vector<<vector<int>>>> dp3(4，vector<vector<int>>(5,vector<int>(6)));声明一个三维数组，元素类型为vector，变量名为dp3，大小为4行5行6列的三维数组，效果上与int dp3[4][5][6];等效
• vector <int> arr[10005];使用数组来声明vector，元素类型为int，变量名为arr，大小为10005的数组，每个元素都是一个vector，可用于链式的向量图

案例：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    cout << "Print a 2D vector" << endl;
    vector <vector<int> > a(5, vector<int>(5,2));
    for(int i=0; i<a.size(); i++)
    {
        for(int j=0; j<a[i].size(); j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    vector<int> b(3,10);
    cout << "Print a vector with 3 elements each of value 10" << endl;
    for(int i=0; i<b.size(); i++) cout << b[i] << " ";
    cout << endl;
    b.resize(5);
    cout << "Resize the vector to 5 elements" << endl;
    for(int i=0; i<b.size(); i++) cout << b[i] << " "; cout << endl;
    b.push_back(23);
    cout << "Push back 23 to the vector" << endl;
    for(int i=0; i<b.size(); i++) cout << b[i] << " "; cout << endl;
    vector <int> c;
    c.assign(b.begin(), b.begin()+4);
    cout << "Copy first 4 elements of vector b to c" << endl;
    for(int i=0; i<c.size(); i++) cout << c[i] << " ";
    cout << endl;
    c.assign(b.begin()+1, b.end());
    cout << "Copy elements from index 1 to end of vector b to c" << endl;
    for(int i=0; i<c.size(); i++) cout << c[i] << " "; cout << endl;
    b.erase(b.begin()+1, b.begin()+5);
    cout << "Erase elements from index 1 to 5 of vector b" << endl;
    for(int i=0; i<b.size(); i++) cout << b[i] << " ";
    cout << endl;
    for(int i=1; i<6; i++) b.push_back(i*i-i*2+1);
    cout << "Push back elements from 1 to 5*(i*i-i*2+1) to vector b" << endl;
    for(int i=0; i<b.size(); i++) cout << b[i] << " "; cout << endl;
    cout << "Swap vector b and c" << endl;
    cout << "Before vector b: ";
    for(int i=0; i<b.size(); i++) cout << b[i] << " "; cout << endl;
    cout << "Before vector c: ";
    for(int i=0; i<c.size(); i++) cout << c[i] << " "; cout << endl;
    b.swap(c);
    cout << "After vector b: ";
    for(int i=0; i<b.size(); i++) cout << b[i] << " "; cout << endl;
    cout << "After vector c: ";
    for(int i=0; i<c.size(); i++) cout << c[i] << " "; cout << endl;
    vector <int> d;
    for(int i=1; i<10; i++) d.push_back(2*i-1);
    cout << "Create vector d with elements from 1 to 2*i-1, i=1 to 9" << endl << "Vector d: ";
    for(int i=0; i<d.size(); i++) cout << d[i] << " "; cout << endl;
    cout << "Use the elements of vector d as indices to access elements of vector c. if the index is out of range, use 0 instead" << endl;
    cout << "After vector c: ";
    for(int i=0; i<c.size(); i++) {int x; x=d[i]<c.size() ? c[d[i]] : 0; cout << x << " ";} cout << endl;
    b.pop_back();
    cout << "Pop back the last element of vector b" << endl;
    for(int i=0; i<b.size(); i++) cout << b[i] << " "; cout << endl;
    cout << "The back of vector b is " << b.back() << endl;
    cout << "The front of vector b is " << b.front() << endl;
    system("pause");
}

常用函数

vector的常用函数包括：

函数名	功能	参数	使用样例	说明
push_back	向末尾添加元素	元素	a.push_back(i);	将元素i添加到a的末尾
pop_back	删除末尾元素	无	a.pop_back();	删除a的最后一个元素
size	获取vector的大小	无	a.size();	返回a中元素的个数
empty	判断是否为空	无	a.empty();	判断a是否为空，返回true为空
begin	获取第一个元素的迭代器	无	a.begin();	返回指向a第一个元素的迭代器
end	获取最后一个元素的迭代器	无	a.end();	返回指向a最后一个元素的迭代器
insert	插入元素	迭代器，元素	a.insert(a.begin()+1, 2);	在a的第1位置插入元素2
erase	删除指定位置的元素	迭代器	a.erase(a.begin()+1);	删除a中第1个元素
clear	清空所有元素	无	a.clear();	删除a中所有元素
resize	改变vector大小	新大小	a.resize(5);	将a的大小调整为5
capacity	获取已分配的内存大小	无	a.capacity();	返回a已分配的内存大小
reserve	设置容量	容量	a.reserve(10);	设置a的容量为10
swap	交换两个vector	另一个vector	a.swap(b);	交换a和b的内容
assign	复制内容	另一个vector	a.assign(b.begin(), b.begin()+3);	复制b前3个元素到a
operator[]	索引访问元素	索引	a[0];	访问a第一个元素
front	获取第一个元素	无	a.front();	返回a的第一个元素
back	获取最后一个元素	无	a.back();	返回a的最后一个元素
emplace_back	向末尾添加元素并构造	元素	a.emplace_back(1);	将元素1添加到a末尾，并构造
emplace	在指定位置添加元素并构造	迭代器，元素	a.emplace(a.begin()+1, 2);	在a的第1位置添加元素2并构造

适用场景

一般vector可以替换掉普通数组，除非该题卡内存，否则一般使用vector即可。

有些情况下需要普通数组去实现：$n \times m$的矩阵，$1\leq n,m \leq 10^6且n \times m\leq 10^6$。

• 如果试图用普通数组int mat[100010][1000010];，则会浪费内存，导致MLE。
• 如果试图用vector<vector<int>> mat(n + 10,vector<int>(m + 10));，则会可以完美解决。

另外，vector数组中的数据存储在堆空间，不会爆栈，而普通数组存储在栈空间，会爆栈（这时可以尝试把普通数组放到全局变量，有可能解决问题）。

注意事项

提前开辟空间

如果长度时已知的，最好提前开辟空间，否则每次插入数据时，vector会进行扩容，时间复杂度会变为$O(n)$，所以最好提前开辟空间。

一个例子：

vector<int> a;
for(int i=1; i<=1e8; i++)
{
    a.push_back(i);
}
///这里使用了752ms
///优化为
vector<int> a(1e8 + 10);
for(int i=1; i<=1e8; i++)
{
    a[i] = i;
}
///这里使用了399ms

当心size_t溢出

vector获取长度的方法.size()返回值为size_t。有的OJ平台用的是32位编译器，那么此时类型的范围为$[0,2^{}32-1]$，当vector长度过大时，size_t会溢出，导致获取的长度为0。

vector<int> a(1e9 + 10);
cout<<a.size()<<endl;
///输出为0

vector的底层实现

vector的底层实现是一个动态数组，它可以在需要时自动调整大小。当向vector中添加元素时，如果数组已满，vector会创建一个新的数组，并将旧数组中的元素复制到新数组中，然后释放旧数组的内存。因此，vector的插入操作可能会比较耗时，特别是当数组需要频繁调整大小时。
具体代码：

#include <iostream>
#include <stdexcept>
#include <algorithm>
#include <iterator>
#include <memory>

template <typename T>
class MyVector {
private:
    T* data;          // 存储元素的指针
    size_t capacity_;  // 容量（分配的内存大小）
    size_t length;    // 当前元素数量

    // 扩容
    void resizeCapacity(size_t new_capacity) {
        T* new_data = new T[new_capacity];  // 分配新的内存
        for (size_t i = 0; i < length; ++i) {
            new_data[i] = std::move(data[i]);  // 移动旧数据
        }
        delete[] data;  // 释放旧的内存
        data = new_data;  // 更新指针
        capacity_ = new_capacity;  // 更新容量
    }

public:
    MyVector() : data(nullptr), capacity_(0), length(0) {}

    // 析构函数，释放内存
    ~MyVector() {
        delete[] data;
    }

    // push_back：在末尾添加一个元素
    void push_back(const T& value) {
        if (length == capacity_) {  // 容量已满，扩容
            resizeCapacity(capacity_ == 0 ? 1 : capacity_ * 2);
        }
        data[length] = value;
        ++length;
    }

    // pop_back：删除最后一个元素
    void pop_back() {
        if (empty()) {
            throw std::out_of_range("pop_back on empty vector");
        }
        --length;
    }

    // size：返回当前元素数量
    size_t size() const {
        return length;
    }

    // capacity：返回当前容量
    size_t capacity() const {
        return capacity_;
    }

    // empty：判断vector是否为空
    bool empty() const {
        return length == 0;
    }

    // begin：返回指向第一个元素的迭代器
    T* begin() {
        return data;
    }

    // end：返回指向最后一个元素后一个位置的迭代器
    T* end() {
        return data + length;
    }

    // insert：在指定位置插入元素
    void insert(size_t index, const T& value) {
        if (index > length) {
            throw std::out_of_range("insert index out of range");
        }
        if (length == capacity_) {
            resizeCapacity(capacity_ == 0 ? 1 : capacity_ * 2);
        }
        for (size_t i = length; i > index; --i) {
            data[i] = std::move(data[i - 1]);  // 移动元素
        }
        data[index] = value;
        ++length;
    }

    // erase：删除指定位置的元素
    void erase(size_t index) {
        if (index >= length) {
            throw std::out_of_range("erase index out of range");
        }
        for (size_t i = index; i < length - 1; ++i) {
            data[i] = std::move(data[i + 1]);  // 移动元素
        }
        --length;
    }

    // clear：清空vector中的所有元素
    void clear() {
        length = 0;
    }

    // resize：重新设置vector的长度
    void resize(size_t new_size) {
        if (new_size > capacity_) {
            resizeCapacity(new_size);
        }
        length = new_size;
    }

    // reserve：设置vector的容量
    void reserve(size_t new_capacity) {
        if (new_capacity > capacity_) {
            resizeCapacity(new_capacity);
        }
    }

    // swap：交换两个vector的内容
    void swap(MyVector& other) noexcept {
        using std::swap;
        swap(data, other.data);
        swap(capacity_, other.capacity_);
        swap(length, other.length);
    }

    // assign：将一个vector的内容复制到另一个vector中
    void assign(const MyVector& other) {
        if (this == &other) {
            return; // 防止自我赋值
        }
        delete[] data;
        capacity_ = other.capacity_;
        length = other.length;
        data = new T[capacity_];
        for (size_t i = 0; i < length; ++i) {
            data[i] = other.data[i];
        }
    }

    // operator[]：通过索引访问vector中的元素
    T& operator[](size_t index) {
        if (index >= length) {
            throw std::out_of_range("index out of range");
        }
        return data[index];
    }

    const T& operator[](size_t index) const {
        if (index >= length) {
            throw std::out_of_range("index out of range");
        }
        return data[index];
    }

    // front：返回vector的第一个元素
    T& front() {
        if (empty()) {
            throw std::out_of_range("front on empty vector");
        }
        return data[0];
    }

    const T& front() const {
        if (empty()) {
            throw std::out_of_range("front on empty vector");
        }
        return data[0];
    }

    // back：返回vector的最后一个元素
    T& back() {
        if (empty()) {
            throw std::out_of_range("back on empty vector");
        }
        return data[length - 1];
    }

    const T& back() const {
        if (empty()) {
            throw std::out_of_range("back on empty vector");
        }
        return data[length - 1];
    }

    // emplace_back：在vector的末尾添加一个元素，并调用其构造函数
    template <typename... Args>
    void emplace_back(Args&&... args) {
        if (length == capacity_) {
            resizeCapacity(capacity_ == 0 ? 1 : capacity_ * 2);
        }
        new (&data[length]) T(std::forward<Args>(args)...); // 在末尾构造元素
        ++length;
    }

    // emplace：在指定位置添加一个元素，并调用其构造函数
    template <typename... Args>
    void emplace(size_t index, Args&&... args) {
        if (index > length) {
            throw std::out_of_range("emplace index out of range");
        }
        if (length == capacity_) {
            resizeCapacity(capacity_ == 0 ? 1 : capacity_ * 2);
        }
        for (size_t i = length; i > index; --i) {
            data[i] = std::move(data[i - 1]);  // 移动元素
        }
        new (&data[index]) T(std::forward<Args>(args)...); // 在指定位置构造元素
        ++length;
    }
};

int main() {
    MyVector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(5);

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    vec.pop_back();
    vec.pop_back();

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    vec.erase(1);

    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    system("pause");
    return 0;
}

list 链表

list 是 STL 中的双向链表实现，支持常数时间的插入和删除操作，但不支持直接访问元素。它可以高效地在中间进行元素插入和删除，但随机访问效率较差。

特性	list	forward_list	deque
底层数据结构	双向链表	单向链表	双端队列（双向动态数组）
访问方式	双向访问（支持前后访问）	单向访问（只能从头部访问）	支持随机访问（通过下标访问）
插入与删除操作	高效（在任意位置插入和删除元素的时间复杂度是 O(1)）	高效（只能在前面插入和删除，时间复杂度是 O(1)）	高效（两端插入和删除操作是 O(1)，但中间插入和删除是 O(n)）
内存占用	较大（每个元素需要存储两个指针）	较小（每个元素只需要存储一个指针）	较小（内存连续分配，但支持两端操作）
是否支持随机访问	❌（不支持直接访问元素，需要通过迭代器遍历）	❌（只能通过迭代器访问，不能随机访问）	✔️（支持随机访问，可以通过下标访问元素）
是否支持直接访问头部/尾部元素	✔️（可以通过 front() 和 back() 访问）	✔️（可以通过 front() 访问）	✔️（可以通过 front() 和 back() 访问）
内存分配	非连续内存（链表节点是动态分配的）	非连续内存（链表节点是动态分配的）	连续内存（类似数组）

使用样例代码格式：

声明list：

list <{$元素类型}> {$变量名};

• 元素类型：即要存储的元素类型，比如int、double、string等。

list <int> lst;  // 存储整数的链表

常用函数：

函数名	功能	参数	使用样例	说明
empty()	判断链表是否为空	无	if (lst.empty()) { ... }	判断链表lst是否为空
size()	获取链表的大小	无	int size = lst.size();	返回链表lst的元素个数
front()	获取链表的第一个元素	无	int firstElement = lst.front();	获取链表lst的第一个元素
back()	获取链表的最后一个元素	无	int lastElement = lst.back();	获取链表lst的最后一个元素
push_front()	在链表头部插入元素	元素	lst.push_front(10);	在链表lst的头部插入元素10
push_back()	在链表尾部插入元素	元素	lst.push_back(20);	在链表lst的尾部插入元素20
pop_front()	删除链表的第一个元素	无	lst.pop_front();	删除链表lst的第一个元素
pop_back()	删除链表的最后一个元素	无	lst.pop_back();	删除链表lst的最后一个元素
insert()	在指定位置插入元素	迭代器, 元素	lst.insert(it, 30);	在迭代器it指定的位置插入元素30
erase()	删除指定位置的元素	迭代器	lst.erase(it);	删除迭代器it指定的元素
clear()	清空链表	无	lst.clear();	删除链表中的所有元素

示例代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    list<int> lst;
    // Insert elements at the back of the list
    for(int i = 1; i <= 5; i++)
        lst.push_back(i);  // Insert elements 1, 2, 3, 4, 5 at the back of the list
    
    // Display the size and the first/last element
    cout << "The size of list is: " << lst.size() << endl;  // Display the size of the list
    cout << "The first element is: " << lst.front() << endl;  // Display the first element
    cout << "The last element is: " << lst.back() << endl;  // Display the last element
    
    // Insert elements at the front and back of the list
    lst.push_front(0);  // Insert element 0 at the front of the list
    lst.push_back(6);   // Insert element 6 at the back of the list
    
    cout << "After inserting, the list is: ";
    // Iterate over the list and print all elements
    for(auto ele : lst) cout << ele << " ";
    cout << endl;
    
    // Remove elements from the front and back of the list
    lst.pop_front();  // Remove the first element of the list
    lst.pop_back();   // Remove the last element of the list
    
    cout << "After popping, the list is: ";
    // Iterate over the list and print all elements after popping
    for(auto ele : lst) cout << ele << " ";
    cout << endl;
    
    // Use iterator for insertion and deletion
    auto it = lst.begin();
    advance(it, 2);  // Move the iterator to the third element
    lst.insert(it, 100);  // Insert element 100 at the position indicated by the iterator
    lst.erase(it);   // Remove the element at the position indicated by the iterator
    
    cout << "After inserting and erasing, the list is: ";
    // Iterate over the list and print all elements after insertion and erasure
    for(auto ele : lst) cout << ele << " ";
    cout << endl;

    // Clear all elements in the list
    lst.clear();  // Remove all elements from the list
    cout << "After clearing, the list size is: " << lst.size() << endl;  // Display the size after clearing
    
    system("pause");
}

适用场景

• 需要频繁进行插入和删除操作（尤其是在链表头或链表尾部）。
• 不需要频繁进行元素访问操作（链表不能像数组一样进行随机访问）。

注意事项

1. 不可随机访问元素：
   list 不能通过索引访问元素，访问需要使用迭代器。
   错误写法：

   cout << lst[2];  // 错误，不能通过索引访问链表元素

2. 链表大小的增加或删除操作：
   push_back()、push_front() 和 pop_back()、pop_front() 在链表的头部和尾部操作时效率较高，但如果涉及到在中间进行插入或删除，效率较低。

---

deque 双端队列

deque（双端队列）是一种可以在头部和尾部都进行高效插入和删除的容器。它是一个线性数据结构，可以在常数时间内进行插入和删除，但不像链表一样提供高效的中间插入。

使用样例代码格式：

声明deque：

deque <{$元素类型}> {$变量名};

• 元素类型：即要存储的元素类型，比如int、double、string等。

deque <int> dq;  // 存储整数的双端队列

常用函数：

函数名	功能	参数	使用样例	说明
empty()	判断双端队列是否为空	无	if (dq.empty()) { ... }	判断双端队列dq是否为空
size()	获取双端队列的大小	无	int size = dq.size();	返回双端队列dq的元素个数
front()	获取双端队列的第一个元素	无	int firstElement = dq.front();	获取双端队列dq的第一个元素
back()	获取双端队列的最后一个元素	无	int lastElement = dq.back();	获取双端队列dq的最后一个元素
push_front()	在队列头部插入元素	元素	dq.push_front(10);	在双端队列dq的头部插入元素10
push_back()	在队列尾部插入元素	元素	dq.push_back(20);	在双端队列dq的尾部插入元素20
pop_front()	删除队列的第一个元素	无	dq.pop_front();	删除双端队列dq的第一个元素
pop_back()	删除队列的最后一个元素	无	dq.pop_back();	删除双端队列dq的最后一个元素
clear()	清空队列	无	dq.clear();	删除双端队列中的所有元素

示例代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    deque<int> dq;
    // Insert elements at the back and front of the deque
    dq.push_back(10);  // Insert element 10 at the back
    dq.push_front(5);  // Insert element 5 at the front
    
    // Display the size and the first/last element
    cout << "The size of deque is: " << dq.size() << endl;  // Display the size of the deque
    cout << "The first element is: " << dq.front() << endl;  // Display the first element
    cout << "The last element is: " << dq.back() << endl;  // Display the last element
    
    // Remove elements from the front and back of the deque
    dq.pop_front();  // Remove the first element of the deque
    dq.pop_back();   // Remove the last element of the deque
    
    cout << "After popping, the deque is: ";
    // Iterate over the deque and print all elements
    for(auto ele : dq) cout << ele << " ";
    cout << endl;
    
    // Insert elements again at the front and back of the deque
    dq.push_front(100);  // Insert element 100 at the front
    dq.push_back(200);   // Insert element 200 at the back
    
    cout << "After inserting, the deque is: ";
    // Iterate over the deque and print all elements after insertion
    for(auto ele : dq) cout << ele << " ";
    cout << endl;
    
    // Clear all elements in the deque
    dq.clear();  // Remove all elements from the deque
    cout << "After clearing, the deque size is: " << dq.size() << endl;  // Display the size after clearing
    
    system("pause");
}

适用场景

• 需要在头尾部高效地进行插入和删除操作。
• 不需要频繁进行随机访问操作。

注意事项

1. 和list的区别：deque 在两端插入和删除效率高，而在中间操作可能较慢，尤其当容器大小较大时。list 是链表结构，适合大量中间元素的插入和删除。

2. 与数组的区别：deque 允许头尾两端的插入和删除操作，但随机访问效率不如数组。

stack 栈

通过二次封装的双端队列deque实现，只能从一端进行操作，后进先出。

使用样例代码格式：

声明stack：

stack <{$元素类型}> {$变量名};

常用函数：

函数名	功能	参数	使用样例	说明
empty()	判断栈是否为空	无	if (s.empty()) { ... }	判断栈s是否为空
size()	获取栈的大小	无	int size = s.size();	返回栈s的元素个数
top()	获取栈顶元素	无	int topElement = s.top();	获取栈顶元素
push()	向栈顶添加元素	元素	s.push(10);	将元素10添加到栈顶
pop()	移除栈顶元素	无	s.pop();	移除栈顶元素
emplace()	向栈顶添加元素并构造	元素	s.emplace(10);	在栈顶添加元素10并构造
swap()	交换两个栈的内容	另一个栈	s1.swap(s2);	交换栈s1和s2的内容

适用场景

如果不卡常，可以使用STL的stack。

另外，vector也可以模拟stack，但是vector的push_back和pop_back的时间复杂度是O(1)，而stack的push和pop的时间复杂度也是O(1)，所以vector模拟stack的时间复杂度也是O(1)。

注意事项

不能访问内部元素！！！下面是错误用法：

for(int i=0; i<stk.size(); i++) cout << stk[i] << end;
for(auto ele : stk) cout << ele << end;

queue 队列

通过二次封装的双端队列deque实现，只能从一端进行操作，先进先出。

使用样例代码格式：

声明queue：

queue <{$元素类型}> {$变量名};

示例代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    queue <int> q1;
    for(int i=1;i<=10;i++)
        q1.push(i);
    cout << "The size of queue is: ";
    cout << q1.size() << endl;
    cout << "The front element is: ";
    while(!q1.empty()) {cout << q1.front() << " ";q1.pop();}
    cout << endl;
    cout << "The queue is empty: ";
    cout << (q1.empty()? "Yes" : "No") << endl;
    system("pause");
}

常用函数：

函数名	功能	参数	使用样例	说明
empty()	判断队列是否为空	无	if (q.empty()) { ... }	判断队列q是否为空
size()	获取队列的大小	无	int size = q.size();	返回队列q的元素个数
front()	获取队首元素	无	int frontElement = q.front();	获取队列q的队首元素
back()	获取队尾元素	无	int backElement = q.back();	获取队列q的队尾元素
push()	向队尾添加元素	元素	q.push(10);	将元素10添加到队列q的队尾
pop()	移除队首元素	无	q.pop();	移除队列q的队首元素
emplace()	向队尾添加元素并构造	元素	q.emplace(10);	在队列q的队尾添加元素10并构造
swap()	交换两个队列的内容	另一个队列	q1.swap(q2);	交换队列q1和q2的内容

适用场景

如果不卡常，可以使用STL的queue。

另外，deque也可以模拟queue，但是deque的push_back和pop_front的时间复杂度是O(1)，而queue的push和pop的时间复杂度也是O(1)，所以deque模拟queue的时间复杂度也是O(1)。

注意事项

不能访问内部元素！！下面是错误用法：

for(int i=0; i<q.size(); i++) cout << q[i] << end;
for(auto ele : q) cout << ele << end;

priority_queue 优先队列

提供常数时间的查找，对数时间的插入和提取，底层原理是二叉堆。

使用样例代码格式：

声明priority_queue：

priority_queue <{$元素类型, $容器, $比较器}> {$变量名};

• 元素类型：即要存储的元素类型，比如int、double、string等。
• 容器：即底层容器类型，默认为vector，也可以是deque。
• 比较器：即比较函数，默认为less，即大根堆。如果需要小根堆，可以使用greater。

priority_queue <int> q1;   \\\大根堆，top的元素是最大的
priority_queue <int, vector<int>, greater<int>> q2;  \\\小根堆，top的元素是最小的

这里涉及了比较器的使用，比较器是一个函数对象，用于比较两个元素的大小。STL库提供了两种比较器：less和greater。less表示小于，greater表示大于。如果需要自定义比较器，可以定义一个函数对象，重载operator()即可。还有lambda表达式的内容，我们之后再讲。

示例代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue <int> q1;
    for(int i=1;i<=10;i++)
        q1.push(i);// 默认大根堆
    for(int i=34;i>=12;i--)
        q1.push(i*2-(int)sqrt(i)); // 添加元素
    cout << "The size of priority_queue is: ";
    cout << q1.size() << endl;
    cout << "The top element is: ";
    while(!q1.empty()) {cout << q1.top() << " ";q1.pop();}
    cout << endl;
    cout << "The priority_queue is empty: ";
    cout << (q1.empty()? "Yes" : "No") << endl;
    priority_queue <int, vector<int>, greater<int> > q2; /// 小根堆
    for(int i=1,j=121;i<=10,j>=56;i++,j--)
    {
        if(i&1==1) q2.push(i);
        else q2.push(j-(int)sqrt(j));
    }
    cout << "The size of priority_queue, which is a small root heap, is: ";
    while(!q2.empty()) {cout << q2.top() << " ";q2.pop();}cout << endl;
    cout << "The priority_queue, which is a small root heap, is empty: ";
    cout << (q2.empty()? "Yes" : "No") << endl;
    system("pause");
}

常用函数：

函数名	功能	参数	使用样例	说明
empty()	判断优先队列是否为空	无	if (q.empty()) { ... }	判断优先队列q是否为空
size()	获取优先队列的大小	无	int size = q.size();	返回优先队列q的元素个数
top()	获取优先队列的队首元素	无	int topElement = q.top();	获取优先队列q的队首元素
push()	向优先队列添加元素	元素	q.push(10);	向优先队列q添加元素10
pop()	移除优先队列的队首元素	无	q.pop();	移除优先队列q的队首元素
emplace()	向优先队列添加元素并构造	元素	q.emplace(10);	向优先队列q的队首添加元素10并构造
swap()	交换两个优先队列的内容	另一个优先队列	q1.swap(q2);	交换优先队列q1和q2的内容

进出堆的时间复杂度是 $O(\log n)$ ，查找堆顶元素的时间复杂度是 $O(1)$ 。

适用场景

持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列中取出最大（或最小）的元素，可以使用优先队列。元素数量是 $n$ ，插入操作数量是 $k$ ：

• 每次插入后快排，时间复杂度是 $O(n \log n)$ ，总时间复杂度是 $O( k·n\log n)$ 。
• 使用优先队列，时间复杂度是 $O(k·\log n)$ 。

注意事项

1. 不可访问内部元素！！
   错误写法：

   for(auto ele : q) cout << ele << end;
   q[12];

2. 不可修改已经写入的值！！
   堆中的所有元素都不可以修改写入的值，因为修改后堆的有序性无法保证。如果需要修改，可以先删除该元素，再插入新的元素。

错误写法：

q.top() = 10;
q[10] = 10;

如果是堆顶元素，可以先删除，再插入：

q.pop();
q.push(10);

set 集合

提供对数时间的插入、删除和查找（时间复杂度为 $\log n$），底层原理是红黑树。

关于是否满足集合的三要素，如下表：

三要素	说明	set	multiset	unordered_set	unordered_multiset
确定性	相同输入总是产生相同的有序输出（有序性）	✔️（有序）	✔️（有序）	❌（无序、哈希存储）	❌（无序、哈希存储）
互异性	集合中的元素有且仅出现一次	✔️	❌（可重复）	✔️	❌（可重复）
无序性	集合中的元素没有顺序（底层哈希存储）	❌（有序，默认升序）	❌（有序，默认升序）	✔️	✔️

这里说到Hash，先简单介绍一下：

哈希容器是STL中非常高效的容器，适用于处理无序数据并且对查找、插入和删除有较高性能要求的场景。通过哈希函数，它们能够提供近乎常数时间的操作，使得在大数据量下的处理速度大大提高。

STL库中的Hash容器有这些，如表：

特性	unordered_set	unordered_multiset	unordered_map	unordered_multimap
底层数据结构	哈希表	哈希表	哈希表	哈希表
元素类型	单一元素（不允许重复）	单一元素（允许重复）	键值对（不允许重复键）	键值对（允许重复键）
是否有序	无序	无序	无序	无序
查找时间复杂度	O(1)（平均情况下）	O(1)（平均情况下）	O(1)（平均情况下）	O(1)（平均情况下）
插入和删除时间复杂度	O(1)（平均情况下）	O(1)（平均情况下）	O(1)（平均情况下）	O(1)（平均情况下）
是否支持重复元素	❌（不允许重复元素）	✔️（允许重复元素）	❌（键不允许重复）	✔️（允许重复键）
是否支持随机访问	❌（不能通过下标访问）	❌（不能通过下标访问）	✔️（支持通过下标访问）	✔️（支持通过下标访问）
底层哈希函数	默认使用 std::hash，可以自定义	默认使用 std::hash，可以自定义	默认使用 std::hash，可以自定义	默认使用 std::hash，可以自定义
常见用途	查找、去重	查找、计数重复元素	快速查找键值对	快速查找多个键值对

使用样例代码格式：

声明set：

set <{$元素类型, $比较器}> {$变量名};

示例代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    set <int> s1;///默认升序集合
    for(int i=1,j=121;i<=41,j>=23;i++,j--)
    {
        if(j%3==0 || j%5==0 ||j%7==0)
            s1.insert(j%4);
        else s1.insert((int)sqrt(i)+i);
    }
    cout << "The first method to thought of the set is : ";
    for(int ele:s1) cout << ele << " "; cout << endl;
    // or
    cout << "The second method to thought of the set is : ";
    set <int> :: iterator it; // iterator declaration（迭代器）
    for(it=s1.begin();it!=s1.end();it++) cout << *it << " "; cout << endl; 
    /// for(set<int>::iterator it=s1.begin();it!=s1.end();it++) cout << *it << " ";
    for(int i=1;i<=100;i++)
        if(s1.find(i)!=s1.end() && i%3==0) cout << i << "is divisible by 3 and is in the set" << endl;
        ///anothor way to find this element is if(s1.count(i))
    ///用set存储二维点集合
    set <pair<int,int>> s2;
    for(int i=12,j=10; i<=100,j<=69; i+=2,j+=3) s2.insert(make_pair(i,j));
    s2.insert({121,23});
    s2.insert(make_pair(23,123));
    s2.insert({23,121});
    cout << "The set of pair in 2D positon is : ";
    for(auto ele:s2) cout << "{" << ele.first << "," << ele.second << "}" <<"  ";
    /// follow the up method  in "x" to print the element
    system("pause");
}

常用函数：

函数名	功能	参数	使用样例	说明
empty()	判断集合是否为空	无	if (s.empty()) { ... }	判断集合s是否为空
size()	获取集合大小	无	int size = s.size();	返回集合s的元素个数
clear()	清空集合	无	s.clear();	清空集合s
insert()	向集合添加元素	元素	s.insert(10);	向集合s中添加元素10
emplace()	原地构造元素并添加到集合中	元素构造参数	s.emplace(10);	原地构造元素并添加到集合s
emplace_hint()	使用提示迭代器原地构造元素	迭代器，元素构造参数	s.emplace_hint(s.begin(), 10);	使用提示迭代器原地构造元素
erase()	删除集合中的元素	元素或迭代器	s.erase(10); 或 s.erase(s.begin());	从集合s中删除元素10或第一个元素
find()	查找元素	元素	auto it = s.find(10);	查找集合s中的元素10，如果存在返回迭代器，否则返回s.end()
count()	检查元素是否存在	元素	bool exists = s.count(10) > 0;	检查元素10是否存在于集合s中
lower_bound()	返回大于等于某个值的第一个元素	元素	auto it = s.lower_bound(10);	返回指向大于等于10的第一个元素的迭代器
upper_bound()	返回大于某个值的第一个元素	元素	auto it = s.upper_bound(10);	返回指向大于10的第一个元素的迭代器
equal_range()	返回等于某个值的范围	元素	auto range = s.equal_range(10);	返回等于10的元素范围（两个迭代器）
swap()	交换两个集合的内容	另一个集合	s1.swap(s2);	交换集合s1和s2的内容
begin()	返回指向第一个元素的迭代器	无	auto it = s.begin();	返回指向集合s第一个元素的迭代器
end()	返回指向最后一个元素之后的位置的迭代器	无	auto it = s.end();	返回指向集合s最后一个元素之后的位置的迭代器
rbegin()	返回指向最后一个元素的逆向迭代器	无	auto it = s.rbegin();	返回指向集合s最后一个元素的逆向迭代器
rend()	返回指向第一个元素之前的位置的逆向迭代器	无	auto it = s.rend();	返回指向集合s第一个元素之前的位置的逆向迭代器
cbegin()	返回指向第一个元素的常量迭代器	无	auto it = s.cbegin();	返回指向集合s第一个元素的常量迭代器
cend()	返回指向最后一个元素之后的位置的常量迭代器	无	auto it = s.cend();	返回指向集合s最后一个元素之后的位置的常量迭代器
crbegin()	返回指向最后一个元素的常量逆向迭代器	无	auto it = s.crbegin();	返回指向集合s最后一个元素的常量逆向迭代器
crend()	返回指向第一个元素之前的位置的常量逆向迭代器	无	auto it = s.crend();	返回指向集合s第一个元素之前的位置的常量逆向迭代器
key_comp()	获取用于比较键的比较器	无	auto comp = s.key_comp();	获取用于比较键的比较器对象
value_comp()	获取用于比较值的比较器	无	auto comp = s.value_comp();	获取用于比较值的比较器对象
max_size()	返回集合能容纳的最大元素数量	无	auto max_size = s.max_size();	返回集合s能容纳的最大元素数量
get_allocator()	获取集合的分配器对象	无	auto alloc = s.get_allocator();	获取集合s的分配器对象

适用情形

• 元素去重：由于set容器不允许有重复元素，因此set容器非常适合用于需要去重的场景。
  • 如：$ {1,22,22,33,1,2} $ -> $ {1,2,22,33} $
• 元素排序：由于set容器会自动对元素进行排序，因此set容器非常适合用于需要排序的场景。
  • 如：$ {1,22,22,33,1,2} $ -> $ {1,2,22,33} $
• 元素查找：由于set容器提供了高效的查找算法，因此set容器非常适合用于需要快速查找的场景。
  • 如：元素大小 $[-10^18,10^18]$ ，元素数量 $n\leq 10^6$ ，这时使用vis数组很容易MLE和TLE

注意事项

无下标索引

set虽然可以遍历，但其无下标索引（如s[12]），因此不能像数组一样通过下标访问元素，只能通过迭代器访问元素。

元素只读

set的迭代器是只读的（const 迭代器），不能通过迭代器修改元素的值。但可以通过 erase() 删除元素，也可以通过 insert() 添加新元素。

cout << st.begin() << endl;  ///正确，可读
*st.begin() = 1;  ///错误，不可写

不可以用迭代器计算下标

set的迭代器不能像vector一样相减得到下标。

auto it = st.find(2) //正确，返回指向2的迭代器
int index = it - st.begin();  ///错误，不能计算下标

map 映射

提供对数时间（即时间复杂度 $O(\log n)$ ）的有序键结构，键值唯一，键值对以<key, value>形式存储，键值对之间无序，底层代码实现为红黑树。

其特性如下表格：

性质	解释	map	mulitmap	unordered_map
互异性	一个键仅可在映射中出现一次	✔️	❌（任意次）	✔️
无序性	键是没有顺序的	❌（从小到大）	❌（从小到大）	✔️

使用样例代码格式：

1. 声明映射：

map<{$键类型}, {$值类型}, {$比较器}> {$变量名};

例如：

map<int, string> m;
map<int, string, greater<int>> m2;///使用greater<int>作为比较器，使map按从大到小排序
map<int, vector<vector<int>>> m3;///键为int，值为vector的二维数组，可以用来存储邻接表

1. 使用函数：

{$变量名}.{$函数名}({参数});

例如：

m.insert(pair<int, string>(1, "apple"));
m[2] = "banana";

使用样例：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    map<int, int> mp1;
    for(int i=1; i<=10; i++)
        mp1[i] = i*i - i*(int)sqrt(i) - i%2, mp1[i+10] = mp1[i], mp1[i+20] = mp1[i] - i;
    cout << "The map is: ";
    for(auto i: mp1) ///if you add '&' before 'i' then it can be write in map.
    ///or for(auto i = mp1.begin(); i != mp1.end(); i++)
    /// or for(int map<int, int>::iterator i = mp1.begin(); i != mp1.end(); i++)
        cout << i.first << "->" << i.second << "  "; cout << endl;
    cout << "The count of key(2) in the map is: ";
    cout << mp1.count(2) << endl;///to check if a key exists or not
    cout << "Find the key(26) in the map: ";
    cout << mp1.find(26)->first << "->" << mp1.find(26)->second << endl;///to find a key
    cout << "Find the key(23412) is exists or not: ";
    cout << (mp1.count(23412) ? "Yes" : "No") << endl;
    cout << "The size of the map is: " << mp1.size() << endl;
    ///delete ten keys randomly
    for(int i=1; i<=10; i++)
    {
        int key = rand() % 100;
        if(mp1.count(key)) mp1.erase(key);
        else 
        {
            i--;
            continue;
        }
    }
    cout << "After deleting ten keys randomly, the size of the map is: ";
    cout << mp1.size() << endl;
    cout << "The map is: ";
    /// use for(auto &[key, value]: mp1) to change the value of the key or print the key and value
    for(auto [key, value]: mp1) cout << key << "->" << value << "  "; cout << endl; ///this method is only available in C++17

    map<string, int> mp2; ///be uesd to store string as a key
    vector<string> v = {"apple", "banana", "orange", "grape", "mango","yellow", 
        "red", "blue", "green", "black", "white", 
        "car", "bike", "mottobike", "bus", "train", "plane", "ship", "boat", "car", "bike", "mottobike", "bus", "train", "plane", "ship", "boat"
        "apple", "banana", "orange", "grape", "mango", 
        "yellow", "red", "blue", "green", "black", "white",
        "pineapple","peach",
        "car","bike", "mottobike", "bus", "train"
        };
    for(string i: v) mp2[i]++; 
    ///or use for(int i=0; i<v.size(); i++) mp2[v[i]]++;
    cout << "The map is: " << endl;
    for(auto i: mp2) cout << "The word: " << i.first << " has been appeared  " << i.second << " times" << endl;
    // You can see that the print format follows the order from "a" to "z" in a sorted manner, which may be different from the input order.
    system("pause");
}

常用函数:

函数名	功能	参数	使用样例	样例说明
insert()	在映射中添加键值对	键值对	m.insert(pair<int, string>(1, "apple"));	在映射中添加键值对
[] 或 at()	使用键访问值	键	m[2] = "banana"; 或 m.at(2) = "banana";	使用键访问值，at() 会抛出异常
find()	在映射中查找键	键	auto it = m.find(1);	在映射中查找键
count()	检查键是否存在于映射中	键	bool exists = m.count(1) > 0;	检查键是否存在于映射中
erase()	从映射中删除键值对	键或迭代器	m.erase(1); 或 m.erase(m.begin());	从映射中删除键值对
size()	返回映射中键值对的数量	无	int size = m.size();	返回映射中键值对的数量
empty()	检查映射是否为空	无	bool isEmpty = m.empty();	检查映射是否为空
clear()	清空映射中的所有键值对	无	m.clear();	清空映射中的所有键值对
begin()	返回指向映射中第一个键值对的迭代器	无	auto it = m.begin();	返回指向映射中第一个键值对的迭代器
end()	返回指向映射中最后一个键值对的下一个位置的迭代器	无	auto it = m.end();	返回指向映射中最后一个键值对的下一个位置的迭代器
rbegin()	返回指向映射中最后一个键值对的逆向迭代器	无	auto it = m.rbegin();	返回指向映射中最后一个键值对的逆向迭代器
rend()	返回指向映射中第一个键值对的前一个位置的逆向迭代器	无	auto it = m.rend();	返回指向映射中第一个键值对的前一个位置的逆向迭代器
cbegin()	返回指向映射中第一个键值对的常量迭代器	无	auto it = m.cbegin();	返回指向映射中第一个键值对的常量迭代器
cend()	返回指向映射中最后一个键值对的下一个位置的常量迭代器	无	auto it = m.cend();	返回指向映射中最后一个键值对的下一个位置的常量迭代器
crbegin()	返回指向映射中最后一个键值对的常量逆向迭代器	无	auto it = m.crbegin();	返回指向映射中最后一个键值对的常量逆向迭代器
crend()	返回指向映射中第一个键值对的前一个位置的常量逆向迭代器	无	auto it = m.crend();	返回指向映射中第一个键值对的前一个位置的常量逆向迭代器
key_comp()	返回用于比较键的比较器对象	无	auto comp = m.key_comp();	返回用于比较键的比较器对象
value_comp()	返回用于比较值的比较器对象	无	auto comp = m.value_comp();	返回用于比较值的比较器对象
max_size()	返回映射能容纳的最大元素数量	无	auto max_size = m.max_size();	返回映射能容纳的最大元素数量
get_allocator()	返回用于分配映射元素的分配器对象	无	auto alloc = m.get_allocator();	返回用于分配映射元素的分配器对象

适用情形

需要维护映射关系，并且需要快速查找、插入和删除键值对时，可以使用 map。
例如，需要根据学生的学号查找学生的姓名，或者根据单词查找其出现的次数时，可以使用 std::map。

注意事项

中括号访问时默认值

如果使用中括号访问 map 对应键不存在时，会自动创建一个默认值，并返回该默认值。如果希望避免这种情况，可以使用 find() 函数来查找键是否存在，然后再进行访问。

map<chat, int> mp;
cout << mp.count('a') << endl;; // 输出 0，因为 'a' 不存在
mp['a'];                        // 即使什么也不做，'a' 也会被添加到 map 中，其值为 0
cout << mp.count('a') << endl;; // 输出 1，因为 'a' 已经存在
cout << mp['a'] << endl;;       // 输出 0，因为 'a' 的值为 0

不可以用迭代器计算下标

同样地，map 的迭代器不能像数组一样使用下标来访问元素，因为 map 的元素是键值对，而不是单个元素。如果需要访问 map 中的元素，可以使用迭代器来遍历 map，或者使用 find() 函数来查找特定的键。

auto it = mp.find('a');
int idx =  it - mp.begin(); // 错误，不能使用迭代器计算下标

string 字符串

顾名思义，就是来存储字符串的。

使用样例代码格式：

string {$变量名};
string {$变量名}({$长度},{$初值});
string {$变量名} = {$字符串};

常用函数：

函数名	功能	参数	使用样例	样例说明
operator+	连接两个字符串	字符串	string newStr = str1 + str2;	连接两个字符串
operator+=	在字符串末尾添加另一个字符串	字符串	str += " world";	在字符串末尾添加另一个字符串
operator==	比较两个字符串是否相等	字符串	bool isEqual = str1 == str2;	比较两个字符串是否相等
size()	返回字符串中字符的数量	无	int size = str.size();	返回字符串中字符的数量
length()	返回字符串中字符的数量	无	int length = str.length();	返回字符串中字符的数量
empty()	检查字符串是否为空	无	bool isEmpty = str.empty();	检查字符串是否为空
clear()	清空字符串	无	str.clear();	清空字符串
substr()	返回字符串的子串	起始位置，长度	string subStr = str.substr(1, 3);	返回字符串的子串
find()	查找子串在字符串中的位置	子串，起始位置	int pos = str.find("abc", 0);	查找子串在字符串中的位置
rfind()	查找子串在字符串中的位置（从后向前）	子串，起始位置	int pos = str.rfind("abc", 0);	查找子串在字符串中的位置（从后向前）
replace()	替换字符串中的子串	起始位置，长度，替换子串	str.replace(1, 3, "XYZ");	替换字符串中的子串
insert()	在指定位置插入子串	起始位置，子串	str.insert(2, "abc");	在指定位置插入子串
erase()	删除指定位置的子串	起始位置，长度	str.erase(2, 3);	删除指定位置的子串
append()	在字符串末尾添加内容	子串	str.append(" world");	在字符串末尾添加内容
c_str()	返回字符串的 C 风格字符串（const char*）	无	const char* cstr = str.c_str();	返回字符串的 C 风格字符串
compare()	比较两个字符串	另一个字符串	int result = str.compare("abc");	比较两个字符串
to_string()	将数字转换为字符串	数字	string numStr = to_string(123);	将数字转换为字符串

适用场景

很好用的字符串类，让我忘记C语言中的字符串😅。

注意事项

尾接字符串一定要用+=

string的+=运算符，将会在原字符串的末尾添加新的字符串，而+会创建一个新的字符串对象，并将原字符串和新字符串的内容复制到新的对象中。因此，使用+=运算符可以避免不必要的内存分配和复制操作，提高程序的性能。

string s(100,'-');
for(int i=1; i<=1e8; i++) s = s + 'a'; ///运行for时间>=4409ms，直接TLE

string s(100,'-');
for(int i=1; i<=1e8; i++) s += 'a'; ///运行for时间257ms，十分高效

.substr()方法的奇葩函数

一定要注意，C++ string的取子串函数substr()的第一个参数是起始位置下标，第二个参数是长度，而不是结束位置。
例如，str.substr(1, 3)表示从字符串str的第二个字符开始，取长度为3的子串。

.find()方法的复杂度

该方法为暴力搜索，时间复杂度为 $O(n·m)$ 。
不要想着Cpp的find()函数用的是KMP算法。

手写KMP算法

这里提一嘴，手写KMP算法：

using namespace std;

class KMP
{
public:
    // 构造函数：构建 KMP 的部分匹配表
    KMP(const string& pattern)
    {
        this->pattern = pattern;
        next = buildNext(pattern);
    }

    // 查找主字符串中所有匹配子字符串的位置
    vector<int> search(const string& s)
    {
        vector<int> result;
        int n = s.length(), m = pattern.length();
        int j = 0;  // j 用来遍历模式串（子串）

        for (int i = 0; i < n; ++i)
        {
            while (j > 0 && s[i] != pattern[j])
                j = next[j - 1];  // 回溯
            if (s[i] == pattern[j])
                j++;  // 匹配成功，扩展匹配长度
            if (j == m) // 找到一个匹配
            {  
                result.push_back(i - m + 1);  // 记录匹配的起始位置
                j = next[j - 1];  // 根据部分匹配表跳转
            }
        }

        if (result.empty())
            result.push_back(-1);  // 如果没有找到，返回 -1
        return result;
    }

private:
    string pattern;
    vector<int> next;  // 部分匹配表

    // 构建部分匹配表（Next数组）
    vector<int> buildNext(const string& pattern)
    {
        int m = pattern.length();
        vector<int> next(m, -1);  // next数组的初始值为-1
        int j = 0;  // j 为前缀的长度
        for (int i = 1; i < m; ++i)
        {
            while (j > 0 && pattern[i] != pattern[j])
                j = next[j - 1];  // 回溯，利用已经匹配的部分信息
            if (pattern[i] == pattern[j])
                j++;  // 匹配成功，扩展前缀
            next[i] = j;  // 保存当前位置的前缀长度
        }
        return next;
    }
};
/*
时间复杂度为O(n+m)，其中n是主字符串的长度，m是子字符串的长度。
使用方法：
KMP kmp("abcabcaabcadbabdbasfabcadsbaacaabcccabcaabbbb");
vector<int> pos = kmp.search("abc");
if( pos.empty()) 
    cout << "No match found." << endl;
else 
    for(auto pos : pos) cout << pos << " "; // 输出匹配的起始位置
*/

pair 二元组

pair二元组是C++标准库中的一个模板类，用于存储两个不同类型的值。pair类定义在<utility>头文件中。

使用样例代码格式：

1. 声明pair对象：

pair <{$类型1}, {$类型2}> {$变量名};

例如：

pair <int, string> p1;
pair <int, string> p2(1, "apple");
pair <string, string> p3 = make_pair("你好", "hello");   ///C++老版本
pair <pair<int,int>,int> = {{1,2},3};    ///曲线救国三元组，实际上如果是存数据直接用struct就行

1. 访问pair对象的元素：

{$变量名}.first
{$变量名}.second

例如：

p1.first = 1;
p1.second = "hello";
int x = p1.first;
string str = p1.second;

常用函数

函数名	功能	参数	使用样例	样例说明
make_pair	创建一个 pair 对象	两个参数，分别表示 pair 对象的两个元素	pair<int, int> p = make_pair(1, 2);	创建一个 pair，第一个元素为1，第二个元素为2
first	获取 pair 的第一个元素	无	int x = p.first;	获取 pair 的第一个元素
second	获取 pair 的第二个元素	无	int y = p.second;	获取 pair 的第二个元素
pair	构造 pair 对象	两个参数，分别表示 pair 的两个元素	pair<int, string> p(1, "apple");	创建一个 pair，第一个元素为 1，第二个元素为 “apple”

适用场景

所有需要构造二元组的场景均可，效率和自己定义的struct结构体差不多。

注意事项

无

迭代器

迭代器是一种特殊的指针，它用于遍历容器中的元素。STL库提供了多种迭代器，包括：

• 输入迭代器：用于读取容器中的元素
• 输出迭代器：用于写入容器中的元素
• 前向迭代器：可以读取和写入容器中的元素，但不能修改元素
• 双向迭代器：可以读取和写入容器中的元素，并且可以向前或向后移动
• 随机访问迭代器：可以读取和写入容器中的元素，并且可以随机访问容器中的元素

具体使用，如：

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

这等价于：

for(auto it = vec.begin(); it != vec.end(); ++it)
    cout << *it << " ";

亦或是：

for(auto it : vec) cout << it << " ";
///或者
for(int i=0; i<vec.size(); i++) cout << vec[i] << " ";

值得注意的是：以上的等价遍历方式普遍只针对线性存储的数据结构，如vector。但对于非线性存储的数据结构，如map、set、unordered_map、unordered_set，是无法通过线性下标去遍历这个数据结构的，而迭代器就提供了这样无线性的遍历方法。

使用样例代码格式：

1. 声明迭代器：

{$容器名} <{$元素类型}> {$变量名};
{$容器名} <{$元素类型}> :: {$迭代器类型} {$变量名};

例如：

• vector <int>::iterator it;
• map<int, string>::iterator it;

1. 使用迭代器：

{$变量名} = {$容器名}.{$函数名}({参数});

例如：

• it = a.begin();
• it = strSet.find("apple");

常用迭代器

由于迭代器对于不同的容器有具体细微差别，这里以vector容器举例：

以下是简化并修正后的表格：

类别	功能描述	示例	关键说明
iterator	正向遍历元素（begin→end）	vector<int>::iterator it;	支持读写操作
reverse_iterator	反向遍历元素（rbegin→rend）	vector<int>::reverse_iterator rit;	实际方向与正向迭代器相反
.begin()	指向第一个元素	it = vec.begin();	正向起始位置
.end()	指向最后一个元素的下一个位置	it = vec.end();	表示结束哨兵
.rbegin()	指向最后一个元素	rit = vec.rbegin();	反向起始位置（等效end()-1）
.rend()	指向第一个元素的前一个位置	rit = vec.rend();	反向结束哨兵
++	移动到下一个元素	++it; / ++rit;	正向向后，反向向前
--	移动到上一个元素	--it; / --rit;	正向向前，反向向后
*	解引用获取元素值	int x = *it;	直接访问元素
+ n / - n	跳跃访问（仅随机访问迭代器支持）	it = it + 3;	直接移动指定偏移量
迭代器1 - 迭代器2	计算两迭代器间的元素数量	int d = it2 - it1;	结果可正可负
prev(it, n)	返回前移n个位置的迭代器（默认n=1）	auto p = prev(it, 2);	等效 it - n
next(it, n)	返回后移n个位置的迭代器（默认n=1）	auto n = next(it, 3);	等效 it + n

注意迭代器-迭代器这个操作不能在集合中使用

常见问题

.end()和.rend()指向的位置是毫无意义的值

对于一个长度为 $10$ 的数组int a[10]，那么其第 $10$ 位是不可访问的
对于一个长度为 $10$ 的vector容器vector<int> a(10)，那么其第 $10$ 位（即a.end()）也是不可访问的

不同迭代器的功能可能不一样

迭代器的细化方向有正向、反向、双向、随机访问四种，而不同的容器可能只支持其中一种或几种，因此在使用迭代器时需要特别注意其功能。
并且，不同容器提供的迭代器运算符也有所不同，如vector支持+ n、- n，而map则不支持。

删除操作需要警惕

举两个例子：

为什么4没有被删除呢？

vector<int> a = {1, 2, 3, 4, 5, 6};
for(auto it=a.begin(); it!=a.end(); ++it) 
    if(*it == 3 || *it == 4) a.erase(it);
for(auto it=a.begin(); it!=a.end(); ++it) cout << *it << " ";

输出结果为：1 2 4 5 6
因为erase函数会返回删除元素后的下一个元素的迭代器，而it在删除后已经指向了下一个元素，因此需要将it重新赋值为erase函数的返回值。
正确做法:

vector<int> a = {1, 2, 3, 4, 5, 6};
for(auto it=a.begin(); it!=a.end(); ) 
    if(*it == 3 || *it == 4) it = a.erase(it);
    else ++it;
for(auto it=a.begin(); it!=a.end(); ++it) cout << *it << " ";

为什么会RE？

vector<int> a = {1, 2, 3, 4, 5};
for(auto it=a.begin(); it!=a.end(); ++it)
    if(*it == 3 || *it == 5) a.erase(it);

因为erase函数会返回删除元素后的下一个元素的迭代器，而it在删除后已经指向了下一个元素，因此需要将it重新赋值为erase函数的返回值。
正确做法:

vector<int> a = {1, 2, 3, 4, 5};
for(auto it=a.begin(); it!=a.end(); ) 
    if(*it == 3 || *it == 5) it = a.erase(it);
    else ++it;

除非必要，建议不要随意用迭代器？你可不想在比赛时，大部分时间花在debug上吧😅

容器

算法

算法是用于操作容器中的元素的一系列操作。STL库提供了多种算法，包括：

• 排序算法：sort、stable_sort、partial_sort、nth_element、make_heap、push_heap、pop_heap
• 查找算法：find、find_if、binary_search、count、count_if、equal_range
• 修改算法：transform、fill、fill_n、copy、copy_if、replace、replace_if、swap、swap_ranges
• 生成算法：generate、generate_n、iota
• 逻辑算法：all_of、any_of、none_of、for_each
• 数值算法：accumulate、inner_product、adjacent_difference、partial_sum、adjacent_find
• 适配器算法：set_union、set_intersection、set_difference、set_symmetric_difference、merge

使用样例代码格式：

1. 使用算法：

{$算法名}({参数});

例如：

• std::sort(vec.begin(), vec.end());
• std::find(vec.begin(), vec.end(), 10);
• std::reverse(strSet.begin(), strSet.end());

常用算法

对于acm比赛来说，能让自己少打些代码，使用STL库内置的一些算法是极好的，虽然一些算法很简单，自己写也只要几行，而且有的还不是最佳的算法。

这里举例acm比赛常用的一些算法：

• 算法库<algorithm>

  • swap() : 交换两个变量的值
  • reverse() : 反转数组或容器中的元素
  • sort() : 排序数组或容器中的元素
  • low_bound() : 返回第一个大于等于指定值的元素的迭代器
  • upper_bound() : 返回第一个大于指定值的元素的迭代器
  • max() : 返回两个值中的最大值
  • min() : 返回两个值中的最小值
  • unique() : 去除数组或容器中的重复元素

• 数学函数库<cmath>

  • abs() : 返回一个数的绝对值
  • pow() : 返回一个数的幂
  • sqrt() : 返回一个数的平方根
  • log() : 返回一个数的自然对数
  • log2() : 返回一个数的以2为底的对数
  • log10() : 返回一个数的以10为底的对数
  • ceil() : 返回大于等于指定值的最小整数
  • floor() : 返回小于等于指定值的最大整数
  • round() : 返回最接近指定值的整数

• 数值算法库<numeric>

  • gcd : 计算两个数的最大公约数
  • lcm : 计算两个数的最小公倍数
  • partial_sum() : 计算数组或容器中元素的部分和

• 字符串函数库<string>

  • substr() : 返回子字符串
  • find() : 查找子字符串
  • replace() : 替换子字符串
  • erase() : 删除子字符串
  • insert() : 插入子字符串
  • compare() : 比较两个字符串
  • length() : 返回字符串的长度
  • empty() : 判断字符串是否为空
  • push_back() : 在字符串末尾添加一个字符
  • pop_back() : 删除字符串末尾的字符

下面是一些有必要说明的算法注意事项：

swap

1. 要注意变量的类型是否一致，否则可能会导致编译错误或逻辑错误。
2. 时间复杂度为 $O(1)$ 。

reverse

1. 要注意容器是否为空，否则可能会出现越界访问等问题。
2. 时间复杂度为 $O(n)$ 。

sort

1. 要注意自定义比较函数的正确性，否则可能会导致排序结果错误。
2. 时间复杂度为 $O(n \log n)$ ，在数据规模较大时，如n达到1e5以上，可能会出现超时的情况，需要考虑使用更高效的排序算法或优化数据结构。
3. sort比较器默认是从小到大排序，如果要实现从大到小排序，可以使用greater。以及，sort函数可以自定义比较器和使用lambda表达式。

vector<pair<int,int>> a = {{1,2},{2,3},{3,1},{4,5},{5,4},{-1,2},{-2,1},{1,12},{-12,0},{4,2},{2,2}};
sort(a.begin(), a.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.first*a.first + a.second*a.second < b.first*b.first + b.second*b.second;
});///这里就是用了lambda表达式，使得坐标按照直线距离升序排序

low_bound 和 upper_bound

1. 要注意序列是否已经排序，否则结果将不正确。因为这就是封装好的二分查找🤗。
2. 时间复杂度为 $O(\log n)$ 。

具体说明一下low_bound是返回到第一个 $\geq$ 某个数的迭代器，而upper_bound是返回到第一个 $>$ 某个数的迭代器。

那么需要返回下标时需要减去begin()即头指针。

vector <int> a = {1, 1, 2, 2, 2, 3, 4, 5, 7, 7, 8, 9};
int pos = lower_bound(a.begin(), a.end(), 2) - a.begin();
///找到第一个大于等于2的数，即2，下标为2

max 和 min

1. ，要注意参数的类型是否一致，否则可能会出现类型转换的问题。

如果使用的C++版本较高，那么可以使用如：maxn=max({2,5,1,76,12,31,4,1,45,23,543,1})这样的写法。

unique

1. 要注意该函数只是将相邻重复元素移到容器的后部，并返回一个指向不重复元素末尾的迭代器，不会自动改变容器的大小，需要手动处理。
2. 时间复杂度为 $O(n)$ 。

这里具体的删除相邻的重复元素举个例子：
{1,2,2,4,4,1,5,2,5,4} -> {1,2,4,1,5,2,5,4,5,4,?,?}

所以去重的代码是（这个代码不能在原数组上修改）

vector<int> a = {1, 2, 2, 4, 4, 1, 5, 2, 5, 4};
sort(a.begin(), a.end());
auto it = unique(a.begin(), a.end());
a.erase(it, a.end()); 
///或者一起写为a.erase(unique(a.begin(), a.end()), a.end());

这里也没必要用vector，实际上用set还更方便（自带去重）。

abs

1. 要注意参数的类型是否为整数类型，对于浮点数，应使用fabs()函数。

pow

1. 要注意参数的范围，如果底数为0且指数为负数，会导致运行时错误。
2. 时间复杂度为 $O(1)$ ，但是在某些情况下，pow函数的效率可能不如手写的快速幂函数（时间复杂度为 $O(\log n)$ ），尤其是当指数很大时。因为pow函数需要进行浮点运算，而浮点运算通常比整数运算慢。
3. 当处理整数幂运算时，pow函数可能会导致浮点数精度问题，进而引发整数溢出等问题。

sqrt log log2 log10

1. 要注意参数不能为负数，否则会导致结果为NaN。
2. 时间复杂度为 $O(1)$ 。

ceil() floor() round()

1. 这些函数在处理浮点数时，要注意精度问题，可能会出现与预期不符的结果。
2. 时间复杂度为 $O(1)$ 。

gcd lcm

1. 时间复杂度为 $O(\log n)$ 。

partial_sum

1. 要注意结果容器的大小是否足够，否则可能会出现越界访问等问题。
2. 时间复杂度为 $O(n)$ 。

copy

1. 要注意目标容器的大小是否足够，否则可能会出现越界访问等问题。
2. 时间复杂度为 $O(n)$ 。

这里具体说明下这个copy函数的用法：

copy({$源容器开始迭代器}, {$源容器结束迭代器}, {$目标容器开始迭代器})

例如：

vector<int> a = {1, 2, 3, 4, 5};
vector<int> b(5);
copy(a.begin(), a.end(), b.begin());

这里copy函数将a中的元素复制到b中，b的大小必须足够大，否则会导致越界访问。

函数对象

函数对象是一种特殊的对象，它可以像函数一样被调用。STL库提供了多种函数对象，包括：

• 一元函数对象：接受一个参数并返回一个值
• 二元函数对象：接受两个参数并返回一个值
• 仿函数：是一种特殊的函数对象，它可以被用作函数参数或返回值

使用样例代码格式：

1. 声明函数对象：

class {$类名} {
public:
    {$返回类型} operator()({参数列表}) {
        // 函数体
    }
};

例如：

• class Compare {
  public:
      bool operator()(int a, int b) {
          return a > b;
      }
  };

• class Add {
  public:
      int operator()(int a, int b) {
          return a + b;
      }
  };

1. 使用函数对象：

{$函数对象名} {$变量名}({参数});

例如：

• std::greater<int> comp;
• std::less<int> lessComp;
• std::sort(vec.begin(), vec.end(), comp); // 使用函数对象作为排序比较

常用函数对象

适配器

适配器是一种特殊的容器或算法，它可以改变容器或算法的行为。STL库提供了多种适配器，包括：

• 容器适配器：stack、queue、priority_queue
• 迭代器适配器：reverse_iterator、back_insert_iterator、front_insert_iterator、insert_iterator

使用样例代码格式：

1. 使用适配器：

{$适配器名} <{$元素类型}> {$变量名};

例如：

• std::stack<int> stk;
• std::queue<std::string> q;
• std::priority_queue<int> pq;
• std::reverse_iterator<std::vector<int>::iterator> revIt;

常用适配器