当前位置：首页 > java >正文

STL重点

java 2025/9/5 15:00:35

1.容器：vector,list,map,set的底层实现（数组、链表、红黑树）及时间复杂度

1. 容器分类概览

序列式容器 vs 关联式容器

2. std::vector - 动态数组

底层实现

时间复杂度分析

代码示例

3. std::list - 双向链表

底层实现

时间复杂度分析

代码示例

4. std::map - 有序映射（红黑树）

底层实现：红黑树

时间复杂度分析

代码示例

5. std::set - 有序集合（红黑树）

底层实现

时间复杂度分析

6. 综合对比表

7. 常见问题

Q1: vector的扩容策略是什么？

Q2: 为什么vector的push_back()是分摊O(1)？

Q3: list和vector如何选择？

Q4: 红黑树相比AVL树有什么优势？

Q5: map和unordered_map如何选择？

总结

2.迭代器：种类及失效问题

1. 迭代器基本概念

什么是迭代器？

2. 迭代器的五种类型

1. 输入迭代器（Input Iterator）

2. 输出迭代器（Output Iterator）

3. 前向迭代器（Forward Iterator）

4. 双向迭代器（Bidirectional Iterator）

5. 随机访问迭代器（Random Access Iterator）

迭代器类别总结表

3. 迭代器失效问题

什么是迭代器失效？

1. vector的迭代器失效

2. list的迭代器失效

3. map/set的迭代器失效

4. deque的迭代器失效

4. 迭代器失效规则总结

各容器迭代器失效规则

安全使用准则

5. 特殊迭代器

反向迭代器（Reverse Iterator）

插入迭代器（Insert Iterator）

6. 常见问题

Q1: 什么是迭代器失效？举例说明

Q2: 如何安全地在遍历时删除元素？

Q3: 不同容器的迭代器类别是什么？

Q4: 什么是迭代器 trait？

Q5: 如何实现自定义迭代器？

7. 最佳实践

使用算法避免手动迭代

谨慎保存迭代器

总结

3.算法：find,sort,copy等

2. 非修改序列算法

2.1 find 系列算法

2.2 count 系列算法

2.3 搜索算法

3. 修改序列算法

3.1 copy 系列算法

3.2 transform - 转换算法

3.3 fill/generate - 填充算法

4. 排序和相关算法

4.1 sort 系列算法

5. 数值算法

5.1 数值处理算法

6. 算法实战应用

6.1 remove-erase 惯用法

6.2 算法组合使用

6.3 自定义算法

7. 常见问题

Q1: std::sort 的时间复杂度是多少？

Q2: remove 算法为什么需要配合 erase 使用？

Q3: 什么情况下使用 stable_sort？

Q4: 如何对自定义类型排序？

Q5: 算法和容器成员函数的区别？

8. 性能考虑和最佳实践

算法选择建议

避免不必要的拷贝

总结

1.容器：vector,list,map,set的底层实现（数组、链表、红黑树）及时间复杂度

1. 容器分类概览

序列式容器 vs 关联式容器

// 序列式容器：元素顺序由插入顺序决定
std::vector<int> vec;     // 动态数组
std::list<int> lst;       // 双向链表
std::deque<int> deq;      // 双端队列// 关联式容器：元素按特定顺序存储
std::set<int> s;          // 有序集合（红黑树）
std::map<int, std::string> m; // 有序映射（红黑树）
std::unordered_set<int> us;   // 哈希集合
std::unordered_map<int, std::string> um; // 哈希映射

2. std::vector - 动态数组

底层实现

// vector的简化内存布局
template<typename T>
class vector {
private:T* start;          // 指向首元素T* finish;         // 指向最后一个元素的下一个位置T* end_of_storage; // 指向分配内存的末尾
};

内存增长策略：当容量不足时，通常按2倍或1.5倍扩容，分配新内存，拷贝元素，释放旧内存。

时间复杂度分析

