STL基本介绍：概述STL的组成和设计思想。
STL容器详解：分类介绍序列容器、关联容器和容器适配器，并提供代码示例。
STL算法详解：介绍常用算法的分类和使用方法，包含代码示例。
STL使用技巧与注意事项：提供性能优化和常见问题解决的技巧。

C++ STL 指南

1 STL 基本介绍

STL（Standard Template Library，标准模板库）是C++标准库的重要组成部分，提供了一个强大的、可复用的软件组件框架。STL包含了诸多在计算机科学领域常用的数据结构和算法，高度体现了软件的可复用性和泛型编程思想。STL的设计理念是将数据结构和算法分离，通过迭代器作为粘合剂，使同一个算法可以适用于不同的容器，大大提高了代码的复用性和开发效率。 STL的核心组成可以概括为三大组件：容器、算法和迭代器。实际上，STL还包含函数对象、适配器和分配器，这些组件共同构成了STL的强大功能体系。在C++编程中，STL就像一个强大的工具箱，里面装满了各种实用工具，可以帮助程序员更高效地开发功能强大且性能优异的应用程序。

2 STL 容器详解

容器是STL中用于存储和管理数据的数据结构,分为三大类：序列容器、关联容器和容器适配器。

2.1 序列容器

序列容器中的元素按线性顺序存储，每个元素都有固定的位置取决于插入的时机和地点。

2.1.1 vector（动态数组）[[vector]]

vector是一个动态数组，在内存中占用连续空间，支持随机访问，可以通过下标直接访问元素。当空间不足时，vector会自动进行扩容，通常每次扩容50%或100%。 常用操作：

push_back(): 在尾部插入元素
pop_back(): 删除尾部元素
size(): 返回元素个数
empty(): 判断是否为空
insert(): 在指定位置插入元素
erase(): 删除指定位置元素 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v;
    v.push_back(3);
    v.push_back(1);
    v.push_back(2);
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    cout<<"\n";
    v.pop_back();
    for(auto it=v.begin();it!=v.end();it++){
        cout<<*it<<" ";
    }
    return 0;
}

洛谷相关题目：P1177 排序 - 使用vector可以方便地存储数据并使用sort算法排序

2.1.2 list（双向链表）

list是一个双向链表，元素在内存中不是连续存储，每个元素包含指向前驱和后继的指针。list不支持随机访问，但在任意位置插入和删除元素都很高效。 常用操作：

push_back(), push_front(): 在尾部和头部插入元素
pop_back(), pop_front(): 删除尾部和头部元素
insert(): 在指定位置插入元素
remove(): 删除指定值的元素
sort(): 对链表排序 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    list<int>l;
    l.push_back(2);
    l.push_front(1);
    l.push_back(3);
    l.insert(++l.begin(),5);
    l.remove(2);
    l.sort();
    for(auto it=l.begin();it!=l.end();it++){
        cout<<*it<<" ";
    }
    return 0;
}

洛谷相关题目：P1160 队列安排 - 使用list可以高效地在任意位置插入和删除元素

2.1.3 deque（双端队列）

deque是一个双端队列，允许在头部和尾部快速插入和删除元素，同时支持随机访问。deque的内部实现类似于动态数组的数组，由多个连续的存储块组成。 常用操作：

push_back(), push_front(): 在尾部和头部插入元素
pop_back(), pop_front(): 删除尾部和头部元素
size(): 返回元素个数 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    deque<int>d;
    d.push_back(2);
    d.push_front(1);
    d.push_back(3);
    d.pop_front();
    for(int i=0;i<d.size();i++){
        cout<<d[i]<<" ";
    }
    return 0;
}

洛谷相关题目：P1886 滑动窗口 - 使用deque可以高效地在两端操作元素

2.2 关联容器

关联容器中的元素是排序的，通过键来存储和访问元素，提供快速的查找能力。

2.2.1 set/multiset（集合/多重集合）

set是一个有序集合，元素唯一，不允许重复。multiset允许元素重复。它们的底层通常通过红黑树实现。 常用操作：

