浅谈STL

题外话：

~~上一世~~上一次STL总结在主页被删了，

~~这一世~~这一次~~我重生了~~我重写了一遍。

**(管理员大大求过)**

---

# STL（Standard Template Library，标准模板库）是 C++ 标准库的重要组成部分，提供了丰富的模板类和函数，可用于实现各种常见的数据结构和算法。

## STL 主要由容器（Containers）、算法（Algorithms）、迭代器（Iterators）、函数对象（Function objects）、适配器（Adapters）和分配器（Allocators）这六大组件构成。以下是对这些组件的详细介绍：

---

## STL提供了多种容器，每种容器都有其特定的用途和操作。以下是STL中所有容器的分类及其常用用法：

### **1. 序列容器（Sequence Containers）**
序列容器按顺序存储元素，支持随机访问或顺序访问。

#### **1.1 `vector`**
- **特点**：动态数组，支持快速随机访问。
- **常用操作**：
  ```cpp
  #include <vector>
  std::vector<int> v;

v.push_back(10);       // 在末尾插入元素
  v.pop_back();          // 删除末尾元素
  v.size();              // 返回元素数量
  v.at(0);               // 访问元素（带边界检查）
  v[0];                  // 访问元素（无边界检查）
  v.begin();             // 返回指向第一个元素的迭代器
  v.end();               // 返回指向末尾的迭代器
  v.erase(v.begin());    // 删除指定位置的元素
  v.clear();             // 清空容器
  ```

#### **1.2 `list`**
- **特点**：双向链表，支持高效插入和删除。
- **常用操作**：
  ```cpp
  #include <list>
  std::list<int> l;

l.push_back(10);       // 在末尾插入元素
  l.push_front(5);       // 在开头插入元素
  l.pop_back();          // 删除末尾元素
  l.pop_front();         // 删除开头元素
  l.size();              // 返回元素数量
  l.begin();             // 返回指向第一个元素的迭代器
  l.end();               // 返回指向末尾的迭代器
  l.erase(l.begin());    // 删除指定位置的元素
  l.clear();             // 清空容器
  ```

#### **1.3 `deque`**
- **特点**：双端队列，支持快速随机访问和在两端插入/删除。
- **常用操作**：
  ```cpp
  #include <deque>
  std::deque<int> d;

d.push_back(10);       // 在末尾插入元素
  d.push_front(5);       // 在开头插入元素
  d.pop_back();          // 删除末尾元素
  d.pop_front();         // 删除开头元素
  d.size();              // 返回元素数量
  d.at(0);               // 访问元素（带边界检查）
  d[0];                  // 访问元素（无边界检查）
  d.begin();             // 返回指向第一个元素的迭代器
  d.end();               // 返回指向末尾的迭代器
  d.erase(d.begin());    // 删除指定位置的元素
  d.clear();             // 清空容器
  ```

#### **1.4 `array`**
- **特点**：固定大小的数组，支持快速随机访问。
- **常用操作**：
  ```cpp
  #include <array>
  std::array<int, 5> a = {1, 2, 3, 4, 5};

a.size();              // 返回元素数量
  a.at(0);               // 访问元素（带边界检查）
  a[0];                  // 访问元素（无边界检查）
  a.begin();             // 返回指向第一个元素的迭代器
  a.end();               // 返回指向末尾的迭代器
  ```

#### **1.5 `forward_list`**
- **特点**：单向链表，只支持从前向后遍历。
- **常用操作**：
  ```cpp
  #include <forward_list>
  std::forward_list<int> fl;

fl.push_front(10);     // 在开头插入元素
  fl.pop_front();        // 删除开头元素
  fl.begin();            // 返回指向第一个元素的迭代器
  fl.end();              // 返回指向末尾的迭代器
  fl.erase_after(fl.begin()); // 删除指定位置之后的元素
  fl.clear();            // 清空容器
  ```

---