操作	时间复杂度	说明
访问
`operator[]`, `at()`, `front()`, `back()`	O(1)	随机访问，直接通过指针算术
插入
`push_back()` (平均)	O(1)	分摊常数时间（考虑扩容）
`push_back()` (最坏)	O(n)	需要扩容和拷贝所有元素
`insert()` (任意位置)	O(n)	需要移动后续元素
删除
`pop_back()`	O(1)	只需调整指针
`erase()` (任意位置)	O(n)	需要移动后续元素
查找
`find()`	O(n)	线性搜索

代码示例

#include <vector>
#include <iostream>void vector_example() {std::vector<int> vec;// 插入 - 分摊O(1)for (int i = 0; i < 10; ++i) {vec.push_back(i); // 可能触发扩容}// 随机访问 - O(1)std::cout << "Element at index 5: " << vec[5] << std::endl;// 中间插入 - O(n)vec.insert(vec.begin() + 3, 100); // 需要移动后面所有元素// 删除中间元素 - O(n)vec.erase(vec.begin() + 3); // 需要移动后面所有元素
}

3. std::list - 双向链表

底层实现

// list节点的简化结构
template<typename T>
struct list_node {T data;list_node* prev;list_node* next;
};// list的简化结构
template<typename T>
class list {
private:list_node<T>* head; // 头节点（通常包含双向循环）size_t size;
};

时间复杂度分析

操作	时间复杂度	说明
访问
`front()`, `back()`	O(1)	直接访问头尾
任意位置访问	O(n)	需要遍历链表
插入
`push_front()`, `push_back()`	O(1)	直接修改指针
`insert()` (已知位置)	O(1)	只需修改指针
删除
`pop_front()`, `pop_back()`	O(1)	直接修改指针
`erase()` (已知位置)	O(1)	只需修改指针
查找
`find()`	O(n)	需要遍历链表

代码示例

#include <list>
#include <iostream>void list_example() {std::list<int> lst = {1, 2, 3, 4, 5};// 头尾插入 - O(1)lst.push_front(0);lst.push_back(6);// 中间插入 - O(1)（已知迭代器位置）auto it = lst.begin();std::advance(it, 3); // 移动到第4个元素 - O(n)lst.insert(it, 100); // 插入 - O(1)// 删除 - O(1)（已知迭代器位置）it = lst.begin();std::advance(it, 2); // O(n)lst.erase(it);       // O(1)// 查找 - O(n)auto found = std::find(lst.begin(), lst.end(), 4);if (found != lst.end()) {std::cout << "Found: " << *found << std::endl;}
}

4. std::map - 有序映射（红黑树）

底层实现：红黑树

红黑树是一种自平衡的二叉搜索树，满足：

每个节点是红色或黑色
根节点是黑色
所有叶子节点（NIL）是黑色
红色节点的子节点必须是黑色
从任一节点到其每个叶子的所有路径包含相同数目的黑色节点

时间复杂度分析

操作	时间复杂度	说明
访问
`operator[]`, `at()`	O(log n)	二叉搜索树查找
插入
`insert()`	O(log n)	查找位置 + 平衡调整
删除
`erase()`	O(log n)	查找位置 + 平衡调整
查找
`find()`	O(log n)	二叉搜索树查找
遍历
有序遍历	O(n)	中序遍历

代码示例

#include <map>
#include <iostream>void map_example() {std::map<int, std::string> student_map;// 插入 - O(log n)student_map.insert({1, "Alice"});student_map[2] = "Bob";        // O(log n)student_map.emplace(3, "Charlie"); // O(log n)// 查找 - O(log n)auto it = student_map.find(2);if (it != student_map.end()) {std::cout << "Found: " << it->second << std::endl;}// 访问 - O(log n)std::cout << "Student 1: " << student_map.at(1) << std::endl;// 删除 - O(log n)student_map.erase(3);// 有序遍历 - O(n)for (const auto& [id, name] : student_map) {std::cout << id << ": " << name << std::endl;}
}

5. std::set - 有序集合（红黑树）

底层实现

std::set 的底层实现也是红黑树，但只存储键（没有值）。

时间复杂度分析

操作	时间复杂度	说明
插入	O(log n)	查找位置 + 平衡调整
删除	O(log n)	查找位置 + 平衡调整
查找	O(log n)	二叉搜索树查找
遍历	O(n)	中序遍历

