1. 容器（Containers）
- 序列容器：元素按线性顺序排列。
vector：动态数组，支持快速随机访问。
list：双向链表，支持高效插入/删除。
deque：双端队列，首尾操作高效。
array（C++11）：固定大小数组。
forward_list（C++11）：单向链表。 - 关联容器：基于键（Key）有序存储，支持快速查找。
set/multiset：有序唯一/重复集合。
map/multimap：键值对映射，键有序。 - 无序关联容器（C++11）：基于哈希表实现。
unordered_set/unordered_multiset。
unordered_map/unordered_multimap。 - 容器适配器：对底层容器的封装。
stack：后进先出（LIFO）。
queue：先进先出（FIFO）。
priority_queue：优先级队列。
2. 迭代器（Iterators）
- 输入迭代器：只读，单向（如istream_iterator）。
- 输出迭代器：只写，单向（如ostream_iterator）。
- 前向迭代器：可读写，单向（如forward_list的迭代器）。
- 双向迭代器：可双向移动（如list的迭代器）。
- 随机访问迭代器：支持随机访问（如vector的迭代器）。
3. 算法（Algorithms）
- 非修改性算法：不改变元素（如find, count）。
find(v.begin(), v.end(), 42) //查找第一个匹配的元素
count(v.begin(), v.end(), 42) //统计匹配元素的数量
all_of(v.begin(), v.end(), [](int x){ return x > 0; }) //检查所有元素是否满足条件 C++11
any_of(v.begin(), v.end(), [](int x){ return x < 0; }) //检查是否有元素满足条件 C++11
none_of(v.begin(), v.end(), [](int x){ return x == 0; }) //检查是否没有元素满足条件 C++11
search(v1.begin(), v1.end(), v2.begin(), v2.end()) //在序列中查找子序列
- 修改性算法：改变元素（如copy, replace）。
copy(src.begin(), src.end(), dest.begin()) //复制元素到目标位置
fill(v.begin(), v.end(), 0) //用指定值填充容器
replace(v.begin(), v.end(), 42, 100) //替换所有匹配的元素
auto it = remove(v.begin(), v.end(), 42) 移除匹配的元素（但不真正删除）
auto it = unique(v.begin(), v.end()) //移除相邻重复元素
reverse(v.begin(), v.end()) //反转序列
shuffle(v.begin(), v.end(), rng) //随机打乱序列 C++11
- 排序算法：如sort, stable_sort, partial_sort。
sort(v.begin(), v.end()) //快速排序（默认升序）
stable_sort(v.begin(), v.end()) //稳定排序（保持相等元素的顺序）
binary_search(v.begin(), v.end(), 42) //二分查找（要求序列有序）
auto it = lower_bound(v.begin(), v.end(), 42) //返回第一个 ≥ 指定值的迭代器
auto it = upper_bound(v.begin(), v.end(), 42) //返回第一个 > 指定值的迭代器
partial_sort(v.begin(), v.begin()+5, v.end()) //部分排序（前N个元素有序）
nth_element(v.begin(), v.begin()+3, v.end()) //使第N个元素处于正确位置
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin()) //合并两个有序序列
- 数值算法：如accumulate, inner_product（需包含numeric）。
accumulate(v.begin(), v.end(), 0) //计算累加和（或自定义操作, 0为累加基数）
inner_product(v1.begin(), v1.end(), v2.begin(), 0) 计算内积（或自定义操作）
partial_sum(v.begin(), v.end(), dest.begin()) 计算部分和
iota(v.begin(), v.end(), 1) 填充递增序列
- 堆操作：make_heap。
make_heap(v.begin(), v.end()) //将序列构建为堆
v.push_back(42); push_heap(v.begin(), v.end()) //向堆中插入元素
pop_heap(v.begin(), v.end()); v.pop_back() //从堆中移除堆顶元素
sort_heap(v.begin(), v.end()) //堆排序
- 其他常用算法：for_each。
for_each(v.begin(), v.end(), [](int x){ cout << x; }) // 对每个元素执行操作
transform(v.begin(), v.end(), dest.begin(), [](int x){ return x*2; }) //对元素进行转换
generate(v.begin(), v.end(), rand) //用生成器填充序列
auto it = min_element(v.begin(), v.end()) //返回最小元素的迭代器
auto it = max_element(v.begin(), v.end()) //返回最大元素的迭代器
4. 函数对象（Function Objects）
函数对象/仿函数：重载了operator()的类或结构体，实例可以像函数一样调用。比普通函数更灵活，可携带状态（成员变量）。
（1）内置仿函数（<functional> 头文件）
- 算术仿函数：plus<T>, minus<T>, multiplies<T>, divides<T>, modulus<T>
#include <functional>
// 使用示例
std::plus<int> add; //std::plus<> add; 自动推导类型C++17
std::cout << add(3, 5); // 输出 8
std::plus 的典型实现：
template <typename T>
struct plus {constexpr T operator()(const T& a, const T& b) const {return a + b;}
};
Lambda 表达式（更简洁）:
auto add = [](int a, int b) { return a + b; };
std::accumulate(v.begin(), v.end(), 0, add);
标准库算法直接支持运算符（C++17 起）：
std::reduce(v.begin(), v.end(), 0, std::plus{}); // 无需模板参数
- 比较仿函数：less<T>, greater<T>, equal_to<T>, not_equal_to<T>, greater_equal<T>, less_equal<T>
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm> // 包含 sortint main() {std::vector<int> v = {3, 1, 4, 1, 5, 9};// (1) 使用 less<int>() 进行升序排序（默认）std::sort(v.begin(), v.end(), std::less<int>());std::cout << "Ascending order: ";for (int x : v) std::cout << x << " "; // 1 1 3 4 5 9std::cout << std::endl;// (2) 使用 greater<int>() 进行降序排序std::sort(v.begin(), v.end(), std::greater<int>());std::cout << "Descending order: ";for (int x : v) std::cout << x << " "; // 9 5 4 3 1 1std::cout << std::endl;// (3) 使用 equal_to<int>() 查找特定值auto it = std::find_if(v.begin(), v.end(), std::bind(std::equal_to<int>(), std::placeholders::_1, 5));if (it != v.end()) {std::cout << "Found: " << *it << std::endl; // 输出 5}return 0;
}
- 逻辑仿函数：logical_and<T>, logical_or<T>, logical_not<T>
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>int main() {std::vector<bool> a = {true, false, true};std::vector<bool> b = {false, false, true};// (1) 使用 logical_and 计算两个布尔数组的逐元素 ANDstd::vector<bool> result(a.size());std::transform(a.begin(), a.end(), b.begin(), result.begin(), std::logical_and<bool>());std::cout << "Logical AND: ";for (bool x : result) std::cout << std::boolalpha << x << " "; // false false truestd::cout << std::endl;// (2) 使用 logical_not 取反std::transform(a.begin(), a.end(), result.begin(), std::logical_not<bool>());std::cout << "Logical NOT: ";for (bool x : result) std::cout << std::boolalpha << x << " "; // false true falsestd::cout << std::endl;return 0;
}
- 其他仿函数：negate<T>, identity
std::negate<int> neg; //取负数
std::cout << neg(5) << std::endl; // -5
std::vector<int> v = {1, 2, 3};
std::transform(v.begin(), v.end(), v.begin(), std::identity{}); //identity返回自身
// v 仍然是 {1, 2, 3}
5. 适配器
适配器用于修改或扩展现有组件（函数、迭代器、容器）的接口。
- 函数适配器
bind：绑定参数或调整参数顺序。
#include <functional>
using namespace std::placeholders; // 占位符 _1, _2...void print(int a, int b) { cout << a << ", " << b; }
auto f = bind(print, _2, _1); // 参数顺序交换
f(10, 20); // 输出 "20, 10"
mem_fn:将成员函数转为可调用对象。
class Person {
public:void say() const { cout << "Hello"; }
};
vector<Person> people = {Person(), Person()};
for_each(people.begin(), people.end(), mem_fn(&Person::say));
- 迭代器适配器
back_inserter：尾部插入迭代器
copy(src.begin(), src.end(), back_inserter(dest))
reverse_iterator：反向遍历
for (auto it = v.rbegin(); it != v.rend(); ++it)
istream_iterator：从输入流读取
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(v))
- 容器适配器
封装底层容器，提供特定接口：
stack<int, vector<int>> s; // 基于vector的栈
queue<int, list<int>> q; // 基于list的队列
priority_queue<int> pq; // 默认基于vector的优先队列