### **2. 关联容器（Associative Containers）**
关联容器基于键值对存储元素，支持快速查找。

#### **2.1 `set`**
- **特点**：有序集合，元素唯一。
- **常用操作**：
  ```cpp
  #include <set>
  std::set<int> s;

s.insert(10);          // 插入元素
  s.erase(10);           // 删除元素
  s.find(10);            // 查找元素
  s.size();              // 返回元素数量
  s.begin();             // 返回指向第一个元素的迭代器
  s.end();               // 返回指向末尾的迭代器
  s.clear();             // 清空容器
  ```

#### **2.2 `map`**
- **特点**：有序键值对集合，键唯一。
- **常用操作**：
  ```cpp
  #include <map>
  std::map<std::string, int> m;

m["key"] = 10;         // 插入或修改元素
  m.erase("key");        // 删除元素
  m.find("key");         // 查找元素
  m.size();              // 返回元素数量
  m.begin();             // 返回指向第一个元素的迭代器
  m.end();               // 返回指向末尾的迭代器
  m.clear();             // 清空容器
  ```

#### **2.3 `multiset`**
- **特点**：有序集合，元素可以重复。
- **常用操作**：
  ```cpp
  #include <set>
  std::multiset<int> ms;

ms.insert(10);         // 插入元素
  ms.erase(10);          // 删除元素
  ms.find(10);           // 查找元素
  ms.size();             // 返回元素数量
  ms.begin();            // 返回指向第一个元素的迭代器
  ms.end();              // 返回指向末尾的迭代器
  ms.clear();            // 清空容器
  ```

#### **2.4 `multimap`**
- **特点**：有序键值对集合，键可以重复。
- **常用操作**：
  ```cpp
  #include <map>
  std::multimap<std::string, int> mm;

mm.insert({"key", 10}); // 插入元素
  mm.erase("key");        // 删除元素
  mm.find("key");         // 查找元素
  mm.size();              // 返回元素数量
  mm.begin();             // 返回指向第一个元素的迭代器
  mm.end();               // 返回指向末尾的迭代器
  mm.clear();             // 清空容器
  ```

---

### **3. 无序关联容器（Unordered Associative Containers）**
无序关联容器基于哈希表实现，支持快速查找。

#### **3.1 `unordered_set`**
- **特点**：无序集合，元素唯一。
- **常用操作**：
  ```cpp
  #include <unordered_set>
  std::unordered_set<int> us;

us.insert(10);         // 插入元素
  us.erase(10);          // 删除元素
  us.find(10);           // 查找元素
  us.size();             // 返回元素数量
  us.begin();            // 返回指向第一个元素的迭代器
  us.end();              // 返回指向末尾的迭代器
  us.clear();            // 清空容器
  ```

#### **3.2 `unordered_map`**
- **特点**：无序键值对集合，键唯一。
- **常用操作**：
  ```cpp
  #include <unordered_map>
  std::unordered_map<std::string, int> um;

um["key"] = 10;        // 插入或修改元素
  um.erase("key");       // 删除元素
  um.find("key");        // 查找元素
  um.size();             // 返回元素数量
  um.begin();            // 返回指向第一个元素的迭代器
  um.end();              // 返回指向末尾的迭代器
  um.clear();            // 清空容器
  ```

#### **3.3 `unordered_multiset`**
- **特点**：无序集合，元素可以重复。
- **常用操作**：
  ```cpp
  #include <unordered_set>
  std::unordered_multiset<int> ums;

ums.insert(10);        // 插入元素
  ums.erase(10);         // 删除元素
  ums.find(10);          // 查找元素
  ums.size();            // 返回元素数量
  ums.begin();           // 返回指向第一个元素的迭代器
  ums.end();             // 返回指向末尾的迭代器
  ums.clear();           // 清空容器
  ```