#include <set>
#include <iostream>void set_example() {std::set<int> unique_numbers;// 插入 - O(log n)unique_numbers.insert(5);unique_numbers.insert(2);unique_numbers.insert(8);unique_numbers.insert(2); // 重复，不会插入// 查找 - O(log n)if (unique_numbers.find(5) != unique_numbers.end()) {std::cout << "5 exists" << std::endl;}// 删除 - O(log n)unique_numbers.erase(2);// 有序遍历 - O(n)for (int num : unique_numbers) {std::cout << num << " "; // 输出: 5 8}std::cout << std::endl;
}

6. 综合对比表

容器	底层结构	访问	插入	删除	查找	有序	重复元素
vector	动态数组	O(1)	尾部O(1)*	尾部O(1)	O(n)	插入序	允许
list	双向链表	O(n)	O(1)	O(1)	O(n)	插入序	允许
map	红黑树	O(log n)	O(log n)	O(log n)	O(log n)	键序	键唯一
set	红黑树	-	O(log n)	O(log n)	O(log n)	键序	元素唯一

*注：vector的push_back()是分摊O(1)，最坏情况O(n)

7. 常见问题

Q1: vector的扩容策略是什么？

答：通常按2倍或1.5倍扩容。当容量不足时，分配新内存（通常是原来的2倍），拷贝所有元素到新内存，释放旧内存。扩容操作的时间复杂度是O(n)。

Q2: 为什么vector的push_back()是分摊O(1)？

答：虽然单次扩容是O(n)，但经过数学证明，n次push_back()操作的总时间复杂度是O(n)，因此单次操作的分摊时间复杂度是O(1)。

Q3: list和vector如何选择？

答：

需要随机访问：选择vector (O(1))
需要频繁在中间插入删除：选择list (O(1))
内存连续性重要：选择vector
需要大量头尾操作：都可以，但list的push_front也是O(1)

Q4: 红黑树相比AVL树有什么优势？

答：红黑树的平衡要求比AVL树宽松，插入删除时需要更少的旋转操作，因此在实际应用中性能更好，特别是写入操作频繁的场景。

Q5: map和unordered_map如何选择？

答：

需要元素有序：选择map (红黑树)
需要最快查找速度：选择unordered_map (哈希表，平均O(1))
需要内存紧凑：选择map (红黑树更节省内存)
需要频繁插入删除：两者都是O(log n) / O(1)，但unordered_map常数因子更小

总结

理解STL容器的底层实现至关重要：

✅ vector：动态数组，随机访问快，中间操作慢
✅ list：双向链表，插入删除快，随机访问慢
✅ map/set：红黑树，有序，查找插入删除都是O(log n)
✅ 选择策略：根据具体需求选择最合适的容器
✅ 性能特征：不同操作的时间复杂度差异很大

2.迭代器：种类及失效问题

1. 迭代器基本概念

什么是迭代器？

迭代器是STL中用于遍历容器元素的对象，它提供了统一的访问接口，使得算法可以独立于容器类型工作。

#include <vector>
#include <list>
#include <iostream>void iterator_basics() {std::vector<int> vec = {1, 2, 3, 4, 5};std::list<int> lst = {1, 2, 3, 4, 5};// 使用迭代器遍历vectorfor (auto it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用迭代器遍历list（接口相同！）for (auto it = lst.begin(); it != lst.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 这就是STL的设计哲学：算法与容器分离
}

2. 迭代器的五种类型

1. 输入迭代器（Input Iterator）

特性：只读，单向，只能递增

// 典型应用：从输入流读取数据
#include <iterator>
#include <iostream>void input_iterator_example() {std::istream_iterator<int> input_it(std::cin);std::istream_iterator<int> end;while (input_it != end) {std::cout << "Read: " << *input_it << std::endl;++input_it; // 只能向前，不能回头}
}

2. 输出迭代器（Output Iterator）

特性：只写，单向，只能递增

