C++标准模板库STL(Standard Template Library)详解

C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。STL 的设计基于泛型编程，这意味着使用模板可以编写出独立于任何特定数据类型的代码。STL 分为多个组件，包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函数对象（Function

白落提fy

918人浏览 · 2026-01-06 18:25:03

白落提fy · 2026-01-06 18:25:03 发布

STL（Standard Template Library）是 C++ 标准库的核心组成部分,由Alexander Stepanov在惠普实验室开发,它通过泛型编程提供了一套通用的模板类和函数，实现了常见的数据结构和算法。

一.STL 概述

C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。
STL 的设计基于泛型编程，这意味着使用模板可以编写出独立于任何特定数据类型的代码。
STL 分为多个组件，包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函数对象（Function Objects）、适配器（Adapters）和分配器（Allocators）等。
使用 STL 的好处:
代码复用：STL 提供了大量的通用数据结构和算法，可以减少重复编写代码的工作。
性能优化：STL 中的算法和数据结构都经过了优化，以提供最佳的性能。
泛型编程：使用模板，STL 支持泛型编程，使得算法和数据结构可以适用于任何数据类型。
易于维护：STL 的设计使得代码更加模块化，易于阅读和维护。

二.STL 的六大组件

组件	功能描述
容器（Containers）	管理数据集合
算法（Algorithms）	操作容器中的元素
迭代器（Iterators）	连接容器和算法的桥梁
函数对象（Function Objects）	使算法更加灵活
适配器（Adapters）	修改或组合组件
分配器（Allocators）	内存管理

1.容器（Containers）

容器是 STL 中最基本的组件之一，用于存储和管理数据集合。所有容器都是模板类，可以存储任意类型的数据。容器提供了各种数据结构，包括向量（vector）、链表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等。这些容器具有不同的特性和用途，可以根据实际需求选择合适的容器。

1.1序列式容器（顺序容器）

元素按线性顺序排列，每个元素都有固定位置，位置取决于插入的时间和位置。允许双向遍历。

vector（动态数组）：支持快速随机访问。将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速，但是在中部或头部安插元素比较费时。

#include <vector>

// 创建和初始化
vector<int> vec1;                    // 空vector
vector<int> vec2(10, 5);             // 10个5
vector<int> vec3 = {1, 2, 3, 4, 5};  // 初始化列表
vector<int> vec4(vec3);              // 拷贝构造
vector<int> vec5(vec3.begin(), vec3.begin() + 3);  // 范围构造

// 容量操作
cout << "大小: " << vec3.size() << endl;          // 5
cout << "容量: " << vec3.capacity() << endl;      // 5
cout << "是否为空: " << vec3.empty() << endl;     // 0(false)

vec3.reserve(20);                    // 预留容量，不改变大小
vec3.resize(8, 0);                   // 调整大小，新元素初始化为0
vec3.shrink_to_fit();                // 减少容量以匹配大小(C++11)

// 元素访问
vec3[2] = 99;                        // 不检查边界
vec3.at(3) = 88;                     // 检查边界，越界抛异常
cout << "第一个元素: " << vec3.front() << endl;  // 1
cout << "最后一个元素: " << vec3.back() << endl;  // 0(新增的元素)

// 添加元素
vec3.push_back(6);                   // 尾部添加，O(1)平摊
vec3.insert(vec3.begin() + 2, 77);   // 指定位置插入，O(n)
vec3.emplace_back(7);                // 尾部就地构造，避免复制(C++11)

// 删除元素
vec3.pop_back();                     // 尾部删除，O(1)
vec3.erase(vec3.begin() + 1);        // 删除指定位置，O(n)
vec3.erase(vec3.begin() + 1, vec3.begin() + 3);  // 删除范围
vec3.clear();                        // 清空所有元素

// 交换
vector<int> other = {10, 20, 30};
vec3.swap(other);                    // 交换两个vector的内容

// 内存管理技巧
vector<int>().swap(vec3);            // 清空并释放所有内存

deque（双端队列）：支持快速插入和删除。是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速，但是在中部安插元素比较费时。

#include <deque>

deque<int> dq = {1, 2, 3, 4, 5};

// 两端操作（高效）
dq.push_front(0);                    // 头部插入，O(1)
dq.push_back(6);                     // 尾部插入，O(1)
dq.pop_front();                      // 头部删除，O(1)
dq.pop_back();                       // 尾部删除，O(1)

// 随机访问（高效）
dq[2] = 99;                          // O(1)

// 中间操作（低效）
dq.insert(dq.begin() + 2, 88);       // O(n)

// 应用场景：需要两端快速操作的序列

list（双向链表）：支持快速插入和删除，但不支持随机访问。不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针。

#include <list>

list<int> lst = {1, 2, 3, 4, 5};

// 插入和删除（任何位置都高效）
auto it = lst.begin();
advance(it, 2);                      // it指向第3个元素
lst.insert(it, 99);                  // O(1)
lst.erase(it);                       // O(1)

// 链表特有操作
lst.sort();                          // 排序，O(n log n)
lst.unique();                        // 去重相邻重复元素，O(n)
lst.reverse();                       // 反转，O(n)

// 合并和拼接
list<int> lst2 = {6, 7, 8};
lst.merge(lst2);                     // 合并两个有序链表
lst.splice(lst.begin(), lst2);       // 将lst2的所有元素移到lst开头

// 访问元素（不支持随机访问）
for (auto it = lst.begin(); it != lst.end(); ++it) {
    cout << *it << " ";
}

// 应用场景：频繁在任意位置插入删除

forward_list（单向链表，C++11引入）：

#include <forward_list>

forward_list<int> flst = {1, 2, 3, 4, 5};

// 只能从头部操作
flst.push_front(0);                  // O(1)
flst.pop_front();                    // O(1)

// 插入删除使用after版本
auto it = flst.begin();
flst.insert_after(it, 99);           // 在it后插入
flst.erase_after(it);                // 删除it后的元素

// 更节省内存，但功能受限

array（固定数组，C++11引入）：

#include <array>

array<int, 5> arr = {1, 2, 3, 4, 5};

// 类似C数组，但有STL接口
arr.fill(0);                         // 填充所有元素为0
cout << "大小: " << arr.size() << endl;        // 5
cout << "是否为空: " << arr.empty() << endl;   // false

// 支持迭代器
for (auto it = arr.begin(); it != arr.end(); ++it) {
    cout << *it << " ";
}

// 编译时确定大小，栈上分配

1.2关联式容器（有序容器）

元素按键（Key）排序，通过键快速访问元素。存储键值对，每个元素都有一个键（key）和一个值（value），并且通过键来组织元素。元素位置取决于特定的排序准则，和插入顺序无关。

set（集合）：不允许重复元素。内部的元素依据其值自动排序，set 内的相同数值的元素只能出现一次。内部由二叉树实现，便于查找。

#include <set>

set<int> s = {5, 3, 1, 4, 2};  // 自动排序: 1,2,3,4,5

// 插入元素
auto result = s.insert(6);     // 返回pair<iterator, bool>
if (result.second) {
    cout << "插入成功" << endl;
}

// 查找元素
auto it = s.find(3);           // O(log n)
if (it != s.end()) {
    cout << "找到: " << *it << endl;
}

// 边界查找
auto lb = s.lower_bound(3);    // 第一个>=3的迭代器
auto ub = s.upper_bound(3);    // 第一个>3的迭代器

// 范围查找
auto range = s.equal_range(3); // pair<lower_bound, upper_bound>
for (auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";
}

// 删除元素
s.erase(3);                    // 删除值为3的元素
s.erase(it);                   // 删除迭代器指向的元素
s.erase(s.begin(), s.find(3)); // 删除范围

// 自定义比较函数
struct Compare {
    bool operator()(int a, int b) const {
        return a > b;           // 降序排列
    }
};
set<int, Compare> s2 = {1, 2, 3, 4, 5};  // 5,4,3,2,1

multiset（多重集合）：允许多个元素具有相同的键。内部的元素依据其值自动排序，multiset 内可包含多个数值相同的元素，内部由二叉树实现，便于查找。

#include <set>

multiset<int> ms = {1, 2, 2, 3, 3, 3};

// 允许重复元素
ms.insert(2);                   // 现在有3个2

// 统计元素个数
int count = ms.count(2);        // 返回3

// 查找所有相同元素
auto range = ms.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";
}

map（映射）：每个键映射到一个值。map 的元素是成对的键值 / 实值，内部的元素依据其值自动排序，map 内的相同数值的元素只能出现一次。

#include <map>

map<string, int> m = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};

// 插入元素
auto result = m.insert({"David", 40});      // 返回pair<iterator, bool>
m["Eve"] = 45;                               // 如果不存在则插入，存在则修改

// 访问元素
int age = m.at("Alice");                     // 如果不存在则抛出异常
int age2 = m["Bob"];                         // 如果不存在则创建默认值

// 查找元素
auto it = m.find("Charlie");
if (it != m.end()) {
    cout << it->first << ": " << it->second << endl;
}

// 遍历
for (const auto& [key, value] : m) {         // C++17结构化绑定
    cout << key << ": " << value << endl;
}

for (const auto& pair : m) {                 // C++11方式
    cout << pair.first << ": " << pair.second << endl;
}

// 删除元素
m.erase("Alice");
m.erase(it);

// 自定义比较函数
map<string, int, greater<string>> m2;        // 按键降序排列

multimap（多重映射）：存储了键值对（pair），其中键是唯一的，但值可以重复，允许一个键映射到多个值。

#include <map>

multimap<string, int> mm = {
    {"Alice", 25},
    {"Alice", 26},
    {"Bob", 30}
};

// 允许重复键
mm.insert({"Alice", 27});

// 查找特定键的所有值
auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << ": " << it->second << endl;
}

// 应用场景：一对多映射关系

1.3无序关联式容器（哈希容器，C++11引入）