insert(): 插入元素
find(): 查找元素
erase(): 删除元素
count(): 统计元素个数 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    set<int>s;
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(1);
    s.erase(2);
    if(s.find(3)!=s.end()){
        cout<<"Found"<<"\n";
    }
    cout<<s.count(1)<<"\n";
    for(auto it=s.begin();it!=s.end();it++){
        cout<<*it<<" ";
    }
    return 0;
}

洛谷相关题目：P5250 木材仓库 - 使用set可以自动去重并排序

2.2.2 map/multimap（映射/多重映射）

map是键值对的集合，键唯一，每个键对应一个值。multimap允许键重复。它们也是通过红黑树实现的。 常用操作：

insert({key, value}): 插入键值对
find(): 查找键
erase(): 删除键
[]: 通过键访问值 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    map<string,int>m;
    m.insert({"a",1});
    m["b"]=2;
    m["c"]=3;
    m.erase("b");
    if(m.find("a")!=m.end()){
        cout<<m["a"]<<"\n";
    }
    for(auto&p:m){
        cout<<p.first<<":"<<p.second<<" ";
    }
    return 0;
}

洛谷相关题目：P3370 字符串哈希 - 使用map可以方便地统计不同字符串的数量

2.3 容器适配器

容器适配器是对其他容器的封装，提供特定的接口。

2.3.1 stack（栈）

stack是一个后进先出（LIFO）的容器，只允许在栈顶操作元素。 常用操作：

push(): 压栈
pop(): 出栈
top(): 返回栈顶元素
empty(): 判断是否为空 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    stack<int>s;
    s.push(1);
    s.push(2);
    s.push(3);
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}

洛谷相关题目：P1449 后缀表达式 - 使用stack可以方便地计算后缀表达式

2.3.2 queue（队列）

queue是一个先进先出（FIFO）的容器，允许在尾部插入，头部删除。 常用操作：

push(): 入队
pop(): 出队
front(): 返回队首元素
back(): 返回队尾元素 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//和deque有啥区别？？？
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    queue<int>q;
    q.push(1);
    q.push(2);
    q.push(3);
    while(!q.empty()){
        cout<<q.front()<<" ";
        q.pop();
    }
    return 0;
}

洛谷相关题目：P1540 机器翻译 - 使用queue可以实现FIFO的缓存机制

2.3.3 priority_queue（优先队列）

priority_queue是一个优先级队列，元素按照优先级出队，默认是大顶堆。 常用操作：

push(): 插入元素
pop(): 删除顶部元素
top(): 返回顶部元素 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//priority不会拼qwq
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    priority_queue<int>pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

洛谷相关题目：P1090 合并果子 - 使用priority_queue可以高效地获取最小或最大值

3 STL 算法详解

STL算法是可以应用于不同容器上的通用函数模板，它们通过迭代器与容器交互。STL提供了大约100个实现算法的模板函数，主要包含在<algorithm>头文件中。事实证明，一般都用万能头文件

3.1 排序算法

3.1.1 sort

sort是STL中最常用的算法之一，用于对序列进行排序，平均时间复杂度为O(n log n)。简称懒人排序^_^ 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={3,1,4,1,5,9,2,6};
    sort(v.begin(),v.end());
    for(int i:v)cout<<i<<" ";
    cout<<endl;
    sort(v.begin(),v.end(),greater<int>());
    for(int i:v)cout<<i<<" ";
    return 0;
}

洛谷相关题目：P1177 排序 - 直接应用sort排序

3.1.2 stable_sort

stable_sort与sort类似，但可以保持相等元素的相对顺序，适用于需要稳定排序的场景。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//弥补了sort的不稳定喵~
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<pair<int,int>>v={{1,2},{3,1},{2,3},{1,1}};
    stable_sort(v.begin(),v.end());
    for(auto&p:v)cout<<p.first<<","<<p.second<<" ";
    return 0;
}

3.1.3 partial_sort

partial_sort可以对序列的部分元素进行排序。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//不太会，没啥用（bushi）
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={5,3,1,4,2,6};
    partial_sort(v.begin(),v.begin()+3,v.end());
    for(int i:v) cout<<i<<" ";
    return 0;
}

3.2 查找算法

3.2.1 find