// 典型应用：向输出流写入数据
#include <iterator>
#include <vector>void output_iterator_example() {std::vector<int> vec = {1, 2, 3, 4, 5};std::ostream_iterator<int> output_it(std::cout, " ");for (int num : vec) {*output_it = num; // 只能写入，不能读取++output_it;}
}

3. 前向迭代器（Forward Iterator）

特性：可读写，单向，可多次遍历

// 典型应用：单链表（std::forward_list）
#include <forward_list>void forward_iterator_example() {std::forward_list<int> flist = {1, 2, 3, 4, 5};auto it = flist.begin();std::cout << *it << std::endl; // 读取*it = 100;                     // 写入++it;                          // 只能向前// 可以多次遍历for (auto it = flist.begin(); it != flist.end(); ++it) {std::cout << *it << " ";}
}

4. 双向迭代器（Bidirectional Iterator）

特性：可读写，可向前向后移动

// 典型应用：双向链表（std::list）
#include <list>void bidirectional_iterator_example() {std::list<int> lst = {1, 2, 3, 4, 5};auto it = lst.begin();++it; // 向前--it; // 向后// 反向遍历for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {std::cout << *rit << " ";}
}

5. 随机访问迭代器（Random Access Iterator）

特性：可读写，支持随机访问，算术运算

// 典型应用：数组、vector、deque
#include <vector>void random_access_iterator_example() {std::vector<int> vec = {1, 2, 3, 4, 5};auto it = vec.begin();it += 3;                    // 随机访问std::cout << it[1] << endl; // 支持下标操作std::cout << it - vec.begin() << endl; // 计算距离// 支持比较操作if (it > vec.begin()) {std::cout << "it is after begin" << std::endl;}
}

迭代器类别总结表

迭代器类型	支持操作	典型容器
输入迭代器	只读，++，==，!=	istream
输出迭代器	只写，++	ostream
前向迭代器	读写，++	forward_list
双向迭代器	读写，++，--	list, set, map
随机访问迭代器	读写，++，--，+，-，[]	vector, deque, array

3. 迭代器失效问题

什么是迭代器失效？

当容器结构发生变化（插入、删除元素）时，指向容器元素的迭代器可能变得无效，继续使用会导致未定义行为。

1. vector的迭代器失效

void vector_iterator_invalidation() {std::vector<int> vec = {1, 2, 3, 4, 5};auto it = vec.begin() + 2; // 指向3// 情况1：插入元素可能导致重新分配for (int i = 0; i < 100; ++i) {vec.push_back(i); // 可能触发扩容// 此时it可能失效！}// std::cout << *it << std::endl; // 危险！未定义行为// 情况2：删除元素it = vec.begin() + 2; // 重新获取vec.erase(vec.begin() + 1); // 删除第2个元素// it现在指向什么？可能失效！// 正确做法：使用erase的返回值it = vec.erase(it); // it现在指向被删除元素的下一个元素std::cout << *it << std::endl; // 安全
}

1. vector的迭代器失效

void vector_iterator_invalidation() {std::vector<int> vec = {1, 2, 3, 4, 5};auto it = vec.begin() + 2; // 指向3// 情况1：插入元素可能导致重新分配for (int i = 0; i < 100; ++i) {vec.push_back(i); // 可能触发扩容// 此时it可能失效！}// std::cout << *it << std::endl; // 危险！未定义行为// 情况2：删除元素it = vec.begin() + 2; // 重新获取vec.erase(vec.begin() + 1); // 删除第2个元素// it现在指向什么？可能失效！// 正确做法：使用erase的返回值it = vec.erase(it); // it现在指向被删除元素的下一个元素std::cout << *it << std::endl; // 安全
}

2. list的迭代器失效

void list_iterator_invalidation() {std::list<int> lst = {1, 2, 3, 4, 5};auto it = ++lst.begin(); // 指向2// list的插入不会使其他迭代器失效lst.insert(lst.begin(), 0); // 插入开头std::cout << *it << std::endl; // 安全：仍然指向2// 但删除会使被删除元素的迭代器失效auto to_erase = it;++it; // 先移动下一个迭代器lst.erase(to_erase); // 删除元素2std::cout << *it << std::endl; // 安全：指向3
}