元素基于哈希表组织，不保证顺序。支持快速的查找、插入和删除。
-unordered_set（无序集合）：

#include <unordered_set>

unordered_set<int> us = {5, 3, 1, 4, 2};  // 顺序不确定

// 基本操作
us.insert(6);
us.erase(3);
auto it = us.find(4);                     // 平均O(1)

// 哈希表特性
cout << "桶数量: " << us.bucket_count() << endl;
cout << "负载因子: " << us.load_factor() << endl;
cout << "最大负载因子: " << us.max_load_factor() << endl;

// 重新哈希
us.rehash(100);                           // 设置桶数量
us.reserve(100);                          // 预留空间

// 遍历桶
for (size_t i = 0; i < us.bucket_count(); ++i) {
    cout << "桶" << i << "有" << us.bucket_size(i) << "个元素" << endl;
}

// 自定义哈希函数
struct Person {
    string name;
    int age;
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
    }
};

struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name && a.age == b.age;
    }
};

unordered_set<Person, PersonHash, PersonEqual> people;

unordered_map（无序映射）：

#include <unordered_map>

unordered_map<string, int> um = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};

// 操作类似map，但无序
um["David"] = 40;
um.insert({"Eve", 45});

// 性能相关
um.max_load_factor(0.7f);                 // 设置最大负载因子
um.rehash(50);                            // 重新哈希

// 遍历
for (const auto& [key, value] : um) {
    cout << key << ": " << value << endl;
}

// 应用场景：需要快速查找，不关心顺序

1.4 容器适配器

基于其他容器实现特殊接口。

stack（栈）：后进先出（LIFO）的数据结构

#include <stack>

stack<int> stk;

// 基本操作
stk.push(10);
stk.push(20);
stk.push(30);

cout << "栈顶: " << stk.top() << endl;    // 30
stk.pop();                                 // 删除30
cout << "大小: " << stk.size() << endl;   // 2
cout << "是否为空: " << stk.empty() << endl; // false

// 使用不同底层容器
stack<int, vector<int>> stk_vec;          // 使用vector作为底层
stack<int, list<int>> stk_list;           // 使用list作为底层
stack<int, deque<int>> stk_deque;         // 使用deque作为底层（默认）

// 注意：stack没有迭代器，只能访问栈顶

queue（队列）：先进先出（FIFO）的数据结构

#include <queue>

queue<int> q;

// 基本操作
q.push(10);
q.push(20);
q.push(30);

cout << "队首: " << q.front() << endl;    // 10
cout << "队尾: " << q.back() << endl;     // 30
q.pop();                                   // 删除10
cout << "大小: " << q.size() << endl;     // 2

// 使用不同底层容器
queue<int, list<int>> q_list;             // 使用list作为底层
queue<int, deque<int>> q_deque;           // 使用deque作为底层（默认）

// 注意：queue没有迭代器

priority_queue（优先队列）：元素按优先级出队，默认最大元素优先

#include <queue>

// 默认最大堆（最大元素在顶部）
priority_queue<int> pq_max;
pq_max.push(30);
pq_max.push(10);
pq_max.push(20);
cout << "顶部: " << pq_max.top() << endl;  // 30

// 最小堆
priority_queue<int, vector<int>, greater<int>> pq_min;
pq_min.push(30);
pq_min.push(10);
pq_min.push(20);
cout << "顶部: " << pq_min.top() << endl;  // 10

// 自定义比较函数
struct Compare {
    bool operator()(int a, int b) {
        // 按绝对值比较，绝对值大的优先级高
        return abs(a) < abs(b);
    }
};
priority_queue<int, vector<int>, Compare> pq_custom;

// 存储复杂类型
struct Task {
    int priority;
    string description;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 最大堆
    }
};

priority_queue<Task> task_queue;
task_queue.push({3, "低优先级任务"});
task_queue.push({1, "高优先级任务"});
task_queue.push({2, "中优先级任务"});

while (!task_queue.empty()) {
    Task task = task_queue.top();
    cout << task.priority << ": " << task.description << endl;
    task_queue.pop();
}

2.算法（Algorithms）

STL算法是STL中非常重要的一部分，它们提供了大量的标准算法，用于对容器中的元素进行操作。这些算法覆盖了常见的操作，如查找、排序、复制、修改等。STL算法通过迭代器与容器进行交互，因此它们可以用于不同类型的容器，只需要指定要操作的范围即可。
STL算法的特点
通过迭代器操作，与容器解耦
大多数算法在<algorithm>头文件中
数值算法在 <numeric>头文件中
STL算法大致可以分为以下几类：

非修改序列算法：不会改变容器中的内容，例如查找、计数等。
修改序列算法：会改变容器中的内容，例如复制、替换、填充等。
排序和相关算法：包括排序、合并、二分查找等。
数值算法：例如累加、内积等。

2.1. 非修改序列算法

查找算法

#include <algorithm>
#include <vector>
#include <iostream>

void find_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // find: 查找指定值
    auto it1 = std::find(v.begin(), v.end(), 5);
    if (it1 != v.end()) {
        std::cout << "找到5: " << *it1 << std::endl;  // 5
    }
    
    // find_if: 按条件查找
    auto it2 = std::find_if(v.begin(), v.end(), [](int x) {
        return x > 7;
    });
    if (it2 != v.end()) {
        std::cout << "找到大于7的元素: " << *it2 << std::endl;  // 8
    }
    
    // find_if_not: 查找不满足条件的元素
    auto it3 = std::find_if_not(v.begin(), v.end(), [](int x) {
        return x < 5;
    });
    if (it3 != v.end()) {
        std::cout << "找到不小于5的元素: " << *it3 << std::endl;  // 5
    }
    
    // find_end: 查找子序列最后出现的位置
    std::vector<int> sub = {3, 4, 5};
    auto it4 = std::find_end(v.begin(), v.end(), sub.begin(), sub.end());
    if (it4 != v.end()) {
        std::cout << "子序列最后出现在位置: " << std::distance(v.begin(), it4) << std::endl;
    }
    
    // search: 查找子序列首次出现的位置
    auto it5 = std::search(v.begin(), v.end(), sub.begin(), sub.end());
    if (it5 != v.end()) {
        std::cout << "子序列首次出现在位置: " << std::distance(v.begin(), it5) << std::endl;
    }
    
    // search_n: 查找连续n个相同元素
    std::vector<int> v2 = {1, 2, 2, 2, 3, 4, 2, 2};
    auto it6 = std::search_n(v2.begin(), v2.end(), 3, 2);
    if (it6 != v2.end()) {
        std::cout << "找到3个连续的2" << std::endl;
    }
    
    // adjacent_find: 查找相邻重复元素
    std::vector<int> v3 = {1, 2, 3, 3, 4, 5, 5, 6};
    auto it7 = std::adjacent_find(v3.begin(), v3.end());
    if (it7 != v3.end()) {
        std::cout << "找到相邻重复元素: " << *it7 << std::endl;  // 3
    }
    
    // 自定义比较函数的adjacent_find
    auto it8 = std::adjacent_find(v3.begin(), v3.end(), 
        [](int a, int b) { return abs(a - b) == 1; });
    if (it8 != v3.end()) {
        std::cout << "找到相邻元素差为1: " << *it8 << "和" << *(it8 + 1) << std::endl;
    }
}

计数算法

void count_examples() {
    std::vector<int> v = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
    
    // count: 统计等于某个值的元素个数
    int cnt1 = std::count(v.begin(), v.end(), 3);
    std::cout << "3的个数: " << cnt1 << std::endl;  // 3
    
    // count_if: 统计满足条件的元素个数
    int cnt2 = std::count_if(v.begin(), v.end(), [](int x) {
        return x > 2;
    });
    std::cout << "大于2的个数: " << cnt2 << std::endl;  // 7
    
    // 统计字符串中字符个数
    std::string str = "Hello, World!";
    int cnt3 = std::count(str.begin(), str.end(), 'l');
    std::cout << "l的个数: " << cnt3 << std::endl;  // 3
    
    // 统计元音字母个数
    std::string vowels = "aeiouAEIOU";
    int cnt4 = std::count_if(str.begin(), str.end(), [&vowels](char c) {
        return vowels.find(c) != std::string::npos;
    });
    std::cout << "元音字母个数: " << cnt4 << std::endl;  // 3
}

比较算法

void compare_examples() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    std::vector<int> v3 = {1, 2, 3, 4, 6};
    
    // equal: 比较两个序列是否相等
    bool eq1 = std::equal(v1.begin(), v1.end(), v2.begin());
    std::cout << "v1等于v2: " << eq1 << std::endl;  // true
    
    bool eq2 = std::equal(v1.begin(), v1.end(), v3.begin());
    std::cout << "v1等于v3: " << eq2 << std::endl;  // false
    
    // 自定义比较函数
    bool eq3 = std::equal(v1.begin(), v1.end(), v3.begin(), [](int a, int b) {
        return abs(a - b) <= 1;
    });
    std::cout << "v1与v3元素差不大于1: " << eq3 << std::endl;  // true
    
    // mismatch: 查找第一个不匹配的位置
    auto p = std::mismatch(v1.begin(), v1.end(), v3.begin());
    if (p.first != v1.end()) {
        std::cout << "第一个不匹配: " << *(p.first) << " vs " << *(p.second) << std::endl;  // 5 vs 6
    }
    
    // lexicographical_compare: 字典序比较
    std::string s1 = "apple";
    std::string s2 = "banana";
    bool lt = std::lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end());
    std::cout << s1 << " < " << s2 << ": " << lt << std::endl;  // true
    
    // is_permutation: 判断是否为排列（C++11）
    std::vector<int> v4 = {1, 2, 3, 4, 5};
    std::vector<int> v5 = {5, 4, 3, 2, 1};
    bool perm = std::is_permutation(v4.begin(), v4.end(), v5.begin());
    std::cout << "v5是v4的排列: " << perm << std::endl;  // true
}

遍历算法

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>