#### **3.4 `unordered_multimap`**
- **特点**：无序键值对集合，键可以重复。
- **常用操作**：
  ```cpp
  #include <unordered_map>
  std::unordered_multimap<std::string, int> umm;

umm.insert({"key", 10}); // 插入元素
  umm.erase("key");        // 删除元素
  umm.find("key");         // 查找元素
  umm.size();              // 返回元素数量
  umm.begin();             // 返回指向第一个元素的迭代器
  umm.end();               // 返回指向末尾的迭代器
  umm.clear();             // 清空容器
  ```

---

### **4. 容器适配器（Container Adapters）**
容器适配器基于其他容器实现，提供特定的接口。

#### **4.1 `stack`**
- **特点**：后进先出（LIFO）栈。
- **常用操作**：
  ```cpp
  #include <stack>
  std::stack<int> s;

s.push(10);            // 压入元素
  s.pop();               // 弹出元素
  s.top();               // 访问栈顶元素
  s.empty();             // 判断栈是否为空
  s.size();              // 返回元素数量
  ```

#### **4.2 `queue`**
- **特点**：先进先出（FIFO）队列。
- **常用操作**：
  ```cpp
  #include <queue>
  std::queue<int> q;

q.push(10);            // 压入元素
  q.pop();               // 弹出元素
  q.front();             // 访问队首元素
  q.back();              // 访问队尾元素
  q.empty();             // 判断队列是否为空
  q.size();              // 返回元素数量
  ```

#### **4.3 `priority_queue`**
- **特点**：优先队列，元素按优先级排序。
- **常用操作**：
  ```cpp
  #include <queue>
  std::priority_queue<int> pq;

pq.push(10);           // 压入元素
  pq.pop();              // 弹出元素
  pq.top();              // 访问队首元素
  pq.empty();            // 判断队列是否为空
  pq.size();             // 返回元素数量
  ```

### **总结**
STL容器提供了丰富的数据结构和操作方法，能够满足大多数编程需求。熟练掌握这些容器的用法，可以大幅提高开发效率。

---

# C++ STL 容器及其完整用法指南

## 一、序列容器 (Sequence Containers)

### 1. vector
**特点**：动态数组，支持快速随机访问
```cpp
#include <vector>
std::vector<int> v;

// 基本操作
v.push_back(10);       // 末尾添加元素
v.pop_back();          // 删除末尾元素
v.insert(v.begin()+1, 20); // 指定位置插入
v.erase(v.begin()+1);  // 删除指定位置元素
v.clear();             // 清空容器

// 访问元素
int a = v[0];          // 无边界检查
int b = v.at(0);       // 有边界检查
int& front = v.front();// 第一个元素
int& back = v.back();  // 最后一个元素

// 容量操作
v.reserve(100);        // 预分配空间
v.shrink_to_fit();     // 减少容量以匹配大小
bool empty = v.empty();// 是否为空
size_t size = v.size();// 元素数量
size_t cap = v.capacity();// 当前容量

// 迭代器
for(auto it=v.begin(); it!=v.end(); ++it) {...}
for(auto& elem : v) {...}
```

### 2. list
**特点**：双向链表
```cpp
#include <list>
std::list<int> l;

// 基本操作
l.push_back(10);       // 末尾添加
l.push_front(5);       // 开头添加
l.pop_back();          // 删除末尾
l.pop_front();         // 删除开头
l.insert(++l.begin(), 20); // 指定位置插入
l.erase(l.begin());    // 删除指定位置
l.remove(10);          // 删除所有值为10的元素
l.unique();            // 删除连续重复元素
l.clear();             // 清空

// 合并与排序
std::list<int> l2 = {15,25};
l.merge(l2);           // 合并两个有序列表
l.sort();              // 排序
l.reverse();           // 反转

// 访问与大小
int& front = l.front();// 第一个元素
int& back = l.back();  // 最后一个元素
bool empty = l.empty();
size_t size = l.size();
```