3. map/set的迭代器失效

void map_iterator_invalidation() {std::map<int, std::string> map = {{1, "a"}, {2, "b"}, {3, "c"}};auto it = map.find(2);// 插入不会使迭代器失效map.insert({4, "d"});std::cout << it->second << std::endl; // 安全：仍然指向"b"// 删除会使被删除元素的迭代器失效auto to_erase = it;++it; // 先移动到下一个元素map.erase(to_erase); // 删除键为2的元素std::cout << it->second << std::endl; // 安全：指向"c"
}

4. deque的迭代器失效

void deque_iterator_invalidation() {std::deque<int> deq = {1, 2, 3, 4, 5};auto it = deq.begin() + 2; // 指向3// 在头尾插入通常不会使迭代器失效deq.push_front(0);deq.push_back(6);std::cout << *it << std::endl; // 通常安全：仍然指向3// 在中间插入可能使所有迭代器失效deq.insert(deq.begin() + 2, 100);// std::cout << *it << std::endl; // 危险！可能失效
}

4. 迭代器失效规则总结

各容器迭代器失效规则

容器	插入操作	删除操作
vector	可能所有迭代器失效（扩容时）	被删元素及之后迭代器失效
deque	中间插入：所有迭代器可能失效头尾插入：通常不会失效	中间删除：所有迭代器可能失效头尾删除：通常只使被删迭代器失效
list	不会使任何迭代器失效	只使被删元素的迭代器失效
map/set	不会使任何迭代器失效	只使被删元素的迭代器失效
unordered_ map/set	可能所有迭代器失效（重哈希时）	只使被删元素的迭代器失效

安全使用准则

void safe_iterator_usage() {std::vector<int> vec = {1, 2, 3, 4, 5};// 错误示范：在遍历时修改容器for (auto it = vec.begin(); it != vec.end(); ++it) {if (*it == 3) {vec.erase(it); // 错误！it失效后继续使用// 应该：it = vec.erase(it); 然后 continue;}}// 正确做法1：使用返回值更新迭代器for (auto it = vec.begin(); it != vec.end(); ) {if (*it == 3) {it = vec.erase(it); // erase返回下一个有效迭代器} else {++it;}}// 正确做法2：使用算法remove-erase惯用法vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());
}

5. 特殊迭代器

反向迭代器（Reverse Iterator）

void reverse_iterator_example() {std::vector<int> vec = {1, 2, 3, 4, 5};// 反向遍历for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {std::cout << *rit << " "; // 输出: 5 4 3 2 1}// 反向迭代器与普通迭代器的转换auto rit = vec.rbegin();auto it = rit.base(); // 获取对应的正向迭代器std::cout << *it << std::endl; // 输出rend位置的元素
}

插入迭代器（Insert Iterator）

void insert_iterator_example() {std::vector<int> vec = {1, 2, 3};std::list<int> lst = {4, 5, 6};// 使用插入迭代器拷贝元素std::back_insert_iterator<std::vector<int>> back_inserter(vec);std::copy(lst.begin(), lst.end(), back_inserter);// vec现在: {1, 2, 3, 4, 5, 6}// 简便写法std::copy(lst.begin(), lst.end(), std::back_inserter(vec));
}

6. 常见问题

Q1: 什么是迭代器失效？举例说明

答：迭代器失效是指当容器结构发生变化时，之前获取的迭代器不再指向有效的元素。例如在vector中插入元素可能导致扩容，所有迭代器都失效。

Q2: 如何安全地在遍历时删除元素？

答：

vector/deque：使用 it = vec.erase(it) 并检查返回值
list/map/set：先保存下一个迭代器 next = it++; 再删除
或者使用 remove-erase惯用法

Q3: 不同容器的迭代器类别是什么？

答：

vector, deque, array：随机访问迭代器
list, map, set：双向迭代器
forward_list：前向迭代器
unordered容器：前向迭代器

Q4: 什么是迭代器 trait？