void foreach_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // for_each: 对每个元素执行操作
    std::cout << "原始值: ";
    std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;
    
    // 修改元素
    std::cout << "乘以2: ";
    std::for_each(v.begin(), v.end(), [](int& x) {
        x *= 2;
    });
    std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;
    
    // 使用函数对象
    struct Printer {
        void operator()(int x) const {
            std::cout << x << " ";
        }
    };
    std::cout << "使用函数对象: ";
    std::for_each(v.begin(), v.end(), Printer());
    std::cout << std::endl;
    
    // for_each_n: 对前n个元素执行操作（C++17）
    std::vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "前5个元素加10: ";
    std::for_each_n(v2.begin(), 5, [](int& x) { x += 10; });
    for (int x : v2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 统计操作次数
    struct Counter {
        int count = 0;
        void operator()(int x) {
            if (x > 12) ++count;
        }
    };
    
    Counter c = std::for_each(v2.begin(), v2.end(), Counter());
    std::cout << "大于12的元素个数: " << c.count << std::endl;
}

搜索算法

void search_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // lower_bound: 第一个不小于给定值的迭代器
    auto lb = std::lower_bound(v.begin(), v.end(), 5);
    std::cout << "第一个不小于5的元素: " << *lb << std::endl;  // 5
    
    // upper_bound: 第一个大于给定值的迭代器
    auto ub = std::upper_bound(v.begin(), v.end(), 5);
    std::cout << "第一个大于5的元素: " << *ub << std::endl;  // 6
    
    // equal_range: 返回等于给定值的范围
    auto range = std::equal_range(v.begin(), v.end(), 5);
    std::cout << "等于5的范围: [" << std::distance(v.begin(), range.first) 
              << ", " << std::distance(v.begin(), range.second) << ")" << std::endl;
    
    // binary_search: 判断是否存在（要求序列有序）
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << "5是否存在: " << found << std::endl;  // true
}

2.2. 修改序列算法

复制算法

void copy_examples() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    
    // copy: 复制元素
    std::vector<int> dst1(src.size());
    std::copy(src.begin(), src.end(), dst1.begin());
    std::cout << "copy结果: ";
    for (int x : dst1) std::cout << x << " ";
    std::cout << std::endl;
    
    // copy_if: 按条件复制
    std::vector<int> dst2;
    std::copy_if(src.begin(), src.end(), std::back_inserter(dst2),
                 [](int x) { return x % 2 == 0; });
    std::cout << "copy_if(偶数): ";
    for (int x : dst2) std::cout << x << " ";
    std::cout << std::endl;
    
    // copy_n: 复制前n个元素
    std::vector<int> dst3(3);
    std::copy_n(src.begin(), 3, dst3.begin());
    std::cout << "copy_n(前3个): ";
    for (int x : dst3) std::cout << x << " ";
    std::cout << std::endl;
    
    // copy_backward: 从后往前复制
    std::vector<int> dst4(5);
    std::copy_backward(src.begin(), src.end(), dst4.end());
    std::cout << "copy_backward结果: ";
    for (int x : dst4) std::cout << x << " ";
    std::cout << std::endl;
    
    // 复制到输出流
    std::cout << "复制到输出流: ";
    std::copy(src.begin(), src.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    
    // 从输入流复制
    std::istringstream iss("1 2 3 4 5");
    std::vector<int> dst5;
    std::copy(std::istream_iterator<int>(iss),
              std::istream_iterator<int>(),
              std::back_inserter(dst5));
    std::cout << "从输入流复制: ";
    for (int x : dst5) std::cout << x << " ";
    std::cout << std::endl;
}

移动算法

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

void move_examples() {
    // move: 移动元素（C++11）
    std::vector<std::string> src = {"apple", "banana", "cherry"};
    std::vector<std::string> dst(3);
    
    std::cout << "move前src: ";
    for (const auto& s : src) std::cout << "\"" << s << "\" ";
    std::cout << std::endl;
    
    std::move(src.begin(), src.end(), dst.begin());
    
    std::cout << "move后src: ";
    for (const auto& s : src) std::cout << "\"" << s << "\" ";  // 有效但未指定状态
    std::cout << std::endl;
    
    std::cout << "move后dst: ";
    for (const auto& s : dst) std::cout << "\"" << s << "\" ";
    std::cout << std::endl;
    
    // move_backward: 从后往前移动
    std::vector<std::string> src2 = {"dog", "cat", "bird"};
    std::vector<std::string> dst2(5);
    
    std::move_backward(src2.begin(), src2.end(), dst2.end());
    
    std::cout << "move_backward后dst2: ";
    for (const auto& s : dst2) {
        if (s.empty()) std::cout << "[空] ";
        else std::cout << "\"" << s << "\" ";
    }
    std::cout << std::endl;
    
    // 实际应用：交换两个vector
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    
    std::cout << "交换前 v1: ";
    for (int x : v1) std::cout << x << " ";
    std::cout << "\n交换前 v2: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    
    // 使用move交换
    std::vector<int> temp = std::move(v1);
    v1 = std::move(v2);
    v2 = std::move(temp);
    
    std::cout << "交换后 v1: ";
    for (int x : v1) std::cout << x << " ";
    std::cout << "\n交换后 v2: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
}

变换算法

void transform_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // transform: 对每个元素应用函数
    std::vector<int> result(v.size());
    std::transform(v.begin(), v.end(), result.begin(),
                   [](int x) { return x * x; });
    
    std::cout << "平方变换: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    
    // 两个序列的transform
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    std::vector<int> result2(v1.size());
    
    std::transform(v1.begin(), v1.end(), v2.begin(), result2.begin(),
                   [](int a, int b) { return a + b; });
    
    std::cout << "两个序列相加: ";
    for (int x : result2) std::cout << x << " ";
    std::cout << std::endl;
    
    // 原地变换
    std::cout << "原地乘以2: ";
    std::transform(v.begin(), v.end(), v.begin(),
                   [](int x) { return x * 2; });
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // 字符串变换
    std::string str = "Hello World";
    std::string upper_str;
    std::transform(str.begin(), str.end(), std::back_inserter(upper_str),
                   [](char c) { return std::toupper(c); });
    
    std::cout << "转大写: " << upper_str << std::endl;
    
    // 复杂变换：生成斐波那契数列
    std::vector<int> fib(10);
    fib[0] = 0;
    fib[1] = 1;
    
    std::transform(fib.begin(), fib.end() - 2,
                   fib.begin() + 1,
                   fib.begin() + 2,
                   std::plus<int>());
    
    std::cout << "斐波那契数列: ";
    for (int x : fib) std::cout << x << " ";
    std::cout << std::endl;
}

替换算法

void replace_examples() {
    std::vector<int> v = {1, 2, 3, 2, 5, 2, 7};
    
    // replace: 替换指定值
    std::replace(v.begin(), v.end(), 2, 99);
    std::cout << "替换2为99: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // replace_if: 按条件替换
    std::vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::replace_if(v2.begin(), v2.end(),
                    [](int x) { return x < 5; },
                    0);
    std::cout << "替换小于5的为0: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    
    // replace_copy: 替换并复制到新容器
    std::vector<int> src = {1, 2, 3, 2, 5};
    std::vector<int> dst(src.size());
    std::replace_copy(src.begin(), src.end(), dst.begin(), 2, 99);
    
    std::cout << "原始: ";
    for (int x : src) std::cout << x << " ";
    std::cout << "\n替换复制后: ";
    for (int x : dst) std::cout << x << " ";
    std::cout << std::endl;
    
    // replace_copy_if: 按条件替换并复制
    std::vector<int> dst2(src.size());
    std::replace_copy_if(src.begin(), src.end(), dst2.begin(),
                         [](int x) { return x % 2 == 0; },
                         -1);
    
    std::cout << "替换偶数为-1并复制: ";
    for (int x : dst2) std::cout << x << " ";
    std::cout << std::endl;
}

填充算法

void fill_examples() {
    // fill: 填充值
    std::vector<int> v(5);
    std::fill(v.begin(), v.end(), 42);
    std::cout << "填充42: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // fill_n: 填充前n个元素
    std::vector<int> v2(10);
    std::fill_n(v2.begin(), 3, 99);
    std::cout << "填充前3个为99: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    
    // generate: 用函数生成值
    std::vector<int> v3(5);
    int n = 1;
    std::generate(v3.begin(), v3.end(), [&n]() { return n++; });
    std::cout << "生成递增序列: ";
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;
    
    // generate_n: 生成前n个值
    std::vector<int> v4(5);
    std::generate_n(v4.begin(), 3, []() { return rand() % 100; });
    std::cout << "生成前3个随机数: ";
    for (int x : v4) std::cout << x << " ";
    std::cout << std::endl;
    
    // iota: 填充递增序列（C++11）
    std::vector<int> v5(10);
    std::iota(v5.begin(), v5.end(), 100);
    std::cout << "iota从100开始: ";
    for (int x : v5) std::cout << x << " ";
    std::cout << std::endl;
}

删除算法