### 3. deque
**特点**：双端队列
```cpp
#include <deque>
std::deque<int> d;

// 操作与vector类似，但支持两端操作
d.push_back(10);
d.push_front(5);
d.pop_back();
d.pop_front();
d.insert(d.begin()+1, 20);
d.erase(d.begin()+1);
d.clear();

// 访问元素
int a = d[0];
int b = d.at(0);
int& front = d.front();
int& back = d.back();

// 容量
bool empty = d.empty();
size_t size = d.size();
```

### 4. array (C++11)
**特点**：固定大小数组
```cpp
#include <array>
std::array<int, 5> arr = {1,2,3,4,5};

// 访问元素
int a = arr[0];
int b = arr.at(0);
int& front = arr.front();
int& back = arr.back();

// 迭代器
for(auto it=arr.begin(); it!=arr.end(); ++it) {...}

// 容量
bool empty = arr.empty();
size_t size = arr.size();

// 特殊操作
arr.fill(10);          // 填充所有元素为10
```

### 5. forward_list (C++11)
**特点**：单向链表
```cpp
#include <forward_list>
std::forward_list<int> fl;

// 基本操作
fl.push_front(10);     // 只能从前面添加
fl.pop_front();        // 只能从前面删除
fl.insert_after(fl.before_begin(), 20); // 在指定位置后插入
fl.erase_after(fl.before_begin()); // 删除指定位置后的元素
fl.clear();

// 特殊操作
fl.remove(10);         // 删除所有值为10的元素
fl.unique();           // 删除连续重复元素
fl.sort();             // 排序
fl.reverse();          // 反转

// 访问
int& front = fl.front();
bool empty = fl.empty();
```

## 二、关联容器 (Associative Containers)

### 1. set
**特点**：有序唯一元素集合
```cpp
#include <set>
std::set<int> s;

// 插入与删除
s.insert(10);
s.erase(10);
s.erase(s.begin());
s.clear();

// 查找
auto it = s.find(10);
if(it != s.end()) {...}
size_t count = s.count(10); // 0或1

// 范围查询
auto lb = s.lower_bound(5); // 第一个不小于5的元素
auto ub = s.upper_bound(15); // 第一个大于15的元素
auto range = s.equal_range(10); // 等于10的范围

// 访问与大小
bool empty = s.empty();
size_t size = s.size();
```

### 2. multiset
**特点**：有序可重复元素集合
```cpp
#include <set>
std::multiset<int> ms;

// 操作与set类似，但允许重复
ms.insert(10);
ms.insert(10); // 可以插入多次
size_t count = ms.count(10); // 可能大于1
ms.erase(10);  // 删除所有值为10的元素

// 删除单个元素
auto it = ms.find(10);
if(it != ms.end()) {
    ms.erase(it); // 只删除一个
}
```

### 3. map
**特点**：有序键值对，键唯一
```cpp
#include <map>
std::map<std::string, int> m;

// 插入与访问
m["apple"] = 5;        // 插入或修改
m.insert({"orange", 3});// 插入
auto [it, success] = m.insert({"apple", 10}); // 检查是否插入成功

// 删除
m.erase("apple");
m.erase(m.begin());
m.clear();

// 查找
auto it = m.find("apple");
if(it != m.end()) {
    std::string key = it->first;
    int value = it->second;
}

// 范围查询
auto lb = m.lower_bound("a");
auto ub = m.upper_bound("m");
auto range = m.equal_range("apple");

// 访问与大小
bool empty = m.empty();
size_t size = m.size();
```

### 4. multimap
**特点**：有序键值对，键可重复
```cpp
#include <map>
std::multimap<std::string, int> mm;

// 操作与map类似，但允许重复键
mm.insert({"apple", 5});
mm.insert({"apple", 7}); // 允许重复键

// 查找返回的是一个范围
auto range = mm.equal_range("apple");
for(auto it=range.first; it!=range.second; ++it) {
    // 处理所有"apple"键对应的值
}
```

## 三、无序关联容器 (Unordered Containers)