答：迭代器trait是用于在编译期获取迭代器特性的模板类，可以获取迭代器的类别、值类型、差异类型等信息。

Q5: 如何实现自定义迭代器？

答：需要定义相应的iterator_category、value_type、difference_type、pointer、reference类型，并实现相应的操作符重载。

7. 最佳实践

使用算法避免手动迭代

void use_algorithms() {std::vector<int> vec = {1, 2, 3, 4, 5, 3, 2, 1};// 而不是手动遍历删除vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());// 使用算法处理std::sort(vec.begin(), vec.end());auto last = std::unique(vec.begin(), vec.end());vec.erase(last, vec.end());
}

谨慎保存迭代器

void be_careful_with_iterators() {std::vector<int> vec = {1, 2, 3, 4, 5};// 危险：保存迭代器auto saved_it = vec.begin() + 2;// 中间操作可能使迭代器失效for (int i = 0; i < 100; ++i) {vec.push_back(i);}// std::cout << *saved_it << std::endl; // 未定义行为！// 解决方案：保存索引而不是迭代器size_t index = 2;// ... 各种操作std::cout << vec[index] << std::endl; // 安全
}

总结

理解迭代器及其失效机制至关重要：

✅ 迭代器类别：了解不同迭代器的能力和限制
✅ 失效规则：掌握各容器在修改操作后的迭代器状态
✅ 安全实践：使用正确的方法在遍历时修改容器
✅ 算法优先：尽量使用STL算法而不是手动迭代

3.算法：find,sort,copy等

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>void algorithm_intro() {std::vector<int> vec = {5, 2, 8, 1, 9};std::list<int> lst = {5, 2, 8, 1, 9};// 同样的算法适用于不同的容器！std::sort(vec.begin(), vec.end());    // vector支持随机访问// std::sort(lst.begin(), lst.end()); // 错误！list不支持随机访问lst.sort();                           // list有专用的sort成员函数// 但非成员算法如find可以用于任何容器auto vec_it = std::find(vec.begin(), vec.end(), 8);auto lst_it = std::find(lst.begin(), lst.end(), 8);if (vec_it != vec.end()) {std::cout << "Found in vector: " << *vec_it << std::endl;}if (lst_it != lst.end()) {std::cout << "Found in list: " << *lst_it << std::endl;}
}

2. 非修改序列算法

2.1 find 系列算法

#include <algorithm>
#include <vector>
#include <iostream>void find_algorithms() {std::vector<int> vec = {1, 2, 3, 4, 5, 3, 2, 1};// 1. find - 查找单个元素auto it = std::find(vec.begin(), vec.end(), 3);if (it != vec.end()) {std::cout << "Found 3 at position: " << it - vec.begin() << std::endl;}// 2. find_if - 按条件查找auto even_it = std::find_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });if (even_it != vec.end()) {std::cout << "First even number: " << *even_it << std::endl;}// 3. find_if_not - 查找不满足条件的元素auto not_even_it = std::find_if_not(vec.begin(), vec.end(),[](int x) { return x % 2 == 0; });// 4. find_first_of - 查找第一个匹配任何元素的元素std::vector<int> targets = {4, 5};auto first_of_it = std::find_first_of(vec.begin(), vec.end(),targets.begin(), targets.end());
}

2.2 count 系列算法

void count_algorithms() {std::vector<int> vec = {1, 2, 3, 4, 5, 3, 2, 1};// 1. count - 统计元素出现次数int count_3 = std::count(vec.begin(), vec.end(), 3);std::cout << "Number 3 appears " << count_3 << " times" << std::endl;// 2. count_if - 按条件统计int even_count = std::count_if(vec.begin(), vec.end(),[](int x) { return x % 2 == 0; });std::cout << "Even numbers: " << even_count << std::endl;
}

2.3 搜索算法