find用于在序列中查找特定值，返回指向该元素的迭代器，如果找不到则返回尾迭代器。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3,4,5};
    auto it=find(v.begin(),v.end(),3);
    if(it!=v.end()){
        cout<<"Found at position:"<<it-v.begin()<<endl;
    }
    return 0;
}

3.2.2 binary_search

binary_search在有序序列中执行二分查找，返回布尔值表示是否找到。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//依旧没啥用
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3,4,5};
    bool found=binary_search(v.begin(),v.end(),3);
    cout<<(found?"Found":"Not found")<<endl;
    return 0;
}```
#### 3.2.3 lower_bound 和 upper_bound
lower_bound返回第一个**大于等于**指定值的元素位置，upper_bound返回第一个**大于**指定值的元素位置。
**代码示例：**
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//懒人二分
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3,3,3,4,5};
    auto lb=lower_bound(v.begin(),v.end(),3);
    auto ub=upper_bound(v.begin(),v.end(),3);
    cout<<"Number of 3s:"<<ub-lb<<endl;
    cout<<"First 3 at:"<<lb-v.begin()<<endl;
    return 0;
}

洛谷相关题目：P2249 有序序列中查找元素 - 使用lower_bound和upper_bound解决问题

3.3 数值算法

3.3.1 accumulate

accumulate用于计算序列中元素的累加和。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//不错
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3,4,5};
    int sum=accumulate(v.begin(),v.end(),0);
    cout<<"Sum:"<<sum;
    return 0;
}

3.3.2 partial_sum

partial_sum用于计算序列的部分和，即前缀和。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//STL大法好，但是如果是输入数组就没啥用qwq
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3,4,5},res(5);
    partial_sum(v.begin(),v.end(),res.begin());
    for(int i:res)cout<<i<<" ";
    return 0;
}

洛谷相关题目：P8218 求区间和 - 使用partial_sum计算前缀和

3.4 其他实用算法

3.4.1 next_permutation

next_permutation用于生成序列的下一个排列，常用于全排列问题。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3};
    do{
        for(int i:v)cout<<i<<" ";
        cout<<endl;
    }while(next_permutation(v.begin(),v.end()));
    return 0;
}

洛谷相关题目：P1706 全排列问题 - 使用next_permutation生成全排列

3.4.2 reverse

reverse用于反转序列中的元素顺序。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,3,4,5};
    reverse(v.begin(),v.end());
    for(int i:v)cout<<i<<" ";
    return 0;
}

3.4.3 unique

unique用于去除序列中的相邻重复元素，通常需要先排序。 代码示例：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//初赛时以为是全排列qwq，英语不好脑子也不好
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    vector<int>v={1,2,2,3,3,3,4,5};
    auto it=unique(v.begin(),v.end());
    v.erase(it,v.end());
    for(int i:v)cout<<i<<" ";
    return 0;
}

洛谷相关题目：P1138 第k小整数 - 使用unique去重

4 STL 使用技巧与注意事项

4.1 性能优化技巧

选择合适的容器：根据具体需求选择最合适的容器

需要随机访问：vector
频繁在中间插入删除：list
需要快速查找：set/map
FIFO操作：queue
LIFO操作：stack

4.2 常见问题与解决

迭代器失效问题：某些容器操作会使迭代器失效
- vector插入/删除元素后，之后位置的迭代器都失效
- list插入不会使迭代器失效，删除只会使被删除元素的迭代器失效
算法与容器匹配：某些算法对容器有特定要求
- sort、binary_search需要随机访问迭代器，list不能使用
- list有自己的sort成员函数，效率更高
自定义比较函数：对于自定义类型，需要提供比较函数

CPP

struct Node{
    int id,val;
};
bool cmp(const Node&a,const Node&b){
    return a.val<b.val;
}
vector<Node>v;
sort(v.begin(),v.end(),cmp);

5 总结

C++ STL是一个功能强大、设计精巧的软件库，它通过容器、算法、迭代器三大核心组件，以及函数对象、适配器和分配器等辅助组件，为C++程序员提供了丰富的工具集。掌握STL不仅可以提高开发效率，还能写出性能更好、更健壮的代码。~~其实就是懒人小妙招~~ 熟练掌握后，你会发现STL是一个不可或缺的得力助手。~~懒人离不开STL~~

STL

文章操作