### 1. unordered_set
**特点**：哈希集合，元素唯一
```cpp
#include <unordered_set>
std::unordered_set<int> us;

// 基本操作
us.insert(10);
us.erase(10);
us.find(10);
us.count(10);
us.clear();

// 桶接口
size_t buckets = us.bucket_count();
size_t bucket = us.bucket(10); // 元素所在的桶
size_t bucket_size = us.bucket_size(bucket);

// 哈希策略
us.load_factor();      // 当前负载因子
us.max_load_factor();  // 最大负载因子
us.rehash(100);        // 重新哈希
us.reserve(100);       // 预留空间

// 访问与大小
bool empty = us.empty();
size_t size = us.size();
```

### 2. unordered_multiset
**特点**：哈希集合，元素可重复
```cpp
#include <unordered_set>
std::unordered_multiset<int> ums;

// 操作与unordered_set类似，但允许重复
ums.insert(10);
ums.insert(10);
size_t count = ums.count(10); // 可能大于1
```

### 3. unordered_map
**特点**：哈希键值对，键唯一
```cpp
#include <unordered_map>
std::unordered_map<std::string, int> um;

// 基本操作
um["apple"] = 5;
um.insert({"orange", 3});
um.erase("apple");
auto it = um.find("apple");
um.clear();

// 桶接口和哈希策略与unordered_set相同

// 访问与大小
bool empty = um.empty();
size_t size = um.size();
```

### 4. unordered_multimap
**特点**：哈希键值对，键可重复
```cpp
#include <unordered_map>
std::unordered_multimap<std::string, int> umm;

// 操作与unordered_map类似，但允许重复键
umm.insert({"apple", 5});
umm.insert({"apple", 7});

// 查找返回的是一个范围
auto range = umm.equal_range("apple");
for(auto it=range.first; it!=range.second; ++it) {
    // 处理所有"apple"键对应的值
}
```

## 四、容器适配器 (Container Adapters)

### 1. stack
**特点**：LIFO栈
```cpp
#include <stack>
std::stack<int> s;

// 基本操作
s.push(10);            // 压栈
s.pop();               // 出栈
int top = s.top();     // 查看栈顶
bool empty = s.empty();
size_t size = s.size();

// 底层容器默认为deque，可以指定
std::stack<int, std::vector<int>> sv;
```

### 2. queue
**特点**：FIFO队列
```cpp
#include <queue>
std::queue<int> q;

// 基本操作
q.push(10);            // 入队
q.pop();               // 出队
int front = q.front(); // 队首
int back = q.back();   // 队尾
bool empty = q.empty();
size_t size = q.size();

// 底层容器默认为deque，可以指定
std::queue<int, std::list<int>> ql;
```

### 3. priority_queue
**特点**：优先队列
```cpp
#include <queue>
std::priority_queue<int> pq; // 默认大顶堆

// 基本操作
pq.push(10);           // 插入元素
pq.pop();              // 删除顶部元素
int top = pq.top();    // 查看顶部元素
bool empty = pq.empty();
size_t size = pq.size();

// 自定义比较函数
auto cmp = [](int a, int b) { return a > b; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> min_pq(cmp);

// 使用自定义类型
struct Item {
    int priority;
    std::string name;
    bool operator<(const Item& other) const {
        return priority < other.priority;
    }
};
std::priority_queue<Item> item_pq;
```

## 五、特殊容器

### 1. bitset
**特点**：固定大小的位集合
```cpp
#include <bitset>
std::bitset<8> bs(0b10101010); // 8位

// 访问与修改
bool bit = bs[0];      // 访问第0位
bs.set(0);             // 设置第0位为1
bs.reset(0);           // 设置第0位为0
bs.flip(0);            // 翻转第0位

// 位操作
bs &= 0b11110000;      // 与操作
bs |= 0b00001111;      // 或操作
bs ^= 0b11111111;      // 异或操作
bs <<= 2;              // 左移
bs >>= 1;              // 右移

// 查询
bool any = bs.any();   // 是否有1
bool none = bs.none(); // 是否全0
bool all = bs.all();   // 是否全1
size_t count = bs.count(); // 1的个数

// 转换
unsigned long ul = bs.to_ulong();
std::string str = bs.to_string();
```