void search_algorithms() {std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};std::vector<int> pattern = {3, 4, 5};// 1. search - 搜索子序列auto sub_it = std::search(vec.begin(), vec.end(),pattern.begin(), pattern.end());if (sub_it != vec.end()) {std::cout << "Pattern found starting at: " << sub_it - vec.begin() << std::endl;}// 2. adjacent_find - 查找相邻重复元素std::vector<int> with_duplicates = {1, 2, 2, 3, 4, 4, 5};auto adj_it = std::adjacent_find(with_duplicates.begin(), with_duplicates.end());if (adj_it != with_duplicates.end()) {std::cout << "First adjacent duplicate: " << *adj_it << std::endl;}
}

3. 修改序列算法

3.1 copy 系列算法

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>void copy_algorithms() {std::vector<int> source = {1, 2, 3, 4, 5};std::vector<int> destination(5);// 1. copy - 基本拷贝std::copy(source.begin(), source.end(), destination.begin());// 2. copy_if - 条件拷贝std::vector<int> evens;std::copy_if(source.begin(), source.end(), std::back_inserter(evens),[](int x) { return x % 2 == 0; });// 3. copy_n - 拷贝前n个元素std::vector<int> first_three(3);std::copy_n(source.begin(), 3, first_three.begin());// 4. 使用输出迭代器std::ostream_iterator<int> output(std::cout, " ");std::copy(source.begin(), source.end(), output); // 输出到屏幕
}

3.2 transform - 转换算法

void transform_example() {std::vector<int> numbers = {1, 2, 3, 4, 5};std::vector<int> squares(numbers.size());// 1. 一元transform - 对每个元素应用函数std::transform(numbers.begin(), numbers.end(), squares.begin(),[](int x) { return x * x; });// 2. 二元transform - 合并两个序列std::vector<int> a = {1, 2, 3};std::vector<int> b = {4, 5, 6};std::vector<int> result(a.size());std::transform(a.begin(), a.end(), b.begin(), result.begin(),[](int x, int y) { return x + y; });
}

3.3 fill/generate - 填充算法

void fill_algorithms() {std::vector<int> vec(5);// 1. fill - 填充相同值std::fill(vec.begin(), vec.end(), 42);// 2. fill_n - 填充前n个元素std::fill_n(vec.begin(), 3, 100);// 3. generate - 用函数生成值填充int counter = 1;std::generate(vec.begin(), vec.end(), [&counter]() { return counter++; });// 4. iota - 填充递增序列 (C++11)std::vector<int> sequence(5);std::iota(sequence.begin(), sequence.end(), 1); // 1, 2, 3, 4, 5
}

4. 排序和相关算法

4.1 sort 系列算法

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>void sort_algorithms() {std::vector<int> numbers = {5, 2, 8, 1, 9, 3};std::vector<std::string> words = {"apple", "banana", "cherry", "date"};// 1. sort - 默认升序排序std::sort(numbers.begin(), numbers.end());// 2. 自定义比较函数std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; }); // 降序// 3. sort字符串按长度排序std::sort(words.begin(), words.end(),[](const std::string& a, const std::string& b) {return a.length() < b.length();});// 4. partial_sort - 部分排序std::vector<int> large_vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};// 只确保前3个元素是最小的且有序std::partial_sort(large_vec.begin(), large_vec.begin() + 3, large_vec.end());// 5. nth_element - 找到第n小的元素std::nth_element(large_vec.begin(), large_vec.begin() + 4, large_vec.end());std::cout << "5th smallest element: " << large_vec[4] << std::endl;
}

5. 数值算法

5.1 数值处理算法

#include <numeric>
#include <vector>
#include <iostream>void numeric_algorithms() {std::vector<int> numbers = {1, 2, 3, 4, 5};// 1. accumulate - 累加int sum = std::accumulate(numbers.begin(), numbers.end(), 0);std::cout << "Sum: " << sum << std::endl;// 带自定义操作的accumulateint product = std::accumulate(numbers.begin(), numbers.end(), 1,[](int a, int b) { return a * b; });std::cout << "Product: " << product << std::endl;// 2. inner_product - 内积std::vector<int> a = {1, 2, 3};std::vector<int> b = {4, 5, 6};int dot_product = std::inner_product(a.begin(), a.end(), b.begin(), 0);std::cout << "Dot product: " << dot_product << std::endl;// 3. partial_sum - 部分和std::vector<int> prefix_sum(numbers.size());std::partial_sum(numbers.begin(), numbers.end(), prefix_sum.begin());// 4. adjacent_difference - 相邻差std::vector<int> differences(numbers.size());std::adjacent_difference(numbers.begin(), numbers.end(), differences.begin());
}

