C++标准模板库（STL）容器、算法、迭代器
一. STL（标准模板库）的概述
定义：STL（Standard Template Library）是C++标准库的一部分，它提供了一系列通用的模板类和函数，用于处理常见的编程任务，如数据存储、排序、搜索等，旨在提高代码的复用性和效率。
组成部分：STL主要由容器（Containers）、算法（Algorithms）和迭代器（Iterators）三大组件构成，此外还包括函数对象（Function objects）、适配器（Adapters）和分配器（Allocators）等辅助组件。
二. 容器（Containers）
1. 顺序容器 vector：
vector是一个动态大小的数组，可以在末尾快速插入和删除元素。它在内存中是连续存储的，这使得随机访问元素非常高效（时间复杂度为$O(1)$），但在中间插入或删除元素可能会比较慢（平均时间复杂度为$O(n)$，其中$n$是容器中的元素个数）。
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for (size_t i = 0; i < v.size(); i++) {
std::cout << v[i] << " ";
}
return 0;
}2. 顺序容器 list：
list是一个双向链表，它的每个节点包含一个元素和指向前一个节点和后一个节点的指针。在list中任意位置插入和删除元素都非常快（时间复杂度为$O(1)$），但随机访问元素比较慢（时间复杂度为$O(n)$）。
#include <list>
#include <iostream>
int main() {
std::list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
for (auto it = l.begin(); it!= l.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}3. 顺序容器 deque（双端队列）：
deque（发音为“deck”）是一种双端队列，它类似于vector，但在两端插入和删除元素都非常高效（时间复杂度为$O(1)$）。deque内部的存储结构可能不是连续的，而是由多个固定大小的块组成。
#include <deque>
#include <iostream>
int main() {
std::deque<int> d;
d.push_back(1);
d.push_front(0);
for (size_t i = 0; i < d.size(); i++) {
std::cout << d[i] << " ";
}
return 0;
}4. 关联容器 set：
set是一个有序的集合，其中的元素是唯一的。它基于红黑树实现，插入、删除和查找操作的时间复杂度都是$O(\log n)$。set会自动对元素进行排序。
#include <set>
#include <iostream>
int main() {
std::set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
for (auto it = s.begin(); it!= s.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}5. 关联容器 map：
map是一个键 - 值对的有序集合，每个键在map中是唯一的。它基于红黑树实现，插入、删除和查找操作的时间复杂度都是$O(\log n)$。可以通过键快速查找对应的值。
#include <map>
#include <iostream>
int main() {
std::map<int, int> m;
m.insert(std::make_pair(1, 10));
m.insert(std::make_pair(2, 20));
m.insert(std::make_pair(3, 30));
for (auto it = m.begin(); it!= m.end(); ++it) {
std::cout << it->first << " " << it->second << " ";
}
return 0;
}6. 关联容器 unordered_set、关联容器 unordered_map（C++11及以上）：
这两个容器分别是set和map的无序版本，它们基于哈希表实现。插入、删除和查找操作在平均情况下的时间复杂度为$O(1)$，但在最坏情况下可能为$O(n)$。由于是无序的，所以不会对元素进行自动排序。
#include <unordered_set>
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(2);
for (auto it = us.begin(); it!= us.end(); ++it) {
std::cout << *it << " ";
}
std::unordered_map<int, int> um;
um.insert(std::make_pair(1, 10));
um.insert(std::make_pair(2, 20));
um.insert(std::make_pair(3, 30));
for (auto it = um.begin(); it!= um.end(); ++it) {
std::cout << it->first << " " << it->second << " ";
}
return 0;
}三. 算法（Algorithms）
1. 排序算法 std::sort：
对给定范围内的元素进行排序。它是一个快速排序的实现，平均时间复杂度为$O(n\log n)$，最坏情况下为$O(n^{2})$，但在实际应用中通常表现良好。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {3, 1, 2};
std::sort(v.begin(), v.end());
for (auto num : v) {
std::cout << num << " ";
}
return 0;
}2. 查找算法 std::find：
功能：在给定范围内查找指定元素，如果找到则返回指向该元素的迭代器，否则返回范围末尾的迭代器。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3};
auto it = std::find(v.begin(), v.end(), 2);
if (it!= v.end()) {
std::cout << "Element found";
} else {
std::cout << "Element not found";
}
return 0;
}四. 迭代器（Iterators）
定义与功能：迭代器是一种类似于指针的对象，用于遍历容器中的元素。不同类型的容器提供不同类型的迭代器，但它们都遵循一定的规范，使得可以使用相同的算法来操作不同类型的容器。
分类：
输入迭代器：可以从容器中读取元素，支持++（向前移动）操作和*（解引用）操作，但不支持多次解引用同一元素，也不支持--（向后移动）操作。
输出迭代器：用于向容器中写入元素，支持++操作和*操作，但解引用操作只能用于赋值，不能读取元素。
前向迭代器：兼具输入迭代器和输出迭代器的功能，并且支持多次解引用同一元素。
双向迭代器：在前向迭代器的基础上，支持--操作，可以双向遍历容器。
随机访问迭代器：除了双向迭代器的功能外，还支持随机访问元素，如it + n、it - n等操作，像vector容器提供的迭代器就是随机访问迭代器。
五. 函数对象（Function objects）、适配器（Adapters）和分配器（Allocators）
函数对象（Function objects）：也称为仿函数，是一个类，其重载了()运算符，使得类的对象可以像函数一样被调用。例如：
class Add {
public:
int operator()(int a, int b) {
return a + b;
}
};
int main() {
Add add;
int result = add(1, 2);
std::cout << result << " ";
return 0;
}适配器（Adapters）：用于修改或组合其他组件的行为。例如，std::bind是一个函数适配器，它可以绑定函数的部分参数，创建一个新的可调用对象。
分配器（Allocators）：负责为容器分配和回收内存。默认的分配器std::allocator在大多数情况下能够满足需求，但在一些特殊场景下，如需要定制内存分配策略时，可以创建自己的分配器。