void remove_examples() {
    // remove: 逻辑删除指定值
    std::vector<int> v = {1, 2, 3, 2, 5, 2, 7};
    auto new_end = std::remove(v.begin(), v.end(), 2);
    
    std::cout << "逻辑删除2后: ";
    for (auto it = v.begin(); it != new_end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    std::cout << "整个vector: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // 物理删除
    v.erase(new_end, v.end());
    std::cout << "物理删除后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // remove_if: 按条件删除
    v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    new_end = std::remove_if(v.begin(), v.end(),
                             [](int x) { return x % 2 == 0; });
    v.erase(new_end, v.end());
    std::cout << "删除偶数后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // remove_copy: 删除并复制到新容器
    std::vector<int> src = {1, 2, 3, 2, 5};
    std::vector<int> dst;
    std::remove_copy(src.begin(), src.end(), std::back_inserter(dst), 2);
    std::cout << "删除2并复制: ";
    for (int x : dst) std::cout << x << " ";
    std::cout << std::endl;
    
    // unique: 删除相邻重复元素
    std::vector<int> v2 = {1, 1, 2, 2, 3, 3, 3, 4, 5, 5};
    new_end = std::unique(v2.begin(), v2.end());
    v2.erase(new_end, v2.end());
    std::cout << "去重后: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    
    // 自定义相等判断的unique
    std::vector<int> v3 = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    std::sort(v3.begin(), v3.end());
    new_end = std::unique(v3.begin(), v3.end(),
                          [](int a, int b) { return abs(a - b) <= 1; });
    v3.erase(new_end, v3.end());
    std::cout << "自定义去重(差<=1): ";
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;
}

交换算法

void swap_examples() {
    // swap: 交换两个元素
    int a = 10, b = 20;
    std::swap(a, b);
    std::cout << "a = " << a << ", b = " << b << std::endl;  // a=20, b=10
    
    // swap_ranges: 交换两个范围
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {10, 20, 30, 40, 50};
    
    std::swap_ranges(v1.begin(), v1.begin() + 3, v2.begin());
    
    std::cout << "交换范围后v1: ";
    for (int x : v1) std::cout << x << " ";
    std::cout << "\n交换范围后v2: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    
    // iter_swap: 交换两个迭代器指向的元素
    std::vector<int> v3 = {1, 2, 3, 4, 5};
    std::iter_swap(v3.begin(), v3.end() - 1);
    std::cout << "交换首尾后v3: ";
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;
    
    // 交换整个容器
    std::vector<int> v4 = {1, 2, 3};
    std::vector<int> v5 = {4, 5, 6};
    std::swap(v4, v5);
    
    std::cout << "交换容器后v4: ";
    for (int x : v4) std::cout << x << " ";
    std::cout << "\n交换容器后v5: ";
    for (int x : v5) std::cout << x << " ";
    std::cout << std::endl;
}

2.3. 排序和相关算法

排序算法

void sort_examples() {
    std::vector<int> v = {5, 3, 1, 4, 2, 6, 8, 7, 9};
    
    // sort: 快速排序
    std::sort(v.begin(), v.end());
    std::cout << "升序排序: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // 降序排序
    std::sort(v.begin(), v.end(), std::greater<int>());
    std::cout << "降序排序: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // 自定义排序
    std::vector<std::string> words = {"apple", "banana", "cherry", "date"};
    std::sort(words.begin(), words.end(),
              [](const std::string& a, const std::string& b) {
                  return a.length() < b.length();
              });
    std::cout << "按长度排序: ";
    for (const auto& w : words) std::cout << w << " ";
    std::cout << std::endl;
    
    // stable_sort: 稳定排序
    std::vector<std::pair<int, int>> pairs = {
        {1, 5}, {2, 3}, {1, 3}, {2, 1}, {1, 1}
    };
    std::stable_sort(pairs.begin(), pairs.end(),
                     [](const auto& a, const auto& b) {
                         return a.first < b.first;
                     });
    std::cout << "稳定排序(按first): ";
    for (const auto& p : pairs) {
        std::cout << "(" << p.first << "," << p.second << ") ";
    }
    std::cout << std::endl;
    
    // partial_sort: 部分排序
    v = {5, 3, 1, 4, 2, 6, 8, 7, 9};
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    std::cout << "部分排序(前3个最小): ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // nth_element: 使第n个元素处于正确位置
    v = {5, 3, 1, 4, 2, 6, 8, 7, 9};
    std::nth_element(v.begin(), v.begin() + 4, v.end());
    std::cout << "第5小元素是: " << v[4] << std::endl;
    std::cout << "nth_element后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // is_sorted: 判断是否有序
    v = {1, 2, 3, 4, 5};
    bool sorted = std::is_sorted(v.begin(), v.end());
    std::cout << "是否升序: " << sorted << std::endl;  // true
    
    // is_sorted_until: 查找无序位置
    v = {1, 2, 3, 5, 4, 6, 7};
    auto it = std::is_sorted_until(v.begin(), v.end());
    if (it != v.end()) {
        std::cout << "从位置 " << std::distance(v.begin(), it)
                  << " 开始无序" << std::endl;
    }
}

二分查找算法

void binary_search_examples() {
    // 必须是有序序列
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // binary_search: 判断是否存在
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << "5是否存在: " << found << std::endl;  // true
    
    found = std::binary_search(v.begin(), v.end(), 10);
    std::cout << "10是否存在: " << found << std::endl;  // false
    
    // lower_bound: 第一个不小于给定值的迭代器
    auto lb = std::lower_bound(v.begin(), v.end(), 5);
    std::cout << "第一个不小于5的元素: " << *lb << std::endl;  // 5
    
    lb = std::lower_bound(v.begin(), v.end(), 5.5);
    std::cout << "第一个不小于5.5的元素: " << *lb << std::endl;  // 6
    
    // upper_bound: 第一个大于给定值的迭代器
    auto ub = std::upper_bound(v.begin(), v.end(), 5);
    std::cout << "第一个大于5的元素: " << *ub << std::endl;  // 6
    
    // equal_range: 返回等于给定值的范围
    auto range = std::equal_range(v.begin(), v.end(), 5);
    std::cout << "等于5的范围大小: " 
              << std::distance(range.first, range.second) << std::endl;  // 1
    
    // 在自定义排序的序列中查找
    std::vector<int> v2 = {9, 8, 7, 6, 5, 4, 3, 2, 1};  // 降序
    found = std::binary_search(v2.begin(), v2.end(), 5, std::greater<int>());
    std::cout << "在降序序列中5是否存在: " << found << std::endl;  // true
    
    // 查找第一个大于等于3的元素（在降序序列中）
    lb = std::lower_bound(v2.begin(), v2.end(), 3, std::greater<int>());
    std::cout << "降序序列中第一个>=3的元素: " << *lb << std::endl;  // 3
    
    // 应用：查找区间
    struct Interval {
        int start, end;
        bool operator<(const Interval& other) const {
            return start < other.start;
        }
    };
    
    std::vector<Interval> intervals = {
        {1, 3}, {2, 4}, {5, 7}, {6, 8}
    };
    
    // 查找起点大于等于3的区间
    Interval target = {3, 0};
    auto it = std::lower_bound(intervals.begin(), intervals.end(), target);
    if (it != intervals.end()) {
        std::cout << "第一个起点>=3的区间: [" 
                  << it->start << ", " << it->end << "]" << std::endl;
    }
}

合并算法

void merge_examples() {
    // merge: 合并两个有序序列
    std::vector<int> v1 = {1, 3, 5, 7, 9};
    std::vector<int> v2 = {2, 4, 6, 8, 10};
    std::vector<int> result(v1.size() + v2.size());
    
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    
    std::cout << "合并结果: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    
    // 自定义比较函数的merge
    std::vector<int> v3 = {9, 7, 5, 3, 1};  // 降序
    std::vector<int> v4 = {10, 8, 6, 4, 2}; // 降序
    std::vector<int> result2(v3.size() + v4.size());
    
    std::merge(v3.begin(), v3.end(), v4.begin(), v4.end(),
               result2.begin(), std::greater<int>());
    
    std::cout << "降序合并: ";
    for (int x : result2) std::cout << x << " ";
    std::cout << std::endl;
    
    // inplace_merge: 原地合并
    std::vector<int> v5 = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    std::inplace_merge(v5.begin(), v5.begin() + 5, v5.end());
    
    std::cout << "原地合并: ";
    for (int x : v5) std::cout << x << " ";
    std::cout << std::endl;
    
    // 应用：多路归并
    std::vector<std::vector<int>> vectors = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    
    std::vector<int> merged;
    for (const auto& vec : vectors) {
        std::vector<int> temp(merged.size() + vec.size());
        std::merge(merged.begin(), merged.end(), vec.begin(), vec.end(),
                   temp.begin());
        merged.swap(temp);
    }
    
    std::cout << "多路归并: ";
    for (int x : merged) std::cout << x << " ";
    std::cout << std::endl;
}

集合算法

void set_algorithm_examples() {
    // 要求序列有序
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    // set_union: 并集
    std::set_union(v1.begin(), v1.end(),
                   v2.begin(), v2.end(),
                   std::back_inserter(result));
    std::cout << "并集: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    
    // set_intersection: 交集
    result.clear();
    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(result));
    std::cout << "交集: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    
    // set_difference: 差集 (v1 - v2)
    result.clear();
    std::set_difference(v1.begin(), v1.end(),
                        v2.begin(), v2.end(),
                        std::back_inserter(result));
    std::cout << "差集(v1-v2): ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    
    // set_symmetric_difference: 对称差集
    result.clear();
    std::set_symmetric_difference(v1.begin(), v1.end(),
                                  v2.begin(), v2.end(),
                                  std::back_inserter(result));
    std::cout << "对称差集: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    
    // includes: 判断是否包含
    bool includes = std::includes(v1.begin(), v1.end(),
                                  v2.begin(), v2.begin() + 3);  // {3, 4, 5}
    std::cout << "v1是否包含{3,4,5}: " << includes << std::endl;  // true
    
    // 应用：合并多个集合
    std::vector<std::vector<int>> sets = {
        {1, 2, 3},
        {2, 3, 4},
        {3, 4, 5}
    };
    
    std::vector<int> all_elements;
    for (const auto& s : sets) {
        std::vector<int> temp;
        std::set_union(all_elements.begin(), all_elements.end(),
                       s.begin(), s.end(),
                       std::back_inserter(temp));
        all_elements.swap(temp);
    }
    
    std::cout << "所有集合的元素: ";
    for (int x : all_elements) std::cout << x << " ";
    std::cout << std::endl;
}

堆算法