## 六、C++17新增容器

### 1. string_view
**特点**：字符串的非拥有视图
```cpp
#include <string_view>
std::string str = "Hello World";
std::string_view sv(str);

// 操作与string类似，但不拥有数据
size_t len = sv.length();
char c = sv[0];
std::string_view sub = sv.substr(0, 5);
```

### 2. flat_map (C++23)
**特点**：扁平化map，性能优化
```cpp
// 待C++23标准正式发布后实现
```

## 七、容器通用操作

### 1. 迭代器操作
```cpp
// 所有容器都支持的迭代器操作
auto begin = c.begin(); // 开始迭代器
auto end = c.end();     // 结束迭代器
auto rbegin = c.rbegin(); // 反向开始
auto rend = c.rend();   // 反向结束

// C++11起支持的常量迭代器
auto cbegin = c.cbegin();
auto cend = c.cend();
```

### 2. 交换与比较
```cpp
// 交换两个容器
std::swap(c1, c2);
c1.swap(c2);

// 比较
bool eq = (c1 == c2);  // 是否相等
bool lt = (c1 < c2);   // 字典序比较
```

### 3. 分配器支持
```cpp
// 所有容器都支持自定义分配器
std::vector<int, MyAllocator<int>> v;
```

## 总结

STL容器提供了丰富的数据结构选择，每种容器都有其特定的应用场景和性能特征。掌握这些容器的完整用法对于编写高效、清晰的C++代码至关重要。在实际开发中，应根据具体需求选择合适的容器类型。

---

## 2. 算法（Algorithms）
STL 提供了大量的算法，用于对容器中的元素进行各种操作，如排序、查找、替换等。
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9};
    // 排序
    std::sort(vec.begin(), vec.end());
    // 查找
    auto it = std::find(vec.begin(), vec.end(), 4);
    if (it != vec.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    return 0;
}
```
---

## 3. 迭代器（Iterators）
迭代器是一种对象，用于遍历容器中的元素，类似于指针。STL 定义了五种迭代器：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。
```cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3};
    // 使用迭代器遍历容器
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}
```
---

## 4. 函数对象（Function objects）
函数对象是重载了()运算符的类或结构体的对象，可作为参数传递给算法。
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

// 函数对象
struct GreaterThan {
    int value;
    GreaterThan(int val) : value(val) {}
    bool operator()(int num) const {
        return num > value;
    }
};

int main() {
    std::vector<int> vec = {1, 3, 5, 2, 4};
    // 使用函数对象进行查找
    auto it = std::find_if(vec.begin(), vec.end(), GreaterThan(3));
    if (it != vec.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    return 0;
}
```
---

## 5. 适配器（Adapters）
适配器是一种特殊的容器或函数对象，用于修改其他容器或函数对象的接口。
```cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> st;
    st.push(1);
    st.push(2);
    std::cout << "Top: " << st.top() << std::endl;
    st.pop();
    std::cout << "Top after pop: " << st.top() << std::endl;
    return 0;
}
```
---

## 6. 分配器（Allocators）
分配器用于管理容器中元素的内存分配和释放。STL 提供了默认的分配器std::allocator，也可以自定义分配器。
```cpp
#include <iostream>
#include <vector>
#include <memory>

int main() {
    std::vector<int, std::allocator<int>> vec;
    vec.push_back(1);
    vec.push_back(2);
    for (int num : vec) {
        std::cout << num << " ";
    }
    return 0;
}
```
---

### 以上就是 C++ STL 的主要内容。

#### 通过合理使用这些组件，可以提高代码的复用性和开发效率。

---

##### 一个好用的网站 -> [Here](https://oi-wiki.org/)