一、STL概述
C++ STL（Standard Template Library）是C++标准库的重要组成部分，它是一组通用的模板类和函数，实现了大量的常用数据结构和算法，为我们提供了高效、可靠和安全的工具，简化了程序设计和开发。STL库中包含了以下容器：
- 容器（Containers）
- 迭代器（Iterators）
- 算法（Algorithms）
- 函数对象（Function Objects）
- 适配器（Adapters）
STL库的设计理念是以泛型编程为基础，将数据类型和算法分开设计，使得数据结构和算法可以独立地发展和变换，从而实现代码的可重用性和可扩展性。
二、容器
容器是用于存储和管理数据的类模板，它们定义了一系列与数据操作有关的成员函数，可以快速地对数据进行插入、删除、查找等操作。常用的STL容器有以下几种：
1. vector
vector是一种动态数组，可以根据需要自动调整容量，实现高效的随机访问和插入/删除操作。例如：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}
输出结果为：1 2 3
2. list
list是一种双向链表，可以在任何位置进行插入和删除操作，但不支持随机访问。例如：
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
for (auto iter = l.begin(); iter != l.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 2 3
3. map
map是一种关联容器，可以将键值对（Key-Value）组合存储，支持按照键值进行查找和删除等操作。例如：
#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> m;
m["apple"] = 1;
m["banana"] = 2;
m["orange"] = 3;
for (auto iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}
输出结果为：
apple 1 banana 2 orange 3
三、迭代器
迭代器是一种通用的数据访问方式，可以方便地遍历STL容器中的元素，常用的迭代器类型有以下几种：
1. Input Iterator
Input Iterator是一个只读的迭代器，它可以对容器中的数据进行遍历和读取，例如：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
for (auto iter = v.begin(); iter != v.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 2 3
2. Output Iterator
Output Iterator是一个只写的迭代器，它可以向容器中写入数据，例如：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
for (auto iter = v.begin(); iter != v.end(); iter++) {
*iter *= 2;
}
for (auto iter = v.begin(); iter != v.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：2 4 6
3. Forward Iterator
Forward Iterator是一种单向的迭代器，它支持递增和取值操作，例如：
#include <iostream>
#include <forward_list>
using namespace std;
int main() {
forward_list<int> flist = {1, 2, 3};
for (auto iter = flist.begin(); iter != flist.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 2 3
4. Bidirectional Iterator
Bidirectional Iterator是一种双向的迭代器，它可以向前和向后遍历容器中的元素，例如：
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l = {1, 2, 3};
for (auto iter = l.rbegin(); iter != l.rend(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：3 2 1
5. Random Access Iterator
Random Access Iterator是一种随机访问的迭代器，可以快速定位到容器中的任意位置，并进行读写操作，例如：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
cout << v[1] << endl; // 输出 2
v[1] = 4;
for (auto iter = v.begin(); iter != v.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 4 3
四、算法
算法是STL库中非常重要的一部分，提供了大量的常用算法，包括查找、排序、遍历、合并等操作。
1. 查找
STL库中提供了多种查找算法，包括二分查找、线性查找、查找最大/最小值等。
例如，使用二分查找算法：（前提是数据序列已经排好序）
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[] = {1, 2, 3, 4, 5};
cout << binary_search(a, a + 5, 4) << endl; // 输出 1
return 0;
}
2. 排序
STL库中提供了多种排序算法，包括快速排序、归并排序、堆排序等，其中最常用的是快速排序。
例如，使用快速排序算法：（vector会使用快排）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {3, 1, 4, 2, 5};
sort(v.begin(), v.end());
for (auto iter = v.begin(); iter != v.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 2 3 4 5
3. 遍历
STL库中提供了多种遍历算法，包括for_each、transform等，这些算法可以对容器中的元素进行操作并输出。
例如，使用for_each算法将vector中的每个元素乘以2并输出：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int n) {
cout << n * 2 << " ";
}
int main() {
vector<int> v = {1, 2, 3};
for_each(v.begin(), v.end(), print);
return 0;
}
输出结果为：2 4 6
4. 合并
STL库中提供了多种合并算法，包括merge、set_union等，这些算法可以将多个有序的序列合并成一个有序的序列。
例如，使用merge算法将两个vector合并成一个有序的序列并输出：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v1 = {1, 3, 5};
vector<int> v2 = {2, 4, 6};
vector<int> v3(v1.size() + v2.size());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for (auto iter = v3.begin(); iter != v3.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 2 3 4 5 6
五、函数对象
函数对象是STL库中的一种概念，是一种重载了运算符()的类，可以像函数一样进行调用，可以用于算法中的比较、计算等操作。
1. 比较函数对象
比较函数对象是一种用于比较两个元素大小的函数对象，常用于sort、max_element等算法中。
例如，比较函数对象的实现：
struct cmp {
bool operator()(int a, int b) const {
return a < b;
}
};
使用比较函数对象对vector进行排序：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct cmp {
bool operator()(int a, int b) const {
return a < b;
}
};
int main() {
vector<int> v = {3, 1, 4, 2, 5};
sort(v.begin(), v.end(), cmp());
for (auto iter = v.begin(); iter != v.end(); iter++) {
cout << *iter << " ";
}
return 0;
}
输出结果为：1 2 3 4 5
2. 计算函数对象
计算函数对象是一种用于计算表达式的函数对象，常用于accumulate等算法中。
例如，计算函数对象的实现：
struct plus_functor {
int operator()(int a, int b) const {
return a + b;
}
};