void heap_examples() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // make_heap: 建立最大堆
    std::make_heap(v.begin(), v.end());
    std::cout << "最大堆: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    std::cout << "堆顶: " << v.front() << std::endl;  // 9
    
    // push_heap: 添加元素到堆
    v.push_back(8);
    std::push_heap(v.begin(), v.end());
    std::cout << "添加8后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // pop_heap: 从堆中移除最大元素
    std::pop_heap(v.begin(), v.end());
    int max_val = v.back();
    v.pop_back();
    std::cout << "移除最大元素: " << max_val << std::endl;
    std::cout << "剩余堆: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // sort_heap: 堆排序
    std::sort_heap(v.begin(), v.end());
    std::cout << "堆排序后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // is_heap: 判断是否为堆
    std::vector<int> v2 = {9, 5, 4, 1, 3, 2};
    bool is_heap = std::is_heap(v2.begin(), v2.end());
    std::cout << "是否为堆: " << is_heap << std::endl;  // false
    
    std::make_heap(v2.begin(), v2.end());
    is_heap = std::is_heap(v2.begin(), v2.end());
    std::cout << "建立堆后是否为堆: " << is_heap << std::endl;  // true
    
    // is_heap_until: 查找破坏堆性质的位置
    v2.push_back(10);
    auto it = std::is_heap_until(v2.begin(), v2.end());
    std::cout << "破坏堆性质的位置: " << std::distance(v2.begin(), it)
              << " (元素: " << *it << ")" << std::endl;
    
    // 最小堆
    std::vector<int> v3 = {5, 3, 8, 1, 9};
    std::make_heap(v3.begin(), v3.end(), std::greater<int>());
    std::cout << "最小堆: ";
    for (int x : v3) std::cout << x << " ";
    std::cout << "\n最小堆堆顶: " << v3.front() << std::endl;  // 1
    
    // 应用：优先级队列
    std::vector<int> tasks = {3, 1, 4, 1, 5, 9, 2, 6};
    std::make_heap(tasks.begin(), tasks.end(), std::greater<int>());  // 最小堆
    
    std::cout << "处理任务顺序: ";
    while (!tasks.empty()) {
        std::pop_heap(tasks.begin(), tasks.end(), std::greater<int>());
        int task = tasks.back();
        tasks.pop_back();
        std::cout << task << " ";
    }
    std::cout << std::endl;
}

最值算法

void minmax_examples() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // min: 返回最小值
    int m1 = std::min(10, 20);
    std::cout << "min(10, 20) = " << m1 << std::endl;  // 10
    
    // max: 返回最大值
    int m2 = std::max(10, 20);
    std::cout << "max(10, 20) = " << m2 << std::endl;  // 20
    
    // minmax: 返回最小值和最大值（C++11）
    auto mm1 = std::minmax(10, 20);
    std::cout << "minmax(10, 20) = (" << mm1.first << ", " << mm1.second << ")" << std::endl;
    
    // min_element: 返回最小元素的迭代器
    auto min_it = std::min_element(v.begin(), v.end());
    std::cout << "最小元素: " << *min_it << " 位置: " 
              << std::distance(v.begin(), min_it) << std::endl;
    
    // max_element: 返回最大元素的迭代器
    auto max_it = std::max_element(v.begin(), v.end());
    std::cout << "最大元素: " << *max_it << " 位置: "
              << std::distance(v.begin(), max_it) << std::endl;
    
    // minmax_element: 返回最小和最大元素的迭代器（C++11）
    auto mm_it = std::minmax_element(v.begin(), v.end());
    std::cout << "最小元素: " << *(mm_it.first) 
              << " 最大元素: " << *(mm_it.second) << std::endl;
    
    // 自定义比较函数
    std::vector<std::string> words = {"apple", "banana", "cherry", "date"};
    auto longest = std::max_element(words.begin(), words.end(),
                                    [](const std::string& a, const std::string& b) {
                                        return a.length() < b.length();
                                    });
    std::cout << "最长的单词: " << *longest << std::endl;
    
    // clamp: 限制值在范围内（C++17）
    int value = 150;
    int clamped = std::clamp(value, 0, 100);
    std::cout << "clamp(150, 0, 100) = " << clamped << std::endl;  // 100
    
    // 应用：查找成绩最优和最差的学生
    struct Student {
        std::string name;
        int score;
    };
    
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 95},
        {"Eve", 88}
    };
    
    auto best = std::max_element(students.begin(), students.end(),
                                 [](const Student& a, const Student& b) {
                                     return a.score < b.score;
                                 });
    auto worst = std::min_element(students.begin(), students.end(),
                                  [](const Student& a, const Student& b) {
                                      return a.score < b.score;
                                  });
    
    std::cout << "最高分: " << best->name << " (" << best->score << "分)" << std::endl;
    std::cout << "最低分: " << worst->name << " (" << worst->score << "分)" << std::endl;
}

排列算法

void permutation_examples() {
    std::vector<int> v = {1, 2, 3};
    
    std::cout << "所有排列:\n";
    do {
        for (int x : v) std::cout << x << " ";
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));
    
    // 重新初始化为降序
    v = {3, 2, 1};
    std::cout << "\n降序排列的上一个排列:\n";
    std::prev_permutation(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";  // 3 1 2
    std::cout << std::endl;
    
    // 判断是否为排列
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {5, 4, 3, 2, 1};
    bool is_perm = std::is_permutation(v1.begin(), v1.end(), v2.begin());
    std::cout << "v2是否是v1的排列: " << is_perm << std::endl;  // true
    
    // 生成所有排列的应用：解决旅行商问题（暴力搜索）
    std::vector<std::string> cities = {"A", "B", "C", "D"};
    std::sort(cities.begin(), cities.end());  // 先排序
    
    std::cout << "\n所有旅行路线:\n";
    int count = 0;
    do {
        std::cout << ++count << ": ";
        for (const auto& city : cities) {
            std::cout << city << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(cities.begin(), cities.end()));
}

2.4. 数值算法

#include <numeric>  // 数值算法头文件
#include <iostream>
#include <vector>
#include <cmath>

void numeric_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // accumulate: 累加
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "累加: " << sum << std::endl;  // 15
    
    // 累乘
    int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
    std::cout << "累乘: " << product << std::endl;  // 120
    
    // 字符串连接
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    std::string sentence = std::accumulate(words.begin(), words.end(), std::string());
    std::cout << "字符串连接: " << sentence << std::endl;  // Hello World!
    
    // inner_product: 内积（点积）
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    int dot = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
    std::cout << "内积: " << dot << std::endl;  // 32 (1*4 + 2*5 + 3*6)
    
    // 自定义操作的内积
    int sum_of_squares = std::inner_product(v1.begin(), v1.end(), v1.begin(), 0);
    std::cout << "平方和: " << sum_of_squares << std::endl;  // 14 (1*1 + 2*2 + 3*3)
    
    // partial_sum: 部分和
    std::vector<int> prefix_sum(v.size());
    std::partial_sum(v.begin(), v.end(), prefix_sum.begin());
    std::cout << "部分和: ";
    for (int x : prefix_sum) std::cout << x << " ";  // 1 3 6 10 15
    std::cout << std::endl;
    
    // 自定义操作的partial_sum
    std::vector<int> prefix_product(v.size());
    std::partial_sum(v.begin(), v.end(), prefix_product.begin(), std::multiplies<int>());
    std::cout << "部分积: ";
    for (int x : prefix_product) std::cout << x << " ";  // 1 2 6 24 120
    std::cout << std::endl;
    
    // adjacent_difference: 相邻差
    std::vector<int> diff(v.size());
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    std::cout << "相邻差: ";
    for (int x : diff) std::cout << x << " ";  // 1 1 1 1 1
    std::cout << std::endl;
    
    // 自定义操作的adjacent_difference
    std::vector<int> ratio(v.size());
    std::adjacent_difference(v.begin(), v.end(), ratio.begin(),
                             [](int a, int b) { return a - b; });
    std::cout << "相邻差(自定义): ";
    for (int x : ratio) std::cout << x << " ";
    std::cout << std::endl;
    
    // iota: 填充递增序列
    std::vector<int> seq(10);
    std::iota(seq.begin(), seq.end(), 100);
    std::cout << "iota从100开始: ";
    for (int x : seq) std::cout << x << " ";  // 100 101 102 ... 109
    std::cout << std::endl;
    
    // gcd和lcm（C++17）
    int a = 12, b = 18;
    int g = std::gcd(a, b);
    int l = std::lcm(a, b);
    std::cout << "gcd(12, 18) = " << g << std::endl;  // 6
    std::cout << "lcm(12, 18) = " << l << std::endl;  // 36
    
    // midpoint（C++20）
    int m = std::midpoint(10, 20);
    std::cout << "midpoint(10, 20) = " << m << std::endl;  // 15
    
    // 应用：计算加权平均值
    std::vector<double> values = {85, 90, 78, 92, 88};
    std::vector<double> weights = {0.1, 0.2, 0.3, 0.2, 0.2};
    
    double weighted_sum = std::inner_product(values.begin(), values.end(),
                                             weights.begin(), 0.0);
    double total_weight = std::accumulate(weights.begin(), weights.end(), 0.0);
    double weighted_avg = weighted_sum / total_weight;
    
    std::cout << "加权平均值: " << weighted_avg << std::endl;
}

3.迭代器（Iterators）

迭代器用于遍历容器中的元素，它是一种类似指针的对象，允许以统一的方式访问容器中的元素，而不用了解容器的内部实现细节。
迭代器的作用
1.连接容器和算法
2.提供统一的访问接口
3.支持泛型编程

3.1. 迭代器类别

五种迭代器类别

// 迭代器分类（按功能从弱到强）

输入迭代器 (Input Iterator) - 只读，只能向前移动

输出迭代器 (Output Iterator) - 只写，只能向前移动

前向迭代器 (Forward Iterator) - 可读写，只能向前移动

双向迭代器 (Bidirectional Iterator) - 可读写，可向前向后移动

随机访问迭代器 (Random Access Iterator) - 可读写，支持随机访问

各类迭代器的能力矩阵