6. 算法实战应用

6.1 remove-erase 惯用法

void remove_erase_idiom() {std::vector<int> numbers = {1, 2, 3, 4, 5, 3, 2, 1};// 错误：remove只是移动元素，不改变容器大小auto new_end = std::remove(numbers.begin(), numbers.end(), 3);// numbers现在: {1, 2, 4, 5, 2, 1, ?, ?}，大小不变// 正确：remove-erase惯用法numbers.erase(std::remove(numbers.begin(), numbers.end(), 3), numbers.end());// numbers现在: {1, 2, 4, 5, 2, 1}，大小改变
}

6.2 算法组合使用

void algorithm_composition() {std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6, 2, 8, 1};// 1. 去重并排序std::sort(numbers.begin(), numbers.end());auto last = std::unique(numbers.begin(), numbers.end());numbers.erase(last, numbers.end());// 2. 转换并过滤std::vector<int> result;std::transform(numbers.begin(), numbers.end(), std::back_inserter(result),[](int x) { return x * 2; });result.erase(std::remove_if(result.begin(), result.end(),[](int x) { return x < 5; }),result.end());
}

6.3 自定义算法

// 自定义算法：分割字符串
#include <sstream>
#include <iterator>template<typename InputIt, typename OutputIt, typename Delimiter>
void split_string(InputIt begin, InputIt end, OutputIt output, Delimiter delim) {std::stringstream ss(std::string(begin, end));std::string item;while (std::getline(ss, item, delim)) {*output++ = item;}
}void custom_algorithm_example() {std::string text = "apple,banana,cherry,date";std::vector<std::string> fruits;split_string(text.begin(), text.end(), std::back_inserter(fruits), ',');for (const auto& fruit : fruits) {std::cout << fruit << std::endl;}
}

7. 常见问题

Q1: std::sort 的时间复杂度是多少？

答：std::sort 的平均时间复杂度是 O(n log n)，最坏情况下也是 O(n log n)。它通常使用内省排序（introsort）算法。

Q2: remove 算法为什么需要配合 erase 使用？

答：std::remove 只是将不需要的元素移动到容器末尾，返回新的逻辑结束位置，但不改变容器实际大小。需要配合 erase 来实际删除元素。

Q3: 什么情况下使用 stable_sort？

答：当需要保持相等元素的相对顺序时使用 stable_sort。它比 sort 稍慢但保持稳定性。

Q4: 如何对自定义类型排序？

答：有两种方式：

在自定义类型中重载 < 运算符
提供自定义比较函数给 sort 算法

Q5: 算法和容器成员函数的区别？

答：

通用算法：适用于多种容器，通过迭代器工作
成员函数：针对特定容器优化（如 list::sort, list::unique）

8. 性能考虑和最佳实践

算法选择建议

void algorithm_selection() {std::vector<int> data = {/*大量数据*/};// 小数据：使用简单算法if (data.size() < 100) {std::sort(data.begin(), data.end());}// 大数据：考虑性能更好的算法else {std::stable_sort(data.begin(), data.end()); // 如果需要稳定性}// 只需要前几个元素时std::partial_sort(data.begin(), data.begin() + 10, data.end());// 只需要第k个元素时std::nth_element(data.begin(), data.begin() + 50, data.end());
}

避免不必要的拷贝

void avoid_unnecessary_copies() {std::vector<std::string> strings = {"apple", "banana", "cherry"};// 不好：创建临时stringstd::sort(strings.begin(), strings.end());// 更好：使用引用避免拷贝std::sort(strings.begin(), strings.end(),[](const std::string& a, const std::string& b) {return a.length() < b.length();});// 使用移动语义 (C++11)std::vector<std::string> sorted_strings;std::move(strings.begin(), strings.end(), std::back_inserter(sorted_strings));
}