C++标准模板库STL(Standard Template Library)全解析
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>一.STL 概述</li><li>二.STL 的六大组件</li><ul class="second_class_ul"><li>1.容器（Containers）</li><ul class="third_class_ul"><li>1.1序列式容器（顺序容器）</li><li>1.2关联式容器（有序容器）</li><li>1.3无序关联式容器（哈希容器，C++11引入）</li><li>1.4 容器适配器</li></ul><li>2.算法（Algorithms）</li><ul class="third_class_ul"><li>2.1. 非修改序列算法</li><li>2.2. 修改序列算法</li><li>2.3. 排序和相关算法</li><li>2.4. 数值算法</li></ul><li>3.迭代器（Iterators）</li><ul class="third_class_ul"><li>3.1. 迭代器类别</li><li>3.2. 迭代器使用</li><li>3.3. 迭代器适配器</li><li>3.4. 迭代器特性</li></ul><li>4.函数对象（Function Objects）</li><ul class="third_class_ul"><li>4.1.STL中预定义的函数对象</li><li>4.2. 自定义函数对象</li><li>4.3. 函数适配器</li></ul><li>5.适配器（Adapters）</li><ul class="third_class_ul"></ul><li>6.分配器（Allocators）</li><ul class="third_class_ul"><li>6.1.标准分配器</li><li>6.2.分配器特性（Allocator Traits）</li><li>6.3.分配器与容器</li><li>6.4.自定义分配器</li></ul></ul></ul></div><p class="maodian"></p><h2>一.STL 概述</h2><p></p>
<ul><li>C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。</li><li>STL 的设计基于泛型编程，这意味着使用模板可以编写出独立于任何特定数据类型的代码。</li><li>STL 分为多个组件，包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函数对象（Function Objects）、适配器（Adapters）和 分配器（Allocators）等。</li><li>使用 STL 的好处:</li><li>代码复用：STL 提供了大量的通用数据结构和算法，可以减少重复编写代码的工作。</li><li>性能优化：STL 中的算法和数据结构都经过了优化，以提供最佳的性能。</li><li>泛型编程：使用模板，STL 支持泛型编程，使得算法和数据结构可以适用于任何数据类型。</li><li>易于维护：STL 的设计使得代码更加模块化，易于阅读和维护。</li></ul>
<p class="maodian"></p><h2>二.STL 的六大组件</h2>
<table><thead><tr><th>组件</th><th>功能描述</th></tr></thead><tbody><tr><td>容器（Containers）</td><td>管理数据集合</td></tr><tr><td>算法（Algorithms）</td><td>操作容器中的元素</td></tr><tr><td>迭代器（Iterators）</td><td>连接容器和算法的桥梁</td></tr><tr><td>函数对象（Function Objects）</td><td>使算法更加灵活</td></tr><tr><td>适配器（Adapters）</td><td>修改或组合组件</td></tr><tr><td>分配器（Allocators）</td><td>内存管理</td></tr></tbody></table>
<p class="maodian"></p><h3>1.容器（Containers）</h3>
<p>容器是 STL 中最基本的组件之一，用于存储和管理数据集合。所有容器都是模板类，可以存储任意类型的数据。容器提供了各种数据结构，包括向量（vector）、链表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等。这些容器具有不同的特性和用途，可以根据实际需求选择合适的容器。</p>
<p class="maodian"></p><h4>1.1序列式容器（顺序容器）</h4>
<p>元素按线性顺序排列，每个元素都有固定位置，位置取决于插入的时间和位置。允许双向遍历。</p>
<ul><li><strong>vector（动态数组）</strong>：支持快速随机访问。将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速，但是在中部或头部安插元素比较费时。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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 = 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); // 清空并释放所有内存</pre></div>
<ul><li><strong>deque（双端队列）</strong>：支持快速插入和删除。是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速，但是在中部安插元素比较费时。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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 = 99; // O(1)
// 中间操作（低效）
dq.insert(dq.begin() + 2, 88); // O(n)
// 应用场景：需要两端快速操作的序列</pre></div>
<ul><li><strong>list（双向链表）</strong>：支持快速插入和删除，但不支持随机访问。不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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 << " ";
}
// 应用场景：频繁在任意位置插入删除</pre></div>
<ul><li><strong>forward_list（单向链表，C++11引入）</strong>：</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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后的元素
// 更节省内存，但功能受限</pre></div>
<ul><li><strong>array（固定数组，C++11引入）</strong>：</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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 << " ";
}
// 编译时确定大小，栈上分配</pre></div>
<p class="maodian"></p><h4>1.2关联式容器（有序容器）</h4>
<p>元素按键（Key）排序，通过键快速访问元素。存储键值对，每个元素都有一个键（key）和一个值（value），并且通过键来组织元素。元素位置取决于特定的排序准则，和插入顺序无关。</p>
<ul><li><strong>set（集合）</strong>：不允许重复元素。内部的元素依据其值自动排序，set 内的相同数值的元素只能出现一次。内部由二叉树实现，便于查找。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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</pre></div>
<ul><li><strong>multiset（多重集合）</strong>：允许多个元素具有相同的键。内部的元素依据其值自动排序，multiset 内可包含多个数值相同的元素，内部由二叉树实现，便于查找。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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 << " ";
}</pre></div>
<ul><li><strong>map（映射）</strong>：每个键映射到一个值。map 的元素是成对的键值 / 实值，内部的元素依据其值自动排序，map 内的相同数值的元素只能出现一次。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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& : 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; // 按键降序排列</pre></div>
<ul><li><strong>multimap（多重映射）</strong>：存储了键值对（pair），其中键是唯一的，但值可以重复，允许一个键映射到多个值。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}
// 应用场景：一对多映射关系</pre></div>
<p class="maodian"></p><h4>1.3无序关联式容器（哈希容器，C++11引入）</h4>
<p>元素基于哈希表组织，不保证顺序。支持快速的查找、插入和删除。<br />-<strong>unordered_set（无序集合）</strong>：</p>
<div class="jb51code"><pre class="brush:cpp;">#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;</pre></div>
<ul><li><strong>unordered_map（无序映射）</strong>：</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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& : um) {
cout << key << ": " << value << endl;
}
// 应用场景：需要快速查找，不关心顺序</pre></div>
<p class="maodian"></p><h4>1.4 容器适配器</h4>
<p>基于其他容器实现特殊接口。</p>
<ul><li><strong>stack（栈）</strong>：后进先出（LIFO）的数据结构</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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没有迭代器，只能访问栈顶</pre></div>
<ul><li><strong>queue（队列）</strong>：先进先出（FIFO）的数据结构</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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没有迭代器</pre></div>
<ul><li><strong>priority_queue（优先队列）</strong>：元素按优先级出队，默认最大元素优先</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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();
}</pre></div>
<p class="maodian"></p><h3>2.算法（Algorithms）</h3>
<ul><li>STL算法是STL中非常重要的一部分，它们提供了大量的标准算法，用于对容器中的元素进行操作。这些算法覆盖了常见的操作，如查找、排序、复制、修改等。STL算法通过迭代器与容器进行交互，因此它们可以用于不同类型的容器，只需要指定要操作的范围即可。</li><li>STL算法的特点</li><li>通过迭代器操作，与容器解耦</li><li>大多数算法在<algorithm>头文件中</li><li>数值算法在 <numeric>头文件中</li><li>STL算法大致可以分为以下几类：</li></ul>
<blockquote><p>非修改序列算法：不会改变容器中的内容，例如查找、计数等。<br />修改序列算法：会改变容器中的内容，例如复制、替换、填充等。<br />排序和相关算法：包括排序、合并、二分查找等。<br />数值算法：例如累加、内积等。</p></blockquote>
<p class="maodian"></p><h4>2.1. 非修改序列算法</h4>
<ul><li><strong>查找算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}
}</pre></div>
<ul><li><strong>计数算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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
}</pre></div>
<ul><li><strong>比较算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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
}</pre></div>
<ul><li><strong>遍历算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<ul><li><strong>搜索算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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
}</pre></div>
<p class="maodian"></p><h4>2.2. 修改序列算法</h4>
<ul><li><strong>复制算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>移动算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<ul><li><strong>变换算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
fib = 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;
}</pre></div>
<ul><li><strong>替换算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>填充算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li>删除算法</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>交换算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<p class="maodian"></p><h4>2.3. 排序和相关算法</h4>
<ul><li><strong>排序算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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 << 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;
}
}</pre></div>
<ul><li><strong>二分查找算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}
}</pre></div>
<ul><li><strong>合并算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>集合算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>堆算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>最值算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>排列算法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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()));
}</pre></div>
<p class="maodian"></p><h4>2.4. 数值算法</h4>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<p class="maodian"></p><h3>3.迭代器（Iterators）</h3>
<ul><li>迭代器用于遍历容器中的元素，它是一种类似指针的对象，允许以统一的方式访问容器中的元素，而不用了解容器的内部实现细节。</li><li>迭代器的作用<br />1.连接容器和算法<br />2.提供统一的访问接口<br />3.支持泛型编程</li></ul>
<p class="maodian"></p><h4>3.1. 迭代器类别</h4>
<ul><li>五种迭代器类别</li></ul>
<blockquote><p>// 迭代器分类（按功能从弱到强）</p>
<ol><li>输入迭代器 (Input Iterator) - 只读，只能向前移动</li><li>输出迭代器 (Output Iterator) - 只写，只能向前移动</li><li>前向迭代器 (Forward Iterator) - 可读写，只能向前移动</li><li>双向迭代器 (Bidirectional Iterator) - 可读写，可向前向后移动</li><li>随机访问迭代器 (Random Access Iterator) - 可读写，支持随机访问</li></ol></blockquote>
<ul><li>各类迭代器的能力矩阵</li></ul>
<table><thead><tr><th>操作</th><th>输入</th><th>输出</th><th>前向</th><th>双向</th><th>随机访问</th></tr></thead><tbody><tr><td>读 (*it)</td><td>✓</td><td></td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>写 (*it = value)</td><td></td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>递增 (++)</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>递减 (–)</td><td></td><td></td><td></td><td>✓</td><td>✓</td></tr><tr><td>比较 (==, !=)</td><td>✓</td><td></td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>一次遍历</td><td>✓</td><td>✓</td><td></td><td></td><td></td></tr><tr><td>多次遍历</td><td></td><td></td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>加/减整数 (it + n)</td><td></td><td></td><td></td><td></td><td>✓</td></tr><tr><td>下标访问 (it)</td><td></td><td></td><td></td><td></td><td>✓</td></tr><tr><td>比较大小 (<, >)</td><td></td><td></td><td></td><td></td><td>✓</td></tr><tr><td>距离 (it1 - it2)</td><td></td><td></td><td></td><td></td><td>✓</td></tr></tbody></table>
<p class="maodian"></p><h4>3.2. 迭代器使用</h4>
<ul><li><strong>获取迭代器</strong><br />每个容器都提供了获取迭代器的成员函数：<br />begin()、end()：返回指向第一个元素和尾后位置的迭代器<br />cbegin()、cend()：返回const迭代器（C++11引入）<br />rbegin()、rend()：返回反向迭代器<br />crbegin()、crend()：返回const反向迭代器（C++11引入）</li><li><strong>迭代器操作示例</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<ul><li><strong>不同容器的迭代器特性</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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; // 支持下标访问
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; // 错误：不支持下标访问
// 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; // 可以修改值
}</pre></div>
<p class="maodian"></p><h4>3.3. 迭代器适配器</h4>
<p>迭代器适配器是特殊的迭代器，它们修改或增强现有迭代器的行为。常见的迭代器适配器有：</p>
<ul><li><strong>反向迭代器（Reverse Iterators）</strong>：允许反向遍历容器。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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
}
</pre></div>
<ul><li><strong>插入迭代器（Insert Iterators）</strong>：用于将元素插入容器，而不是覆盖现有元素。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<ul><li><strong>流迭代器（Stream Iterators）</strong>：用于从流中读取或写入数据。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<ul><li><strong>移动迭代器（Move Iterators，C++11引入）</strong>：将迭代器的解引用操作转换为移动操作。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<p class="maodian"></p><h4>3.4. 迭代器特性</h4>
<p>迭代器特性（iterator_traits）是一种模板结构，用于获取迭代器的相关类型信息。它对于编写通用算法非常重要，因为算法需要知道迭代器所指元素的类型等信息。</p>
<p>迭代器特性定义了以下类型：</p>
<blockquote><p>value_type：迭代器指向的元素的类型<br />difference_type：两个迭代器之间距离的类型（通常为ptrdiff_t）<br />pointer：指向元素的指针类型<br />reference：元素的引用类型<br />iterator_category：迭代器的类别（五种之一）</p></blockquote>
<p class="maodian"></p><h3>4.函数对象（Function Objects）</h3>
<ul><li>STL中的函数对象（Function Objects）也称为仿函数（Functors）。它们是行为类似函数的对象，通过重载函数调用运算符（operator()）来实现。函数对象可以像函数一样被调用，同时可以拥有状态（即数据成员），因此比普通函数更加灵活。</li><li>函数对象的优点：<br />1.可以拥有状态：因为函数对象是类实例，可以拥有成员变量，从而记录状态。<br />2.可以作为模板参数传递：函数对象的类型可以作为模板参数，从而在编译时进行优化。<br />3.可以被内联：函数对象的operator()可以被编译器内联，提高性能。</li></ul>
<p class="maodian"></p><h4>4.1.STL中预定义的函数对象</h4>
<p>STL在<functional>头文件中定义了一些常用的函数对象，分为以下几类：</p>
<ul><li><strong>算术函数对象</strong>:</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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
}</pre></div>
<ul><li><strong>比较函数对象</strong>:</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>逻辑函数对象</strong>:</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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
}</pre></div>
<ul><li><strong>位运算函数对象（C++11引入）</strong>:</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<p class="maodian"></p><h4>4.2. 自定义函数对象</h4>
<p>我们可以通过定义一个类并重载operator()来创建自定义函数对象。</p>
<ul><li><strong>基本函数对象</strong>:</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<ul><li><strong>有状态函数对象</strong>:</li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<p class="maodian"></p><h4>4.3. 函数适配器</h4>
<p>函数适配器是用来适配函数对象，使其与其他函数对象或值组合，形成新的函数对象。C++11之后，函数适配器的使用减少，因为lambda表达式更灵活。但了解一些传统的适配器仍有必要：</p>
<ul><li><strong>bind（C++11引入）- 参数绑定</strong>：可以绑定函数对象的参数，并可以重新排列参数顺序</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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
}</pre></div>
<ul><li><strong>function（C++11引入）- 函数包装器</strong>：</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}
}</pre></div>
<ul><li><strong>mem_fn（C++11引入）- 成员函数适配器</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<ul><li><strong>函数对象与lambda表达式</strong>：从C++11开始，lambda表达式提供了另一种创建函数对象的方式，通常更简洁。</li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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(), (int x) {
return x * factor;
});
for (int x : v) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}</pre></div>
<p class="maodian"></p><h3>5.适配器（Adapters）</h3>
<ul><li>STL适配器是一种设计模式，它用于修改或调整其他组件的接口，使其适应不同的需求。STL中的适配器主要分为三类：容器适配器、迭代器适配器和函数适配器。</li></ul>
<ol><li>适配器分类：<br />容器适配器：基于其他容器实现的特殊数据结构<br />迭代器适配器：改变迭代器的行为<br />函数适配器：修改函数对象的行为</li><li>适配器特点：<br />不提供新功能，而是改变现有组件的接口<br />实现组件复用<br />提高代码的灵活性和可重用性</li></ol>
<p class="maodian"></p><h3>6.分配器（Allocators）</h3>
<ul><li>STL中的分配器（Allocators）是用于内存管理的组件，它封装了内存分配和释放的细节，使得STL容器能够独立于具体的内存管理方式。分配器是一个模板类，它定义了如何为容器分配和释放内存，以及如何构造和销毁对象。</li><li>分配器的作用<br />1.分离内存分配与对象构造<br />2.分离对象析构与内存释放<br />3.提供一种可定制内存管理策略的机制</li></ul>
<p class="maodian"></p><h4>6.1.标准分配器</h4>
<p>C++标准库提供了一个默认的分配器std::allocator，它使用::operator new和::operator delete来分配和释放内存。</p>
<ul><li><strong>标准分配器（std::allocator）的基本使用</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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处构造int，值为i*10
}
// 使用构造的对象
for (int i = 0; i < 5; ++i) {
std::cout << p << " ";// 输出: 0 10 20 30 40
}
std::cout << std::endl;
// 销毁对象（但不释放内存）
for (int i = 0; i < 5; ++i) {
alloc.destroy(p + i);
}
// 释放内存
alloc.deallocate(p, 5);
}</pre></div>
<ul><li><strong>分配器的方法</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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
}</pre></div>
<ul><li><strong>使用allocator_traits（C++11）</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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 << " ";// 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;
}</pre></div>
<p class="maodian"></p><h4>6.2.分配器特性（Allocator Traits）</h4>
<p>C++11引入了 allocator_traits，提供了一种统一的方式来访问分配器的属性，即使分配器没有提供某些成员，allocator_traits 也会提供默认实现。</p>
<ul><li><strong>allocator_traits 的主要功能</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}</pre></div>
<p class="maodian"></p><h4>6.3.分配器与容器</h4>
<ul><li><strong>容器如何与分配器交互</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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);
}
}</pre></div>
<ul><li><strong>分配器对容器行为的影响</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">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;
}</pre></div>
<p class="maodian"></p><h4>6.4.自定义分配器</h4>
<ul><li><strong>简单自定义分配器实现</strong></li></ul>
<div class="jb51code"><pre class="brush:cpp;">#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;
}
}</pre></div>
<p>到此这篇关于C++标准模板库STL(Standard Template Library)详解的文章就介绍到这了,更多相关C++标准模板库STL内容请搜索琼殿技术社区以前的文章或继续浏览下面的相关文章希望大家以后多多支持琼殿技术社区！</p>
<div class="art_xg">
<b>您可能感兴趣的文章:</b><ul><li>C++面试八股文之STL标准模板库使用详解</li><li>C++标准模板库STL深入讲解</li><li>C++ 标准模板库 STL 顺序容器详解</li><li>C++标准模板库STL的介绍</li></ul>
</div>
</div>
<!--endmain-->
頁:
[1]