操作	输入	输出	前向	双向	随机访问
读 (*it)	✓		✓	✓	✓
写 (*it = value)		✓	✓	✓	✓
递增 (++)	✓	✓	✓	✓	✓
递减 (–)				✓	✓
比较 (==, !=)	✓		✓	✓	✓
一次遍历	✓	✓
多次遍历			✓	✓	✓
加/减整数 (it + n)					✓
下标访问 (it[n])					✓
比较大小 (<, >)					✓
距离 (it1 - it2)					✓

3.2. 迭代器使用

获取迭代器
每个容器都提供了获取迭代器的成员函数：
begin()、end()：返回指向第一个元素和尾后位置的迭代器
cbegin()、cend()：返回const迭代器（C++11引入）
rbegin()、rend()：返回反向迭代器
crbegin()、crend()：返回const反向迭代器（C++11引入）
迭代器操作示例

#include <iostream>
#include <vector>
#include <list>

void basic_operations() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 获取迭代器
    auto begin_it = v.begin();    // 指向第一个元素
    auto end_it = v.end();        // 指向最后一个元素的下一个位置
    
    // 解引用
    int first = *begin_it;        // 获取第一个元素的值
    *begin_it = 10;               // 修改第一个元素的值
    
    // 递增
    auto it = begin_it;
    ++it;                         // 移动到下一个元素
    it++;                         // 移动到下一个元素
    
    // 比较
    if (it != end_it) {
        std::cout << "迭代器有效" << std::endl;
    }
    
    // 迭代器遍历
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

不同容器的迭代器特性

void iterator_properties() {
    // vector - 随机访问迭代器
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto vec_it = vec.begin();
    vec_it += 3;                  // 支持随机访问
    int value = vec_it[2];        // 支持下标访问
    if (vec_it > vec.begin()) {   // 支持比较
        // ...
    }
    
    // list - 双向迭代器
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lst_it = lst.begin();
    ++lst_it;                     // 支持向前移动
    --lst_it;                     // 支持向后移动
    // lst_it += 2;               // 错误：不支持随机访问
    // int val = lst_it[2];       // 错误：不支持下标访问
    
    // set - 双向迭代器（const迭代器）
    std::set<int> s = {1, 2, 3, 4, 5};
    auto set_it = s.begin();
    // *set_it = 10;              // 错误：set迭代器是const的
    int read_value = *set_it;     // 只能读取
    
    // map - 双向迭代器
    std::map<std::string, int> m = {{"a", 1}, {"b", 2}};
    auto map_it = m.begin();
    map_it->first;                // 访问键（只读）
    map_it->second = 3;           // 可以修改值
}

3.3. 迭代器适配器

迭代器适配器是特殊的迭代器，它们修改或增强现有迭代器的行为。常见的迭代器适配器有：

反向迭代器（Reverse Iterators）：允许反向遍历容器。

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << " ";  // 输出: 5 4 3 2 1
}

插入迭代器（Insert Iterators）：用于将元素插入容器，而不是覆盖现有元素。

#include <iterator>
#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3};
    std::list<int> lst;
    
    // 使用back_inserter（尾部插入）
    std::copy(v.begin(), v.end(), std::back_inserter(lst));
    // lst: 1 2 3
    
    // 使用front_inserter（头部插入）
    std::list<int> lst2;
    std::copy(v.begin(), v.end(), std::front_inserter(lst2));
    // lst2: 3 2 1（注意顺序）
    
    // 使用inserter（指定位置插入）
    std::vector<int> v2 = {4, 5, 6};
    std::copy(v2.begin(), v2.end(), std::inserter(lst, lst.begin()));
    // lst: 4 5 6 1 2 3
    
    return 0;
}

流迭代器（Stream Iterators）：用于从流中读取或写入数据。

#include <iterator>
#include <vector>
#include <iostream>
#include <sstream>

int main() {
    // 从标准输入读取整数
    std::cout << "请输入一些整数，以Ctrl+D结束: ";
    std::istream_iterator<int> input_begin(std::cin);
    std::istream_iterator<int> input_end;
    std::vector<int> numbers(input_begin, input_end);
    
    // 输出到标准输出
    std::cout << "你输入的数字是: ";
    std::ostream_iterator<int> output(std::cout, " ");
    std::copy(numbers.begin(), numbers.end(), output);
    std::cout << std::endl;
    
    // 从字符串流读取
    std::stringstream ss("1 2 3 4 5");
    std::istream_iterator<int> ss_begin(ss);
    std::istream_iterator<int> ss_end;
    std::vector<int> nums(ss_begin, ss_end);
    
    return 0;
}

移动迭代器（Move Iterators，C++11引入）：将迭代器的解引用操作转换为移动操作。

#include <iterator>
#include <vector>
#include <string>
#include <iostream>

int main() {
    std::vector<std::string> src = {"apple", "banana", "cherry"};
    std::vector<std::string> dst;
    
    // 使用移动迭代器将元素从src移动到dst
    dst.assign(std::make_move_iterator(src.begin()),
               std::make_move_iterator(src.end()));
    
    std::cout << "src: ";
    for (const auto& s : src) {
        std::cout << "\"" << s << "\" ";  // 注意：移动后src中的字符串处于有效但未指定状态
    }
    std::cout << std::endl;
    
    std::cout << "dst: ";
    for (const auto& s : dst) {
        std::cout << "\"" << s << "\" ";
    }
    std::cout << std::endl;
    
    return 0;
}

3.4. 迭代器特性

迭代器特性（iterator_traits）是一种模板结构，用于获取迭代器的相关类型信息。它对于编写通用算法非常重要，因为算法需要知道迭代器所指元素的类型等信息。

迭代器特性定义了以下类型：

value_type：迭代器指向的元素的类型
difference_type：两个迭代器之间距离的类型（通常为ptrdiff_t）
pointer：指向元素的指针类型
reference：元素的引用类型
iterator_category：迭代器的类别（五种之一）

4.函数对象（Function Objects）

STL中的函数对象（Function Objects）也称为仿函数（Functors）。它们是行为类似函数的对象，通过重载函数调用运算符（operator()）来实现。函数对象可以像函数一样被调用，同时可以拥有状态（即数据成员），因此比普通函数更加灵活。
函数对象的优点：
1.可以拥有状态：因为函数对象是类实例，可以拥有成员变量，从而记录状态。
2.可以作为模板参数传递：函数对象的类型可以作为模板参数，从而在编译时进行优化。
3.可以被内联：函数对象的operator()可以被编译器内联，提高性能。

4.1.STL中预定义的函数对象

STL在<functional>头文件中定义了一些常用的函数对象，分为以下几类：

算术函数对象:

#include <functional>
#include <iostream>

void arithmetic_functors() {
    // plus: 加法
    std::plus<int> add;
    std::cout << "10 + 5 = " << add(10, 5) << std::endl;  // 15
    
    // minus: 减法
    std::minus<int> sub;
    std::cout << "10 - 5 = " << sub(10, 5) << std::endl;  // 5
    
    // multiplies: 乘法
    std::multiplies<int> mul;
    std::cout << "10 * 5 = " << mul(10, 5) << std::endl;  // 50
    
    // divides: 除法
    std::divides<int> div;
    std::cout << "10 / 5 = " << div(10, 5) << std::endl;  // 2
    
    // modulus: 取模
    std::modulus<int> mod;
    std::cout << "10 % 3 = " << mod(10, 3) << std::endl;  // 1
    
    // negate: 取负
    std::negate<int> neg;
    std::cout << "-10 = " << neg(10) << std::endl;  // -10
}

比较函数对象:

void comparison_functors() {
    // equal_to: 等于
    std::equal_to<int> eq;
    std::cout << "10 == 10: " << eq(10, 10) << std::endl;  // true
    std::cout << "10 == 5: " << eq(10, 5) << std::endl;    // false
    
    // not_equal_to: 不等于
    std::not_equal_to<int> neq;
    std::cout << "10 != 5: " << neq(10, 5) << std::endl;   // true
    
    // greater: 大于
    std::greater<int> gt;
    std::cout << "10 > 5: " << gt(10, 5) << std::endl;     // true
    
    // less: 小于
    std::less<int> lt;
    std::cout << "10 < 5: " << lt(10, 5) << std::endl;     // false
    
    // greater_equal: 大于等于
    std::greater_equal<int> ge;
    std::cout << "10 >= 10: " << ge(10, 10) << std::endl;  // true
    
    // less_equal: 小于等于
    std::less_equal<int> le;
    std::cout << "5 <= 10: " << le(5, 10) << std::endl;    // true
    
    // 在算法中使用比较函数对象
    std::vector<int> v = {5, 3, 1, 4, 2};
    
    // 降序排序
    std::sort(v.begin(), v.end(), std::greater<int>());
    std::cout << "降序排序: ";
    for (int x : v) std::cout << x << " ";  // 5 4 3 2 1
    std::cout << std::endl;
    
    // 升序排序（默认）
    std::sort(v.begin(), v.end(), std::less<int>());
    std::cout << "升序排序: ";
    for (int x : v) std::cout << x << " ";  // 1 2 3 4 5
    std::cout << std::endl;
}

逻辑函数对象:

void logical_functors() {
    // logical_and: 逻辑与
    std::logical_and<bool> land;
    std::cout << "true && false: " << land(true, false) << std::endl;  // false
    std::cout << "true && true: " << land(true, true) << std::endl;    // true
    
    // logical_or: 逻辑或
    std::logical_or<bool> lor;
    std::cout << "true || false: " << lor(true, false) << std::endl;  // true
    std::cout << "false || false: " << lor(false, false) << std::endl; // false
    
    // logical_not: 逻辑非
    std::logical_not<bool> lnot;
    std::cout << "!true: " << lnot(true) << std::endl;   // false
    std::cout << "!false: " << lnot(false) << std::endl; // true
    
    // 在算法中使用逻辑函数对象
    std::vector<bool> flags = {true, false, true, false, true};
    
    // 检查是否所有元素都为true
    bool all_true = std::all_of(flags.begin(), flags.end(), 
                                [](bool b) { return b; });
    std::cout << "所有元素都为true: " << all_true << std::endl;  // false
    
    // 检查是否有任意元素为true
    bool any_true = std::any_of(flags.begin(), flags.end(), 
                                [](bool b) { return b; });
    std::cout << "有任意元素为true: " << any_true << std::endl;  // true
}

位运算函数对象（C++11引入）:

void bitwise_functors() {
    // bit_and: 位与
    std::bit_and<int> band;
    int result = band(0b1010, 0b1100);  // 0b1000 -> 8
    std::cout << "0b1010 & 0b1100 = " << result << std::endl;  // 8
    
    // bit_or: 位或
    std::bit_or<int> bor;
    result = bor(0b1010, 0b1100);       // 0b1110 -> 14
    std::cout << "0b1010 | 0b1100 = " << result << std::endl;  // 14
    
    // bit_xor: 位异或
    std::bit_xor<int> bxor;
    result = bxor(0b1010, 0b1100);      // 0b0110 -> 6
    std::cout << "0b1010 ^ 0b1100 = " << result << std::endl;  // 6
    
    // 在算法中使用位运算函数对象
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {5, 4, 3, 2, 1};
    std::vector<int> result_vec(5);
    
    // 对两个vector进行位与操作
    std::transform(v1.begin(), v1.end(), v2.begin(), result_vec.begin(),
                   std::bit_and<int>());
    
    std::cout << "位与结果: ";
    for (int x : result_vec) std::cout << x << " ";  // 1&5=1, 2&4=0, 3&3=3, 4&2=0, 5&1=1
    std::cout << std::endl;
}

4.2. 自定义函数对象

我们可以通过定义一个类并重载operator()来创建自定义函数对象。

基本函数对象:

class BasicFunctor {
public:
    // 无状态函数对象
    int operator()(int a, int b) const {
        return a + b;
    }
};

void basic_custom_functor() {
    BasicFunctor adder;
    std::cout << "5 + 3 = " << adder(5, 3) << std::endl;
    
    // 临时对象调用
    std::cout << "10 + 20 = " << BasicFunctor()(10, 20) << std::endl;
}

有状态函数对象:

class StatefulFunctor {
private:
    int count;
    int increment;
public:
    StatefulFunctor(int inc = 1) : count(0), increment(inc) {}
    
    int operator()() {
        count += increment;
        return count;
    }
    
    int getCount() const { return count; }
    void reset() { count = 0; }
};

void stateful_functor_example() {
    StatefulFunctor counter1;           // 默认每次增加1
    StatefulFunctor counter2(5);        // 每次增加5
    
    std::cout << "counter1: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << counter1() << " ";  // 1 2 3 4 5
    }
    std::cout << std::endl;
    
    std::cout << "counter2: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << counter2() << " ";  // 5 10 15 20 25
    }
    std::cout << std::endl;
    
    // 在算法中使用有状态函数对象
    std::vector<int> numbers(10);
    StatefulFunctor generator(2);
    
    std::generate(numbers.begin(), numbers.end(), generator);
    
    std::cout << "生成的序列: ";
    for (int n : numbers) {
        std::cout << n << " ";  // 2 4 6 8 10 12 14 16 18 20
    }
    std::cout << std::endl;
}

4.3. 函数适配器

函数适配器是用来适配函数对象，使其与其他函数对象或值组合，形成新的函数对象。C++11之后，函数适配器的使用减少，因为lambda表达式更灵活。但了解一些传统的适配器仍有必要：

bind（C++11引入）- 参数绑定：可以绑定函数对象的参数，并可以重新排列参数顺序

#include <functional>
#include <iostream>

void bind_examples() {
    using namespace std::placeholders;  // 使用占位符 _1, _2, _3...
    
    // 普通函数
    int multiply(int a, int b) {
        return a * b;
    }
    
    // 绑定第一个参数
    auto multiply_by_5 = std::bind(multiply, 5, _1);
    std::cout << "5 * 10 = " << multiply_by_5(10) << std::endl;  // 50
    
    // 绑定第二个参数
    auto multiply_by_3 = std::bind(multiply, _1, 3);
    std::cout << "10 * 3 = " << multiply_by_3(10) << std::endl;  // 30
    
    // 交换参数顺序
    auto multiply_reverse = std::bind(multiply, _2, _1);
    std::cout << "交换参数: " << multiply_reverse(5, 10) << std::endl;  // 50
    
    // 绑定成员函数
    class Calculator {
    public:
        int add(int a, int b) const {
            return a + b;
        }
    };
    
    Calculator calc;
    auto add_10 = std::bind(&Calculator::add, &calc, _1, 10);
    std::cout << "add(5, 10) = " << add_10(5) << std::endl;  // 15
    
    // 绑定数据成员
    struct Point {
        int x, y;
    };
    
    Point p = {10, 20};
    auto get_x = std::bind(&Point::x, _1);
    std::cout << "p.x = " << get_x(p) << std::endl;  // 10
    
    // 组合绑定
    auto complex = std::bind(multiply, 
                            std::bind(std::plus<int>(), _1, 5),  // (x + 5)
                            _2);                                 // * y
    std::cout << "(5 + 5) * 2 = " << complex(5, 2) << std::endl;  // 20
}

function（C++11引入）- 函数包装器：

#include <functional>
#include <iostream>

void function_examples() {
    // 包装普通函数
    int add(int a, int b) { return a + b; }
    
    std::function<int(int, int)> func1 = add;
    std::cout << "add(10, 20) = " << func1(10, 20) << std::endl;  // 30
    
    // 包装函数对象
    struct Multiply {
        int operator()(int a, int b) const {
            return a * b;
        }
    };
    
    Multiply mult;
    std::function<int(int, int)> func2 = mult;
    std::cout << "mult(10, 20) = " << func2(10, 20) << std::endl;  // 200
    
    // 包装lambda表达式
    std::function<int(int, int)> func3 = [](int a, int b) {
        return a - b;
    };
    std::cout << "subtract(20, 10) = " << func3(20, 10) << std::endl;  // 10
    
    // 包装成员函数
    class Math {
    public:
        int square(int x) const {
            return x * x;
        }
        static int cube(int x) {
            return x * x * x;
        }
    };
    
    Math math;
    std::function<int(const Math&, int)> func4 = &Math::square;
    std::cout << "math.square(5) = " << func4(math, 5) << std::endl;  // 25
    
    std::function<int(int)> func5 = Math::cube;
    std::cout << "Math::cube(3) = " << func5(3) << std::endl;  // 27
    
    // 作为回调函数
    class Button {
        std::function<void()> onClick;
    public:
        void setOnClick(std::function<void()> callback) {
            onClick = callback;
        }
        void click() {
            if (onClick) onClick();
        }
    };
    
    Button button;
    button.setOnClick([]() {
        std::cout << "按钮被点击了！" << std::endl;
    });
    button.click();
    
    // 判断是否为空
    std::function<void()> empty_func;
    if (!empty_func) {
        std::cout << "函数对象为空" << std::endl;
    }
}

mem_fn（C++11引入）- 成员函数适配器

#include <functional>
#include <vector>
#include <algorithm>

void mem_fn_examples() {
    class Person {
    public:
        std::string name;
        int age;
        
        Person(std::string n, int a) : name(std::move(n)), age(a) {}
        
        bool isAdult() const {
            return age >= 18;
        }
        
        void birthday() {
            ++age;
        }
        
        std::string getName() const {
            return name;
        }
    };
    
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 17},
        {"Charlie", 30},
        {"David", 16},
        {"Eve", 20}
    };
    
    // 使用mem_fn调用成员函数
    // 统计成年人数量
    int adult_count = std::count_if(people.begin(), people.end(),
                                    std::mem_fn(&Person::isAdult));
    std::cout << "成年人数量: " << adult_count << std::endl;  // 3
    
    // 获取所有人的名字
    std::vector<std::string> names;
    std::transform(people.begin(), people.end(), std::back_inserter(names),
                   std::mem_fn(&Person::getName));
    
    std::cout << "名字: ";
    for (const auto& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;
    
    // 给所有人过生日
    std::for_each(people.begin(), people.end(),
                  std::mem_fn(&Person::birthday));
    
    std::cout << "过生日后的年龄: ";
    for (const auto& p : people) {
        std::cout << p.name << ":" << p.age << " ";
    }
    std::cout << std::endl;
    
    // 访问数据成员
    std::vector<int> ages;
    std::transform(people.begin(), people.end(), std::back_inserter(ages),
                   std::mem_fn(&Person::age));
    
    std::cout << "年龄: ";
    for (int age : ages) {
        std::cout << age << " ";
    }
    std::cout << std::endl;
}

函数对象与lambda表达式：从C++11开始，lambda表达式提供了另一种创建函数对象的方式，通常更简洁。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 使用lambda表达式作为函数对象
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a > b; // 降序排序
    });

    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // lambda表达式可以捕获变量，类似于有状态的函数对象
    int factor = 3;
    std::transform(v.begin(), v.end(), v.begin(), [factor](int x) {
        return x * factor;
    });

    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

5.适配器（Adapters）

STL适配器是一种设计模式，它用于修改或调整其他组件的接口，使其适应不同的需求。STL中的适配器主要分为三类：容器适配器、迭代器适配器和函数适配器。

适配器分类：
容器适配器：基于其他容器实现的特殊数据结构
迭代器适配器：改变迭代器的行为
函数适配器：修改函数对象的行为
适配器特点：
不提供新功能，而是改变现有组件的接口
实现组件复用
提高代码的灵活性和可重用性

6.分配器（Allocators）

STL中的分配器（Allocators）是用于内存管理的组件，它封装了内存分配和释放的细节，使得STL容器能够独立于具体的内存管理方式。分配器是一个模板类，它定义了如何为容器分配和释放内存，以及如何构造和销毁对象。
分配器的作用
1.分离内存分配与对象构造
2.分离对象析构与内存释放
3.提供一种可定制内存管理策略的机制

6.1.标准分配器

C++标准库提供了一个默认的分配器std::allocator，它使用::operator new和::operator delete来分配和释放内存。

标准分配器（std::allocator）的基本使用

#include <memory>  // allocator 头文件
#include <iostream>

void basic_allocator_usage() {
    // 创建int类型的分配器
    std::allocator<int> alloc;
    
    // 分配可以存储5个int的内存（不构造对象）
    int* p = alloc.allocate(5);
    
    // 在已分配的内存上构造对象
    for (int i = 0; i < 5; ++i) {
        alloc.construct(p + i, i * 10);  // 在p[i]处构造int，值为i*10
    }
    
    // 使用构造的对象
    for (int i = 0; i < 5; ++i) {
        std::cout << p[i] << " ";  // 输出: 0 10 20 30 40
    }
    std::cout << std::endl;
    
    // 销毁对象（但不释放内存）
    for (int i = 0; i < 5; ++i) {
        alloc.destroy(p + i);
    }
    
    // 释放内存
    alloc.deallocate(p, 5);
}

分配器的方法

void allocator_methods() {
    std::allocator<std::string> alloc;
    
    // 1. allocate: 分配原始内存
    std::string* ptr = alloc.allocate(3);  // 分配3个string的内存
    
    // 2. construct: 构造对象（C++17前，C++17后已弃用）
    alloc.construct(ptr, "Hello");         // 构造第一个string
    alloc.construct(ptr + 1, "World");     // 构造第二个string
    alloc.construct(ptr + 2, "!");         // 构造第三个string
    
    // 3. destroy: 销毁对象（C++17前，C++17后已弃用）
    alloc.destroy(ptr);
    alloc.destroy(ptr + 1);
    alloc.destroy(ptr + 2);
    
    // 4. deallocate: 释放内存
    alloc.deallocate(ptr, 3);
    
    // 5. max_size: 最大可分配数量（已弃用）
    // std::size_t max = alloc.max_size();
    
    // C++17推荐使用allocator_traits
}

使用allocator_traits（C++11）

#include <memory>

void allocator_traits_example() {
    using Alloc = std::allocator<int>;
    using Traits = std::allocator_traits<Alloc>;
    
    Alloc alloc;
    
    // 通过traits分配内存
    int* p = Traits::allocate(alloc, 5);
    
    // 通过traits构造对象
    for (int i = 0; i < 5; ++i) {
        Traits::construct(alloc, p + i, i * 10);
    }
    
    for (int i = 0; i < 5; ++i) {
        std::cout << p[i] << " ";  // 0 10 20 30 40
    }
    std::cout << std::endl;
    
    // 通过traits销毁对象
    for (int i = 0; i < 5; ++i) {
        Traits::destroy(alloc, p + i);
    }
    
    // 通过traits释放内存
    Traits::deallocate(alloc, p, 5);
    
    // 获取最大可分配大小
    auto max_size = Traits::max_size(alloc);
    std::cout << "max_size: " << max_size << std::endl;
}

6.2.分配器特性（Allocator Traits）

C++11引入了 allocator_traits，提供了一种统一的方式来访问分配器的属性，即使分配器没有提供某些成员，allocator_traits 也会提供默认实现。

allocator_traits 的主要功能

#include <memory>
#include <iostream>

void allocator_traits_features() {
    using Alloc = std::allocator<int>;
    using Traits = std::allocator_traits<Alloc>;
    
    Alloc alloc;
    
    // 1. 类型定义
    using value_type = Traits::value_type;           // int
    using pointer = Traits::pointer;                 // int*
    using const_pointer = Traits::const_pointer;     // const int*
    using void_pointer = Traits::void_pointer;       // void*
    using const_void_pointer = Traits::const_void_pointer;  // const void*
    using difference_type = Traits::difference_type; // ptrdiff_t
    using size_type = Traits::size_type;             // size_t
    
    // 2. 传播特性（用于控制分配器的复制行为）
    using propagate_on_container_copy_assignment = 
        Traits::propagate_on_container_copy_assignment;  // false_type
    using propagate_on_container_move_assignment = 
        Traits::propagate_on_container_move_assignment;  // false_type
    using propagate_on_container_swap = 
        Traits::propagate_on_container_swap;              // false_type
    
    // 3. 分配器是否总是相等
    using is_always_equal = Traits::is_always_equal;      // true_type
    
    std::cout << "propagate_on_container_copy_assignment: " 
              << propagate_on_container_copy_assignment::value << std::endl;
    std::cout << "propagate_on_container_move_assignment: " 
              << propagate_on_container_move_assignment::value << std::endl;
    std::cout << "is_always_equal: " 
              << is_always_equal::value << std::endl;
}

6.3.分配器与容器

容器如何与分配器交互

void container_allocator_interaction() {
    // 1. 容器构造时接收分配器
    std::allocator<int> alloc;
    std::vector<int, std::allocator<int>> v1(alloc);
    
    // 2. 获取容器的分配器
    auto alloc_copy = v1.get_allocator();
    
    // 3. 分配器感知的容器操作
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    std::vector<int> v3(v2.get_allocator());  // 使用相同的分配器
    
    // 4. 使用分配器分配内存
    auto& alloc_ref = v3.get_allocator();
    int* p = alloc_ref.allocate(10);
    
    // ... 使用内存 ...
    
    alloc_ref.deallocate(p, 10);
    
    // 5. 使用自定义分配器的容器
    SimpleAllocator<double> custom_alloc;
    std::vector<double, SimpleAllocator<double>> v4(custom_alloc);
    
    for (int i = 0; i < 10; ++i) {
        v4.push_back(i * 3.14);
    }
}

分配器对容器行为的影响

template<typename T>
class DebugAllocator {
public:
    using value_type = T;
    
    T* allocate(std::size_t n) {
        std::cout << "分配 " << n << " 个 " << typeid(T).name() << std::endl;
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    
    void deallocate(T* p, std::size_t n) {
        std::cout << "释放 " << n << " 个 " << typeid(T).name() << std::endl;
        ::operator delete(p);
    }
    
    template<typename U>
    struct rebind {
        using other = DebugAllocator<U>;
    };
};

template<typename T, typename U>
bool operator==(const DebugAllocator<T>&, const DebugAllocator<U>&) {
    return true;
}

template<typename T, typename U>
bool operator!=(const DebugAllocator<T>&, const DebugAllocator<U>&) {
    return false;
}

void allocator_effect_on_container() {
    // 使用调试分配器的vector
    std::cout << "=== vector with debug allocator ===" << std::endl;
    std::vector<int, DebugAllocator<int>> v;
    
    // 观察vector如何分配内存
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        std::cout << "size: " << v.size() 
                  << ", capacity: " << v.capacity() << std::endl;
    }
    
    // 使用调试分配器的map
    std::cout << "\n=== map with debug allocator ===" << std::endl;
    std::map<std::string, int, std::less<std::string>, 
             DebugAllocator<std::pair<const std::string, int>>> m;
    
    m["apple"] = 3;
    m["banana"] = 5;
    m["cherry"] = 2;
    m["date"] = 7;
}

6.4.自定义分配器

简单自定义分配器实现

#include <cstdlib>  // malloc, free
#include <iostream>
#include <memory>
#include <new>

template<typename T>
class SimpleAllocator {
public:
    // 类型定义（必须）
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    
    // 支持分配其他类型的rebind模板（必须）
    template<typename U>
    struct rebind {
        using other = SimpleAllocator<U>;
    };
    
    // 构造函数
    SimpleAllocator() noexcept = default;
    
    template<typename U>
    SimpleAllocator(const SimpleAllocator<U>&) noexcept {}
    
    // 分配内存
    pointer allocate(size_type n, const void* hint = 0) {
        if (n > max_size()) {
            throw std::bad_alloc();
        }
        
        // 使用malloc分配内存
        if (auto p = static_cast<pointer>(std::malloc(n * sizeof(T)))) {
            std::cout << "分配 " << n << " 个 " << typeid(T).name() 
                      << " (" << n * sizeof(T) << " 字节)" << std::endl;
            return p;
        }
        throw std::bad_alloc();
    }
    
    // 释放内存
    void deallocate(pointer p, size_type n) noexcept {
        std::cout << "释放 " << n << " 个 " << typeid(T).name() 
                  << " (" << n * sizeof(T) << " 字节)" << std::endl;
        std::free(p);
    }
    
    // 最大可分配数量
    size_type max_size() const noexcept {
        return std::size_t(-1) / sizeof(T);
    }
    
    // 构造对象
    template<typename U, typename... Args>
    void construct(U* p, Args&&... args) {
        ::new(static_cast<void*>(p)) U(std::forward<Args>(args)...);
    }
    
    // 销毁对象
    template<typename U>
    void destroy(U* p) {
        p->~U();
    }
    
    // 获取地址
    pointer address(reference x) const noexcept { return &x; }
    const_pointer address(const_reference x) const noexcept { return &x; }
};

// 比较操作符（必须）
template<typename T, typename U>
bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&) noexcept {
    return true;
}

template<typename T, typename U>
bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) noexcept {
    return false;
}

void custom_allocator_example() {
    // 使用自定义分配器的vector
    std::vector<int, SimpleAllocator<int>> v;
    
    for (int i = 0; i < 5; ++i) {
        v.push_back(i * 10);
    }
    
    std::cout << "vector元素: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 使用自定义分配器的map
    std::map<std::string, int, std::less<std::string>, 
             SimpleAllocator<std::pair<const std::string, int>>> m;
    
    m["apple"] = 3;
    m["banana"] = 5;
    m["cherry"] = 2;
    
    for (const auto& p : m) {
        std::cout << p.first << ": " << p.second << std::endl;
    }
}