C++核心编程（动态类型转换，STL，Lanmda）

一. 类型转换

二. STL

1. 容器

1.1 Vector（常用）

1.1.1 概述 

• 特性：

  • 动态数组： 想象成一个会自动变长变短的数组。起始在内存中是连续存储的。

  • 随机访问： 通过[]运算符或at()方法，可以瞬间（O(1)复杂度） 访问任意位置的元素（就像数组下标）。这是它最大的优势之一。

  • 尾部高效： 在末尾添加(push_back)或删除(pop_back)元素非常快（通常是O(1)，除非需要重新分配内存）。

  • 中间/头部低效： 在中间或开头插入(insert)或删除(erase)元素比较慢（O(n)复杂度），因为它需要移动后面的所有元素来保持连续性。

  • 内存管理： 当添加元素导致当前内存不够时，vector会自动申请一块更大的新内存（通常是翻倍），把旧元素复制过去，再释放旧内存。这个操作(reallocation)开销较大，所以如果你预先知道大概要存多少元素，用reserve()提前分配足够空间能显著提升性能。

  • 大小可变： size()告诉你当前有多少元素，capacity()告诉你当前分配的内存最多能放多少元素（size <= capacity）。

• 适用场景： 当你需要像数组一样快速随机访问元素，并且主要在尾部添加/删除元素时（例如：存储游戏中的得分列表、读取文件内容到内存、实现动态数组需求）。

• 新手注意： 在中间插入删除很慢！频繁操作中间位置考虑list或deque。预先reserve()可以避免频繁内存分配，提升性能。

1.1.2 vector概念与特性

`vector` 是C++标准模板库（STL）中的一个动态数组容器，它可以存储相同类型的元素，并且可以根据需要自动调整大小。以下是 `vector` 的一些主要特性：

1. **动态大小**：`vector` 能够在运行时动态地增加或减少其大小。当插入新元素时，如果当前容量不足，`vector` 会自动分配更大的内存空间，并将原有的元素复制到新的内存区域。

2. **随机访问**：可以使用下标运算符 `[]` 或 `at()` 函数对 `vector` 中的元素进行随机访问，时间复杂度为O(1)。

3. **连续存储**：`vector` 中的元素在内存中是连续存储的，这使得它可以高效地进行随机访问，但在插入或删除元素时可能需要移动大量元素，时间复杂度较高。

4. **元素类型支持**：`vector` 是一个模板类，可以存储任意类型的元素，包括内置类型（如 `int`、`double` 等）和自定义类型。

5. **迭代器支持**：`vector` 提供了多种迭代器，如 `begin()`、`end()` 等，可以方便地遍历容器中的元素。

1.1.3 vector容器的构造函数：

初始化列表构造函数：vector(initializer_list<T> init); 
    该构造函数允许使用初始化列表来创建vector容器，方便一次性初始化多个元素。例如：vector<int> v = {1, 2, 3}; 会创建一个包含元素1、2、3的vector容器。

 1. 默认构造函数：创建一个空的vector容器，模板参数T指定容器中元素的类型。
    例如：vector<int> v;  会创建一个存储int类型元素的空容器。

 2. 范围构造函数：vector(v.begin(), v.end()); 
    该构造函数会将另一个vector容器v中从开始迭代器，v.begin()到结束迭代器v.end()之间的所有元素拷贝到新创建的vector容器中。

 3. 填充构造函数：vector(n, elem); 
    此构造函数会创建一个包含n个元素的vector容器，每个元素的值都为elem。

 4. 拷贝构造函数：vector(const vector &vec); 
    用于创建一个新的vector容器，该容器是另一个vector容器vec的副本。

1.1.4 vector的赋值操作： 

1. 重载等号操作符：vector& operator = (const vector &vec); 
    允许将一个vector容器赋值给另一个vector容器，会将vec中的元素复制到当前容器中。

 2. assign(beg, end); 
    将从迭代器beg到end之间的元素拷贝赋值给当前vector容器。

 3. assign(n, elem); 
    将n个值为elem的元素赋值给当前vector容器。

1.1.5 vector容器和大小的操作：

1. empty(); 
    用于判断vector容器是否为空，如果容器中没有元素，返回true，否则返回false。

2. capacity(); 
    返回vector容器当前的容量，即容器在不重新分配内存的情况下可以存储的元素数量。

3. size(); 
    返回vector容器中当前实际存储的元素个数。
4. resize(int num); 
    重新指定容器的长度为num。如果num大于当前容器的大小，容器会变长，新增的位置会用默认值填充；
    如果num小于当前容器的大小，容器会变短，末尾超出容器长度的元素会被删除。

5. resize(int num, elem); 
    同样是重新指定容器的长度为num，但当容器变长时，新增的位置会用elem值填充。

1.1.6 vector的插入和删除操作：

1. push_back(elem); 
   在vector容器的尾部插入一个新元素elem。

2. pop_back(); 
   删除vector容器的最后一个元素。
3. insert(const_iterator pos, elem); 

   在迭代器pos指向的位置插入一个元素elem。
4. insert(const_iterator pos, int count, elem); 
   在迭代器pos指向的位置插入count个元素elem。

5. erase(const_iterator pos); 
   删除迭代器pos指向的元素。

6. erase(const_iterator start, const_iterator end); 
   删除从迭代器start到end之间的所有元素。

7. clear(); 
   删除vector容器中的所有元素，使容器变为空容器。

1.1.7 vector容器中的数据存取操作：

1. at(int idx); 
   返回索引idx所指的数据，如果索引越界，会抛出out_of_range异常。

2. operator[]; 
   同样返回索引idx所指的数据，但不进行越界检查，使用时需要确保索引在有效范围内。

3. front(); 
   返回vector容器中第一个数据元素。
4. back(); 
   返回vector容器中最后一个数据元素。

1.1.8 vector互换容器操作：

swap(vec); 
   将当前vector容器与另一个vector容器vec中的元素进行互换。

1.1.9 vector容器预留空间操作：

reserve(int len); 
   容器预留len个元素长度的内存空间，但这些预留位置不会被初始化，元素也不可访问。
   这样做可以减少在插入元素时频繁进行内存重新分配的开销。

 1.1.10 代码示例：

#include <iostream>
#include <vector>
using namespace std;void VectorApiTest()
{// vector的数据结构我还没看，注意！// 初始化 vector 的不同方式,由此可知，vector支持重载初始化std::vector<int> myVector;     // 创建一个存储整数的空 vectorstd::vector<int> myVector1(5); // 创建一个包含 5 个整数的 vector，每个值都为默认值（0）vector<int> myVector2(5, 10);  // 创建一个包含 5 个整数的 vector，每个值都为 10// 插入vector尾部// 添加的是第一个初始化的值myVector.push_back(1); // 将整数 7 添加到 vector 的末尾myVector.push_back(2);myVector1.push_back(1);myVector1.push_back(2);myVector2.push_back(1);myVector2.push_back(2);// 访问元素--通过下标来访问--与数组一致// 注意：vector 不支持负索引，即 myVector[-1] 是无效的// 注意：vector 不支持越界访问，即 myVector[10] 是无效的int x = myVector[0];      // 获取第一个元素int y = myVector.at(1);   // 获取第二个元素int x1 = myVector1[0];    // 获取第一个元素int y1 = myVector1.at(1); // 获取第二个元素int x2 = myVector2[0];    // 获取第一个元素int y2 = myVector2.at(1); // 获取第二个元素// 获取vector大小int size = myVector.size(); // 获取 vector 中的元素数量int size1 = myVector1.size();int size2 = myVector2.size();// 迭代vector,由于size（）代表其长度for (int i = 0; i < myVector.size(); i++){std::cout << myVector[i] << " "; // 输出 vector 中的元素}std::cout << std::endl;for (int i = 0; i < myVector1.size(); i++){std::cout << myVector1[i] << " "; // 输出 vector 中的元素}std::cout << std::endl;for (int i = 0; i < myVector2.size(); i++){std::cout << myVector2[i] << " "; // 输出 vector 中的元素}// vector的动态扩容机制// 当 vector 中的元素数量超过其容量时，vector 会自动重新分配更大的内存空间来存储元素。// 这种机制使得 vector 可以动态地调整大小，而不需要手动管理内存。扩容倍数为2倍// 注意：vector 的动态扩容机制可能会导致性能下降，特别是当 vector 中的元素数量很大时。// 因此，在使用 vector 时，应该尽量避免频繁的插入和删除操作，以避免性能问题。// 可以使用 reserve() 函数来预先分配内存空间，以避免频繁的扩容操作。// 可以使用 shrink_to_fit() 函数来释放未使用的内存空间，以减少内存占用。// 写出vector的扩容机制的代码，当vector的size等于capacity时，vector会重新分配内存空间，指针重新指向新的内存空间
}
void VectorApiTest2()
{// 使用构造函数初始化vectorstd::vector<int> myVector = {1, 2, 3, 4, 5};// 使用深拷贝构造函数std::vector<int> myVector1;// assign()函数的作用是将一个vector的内容赋值给另一个vector，属于深拷贝myVector1.assign(myVector.begin(), myVector.end());for (int i = 0; i < myVector1.size(); i++){std::cout << myVector1[i];}std::cout << std::endl;for (int i = 0; i < myVector.size(); i++){std::cout << myVector[i];}
}
void VectorApiTest3()
{// 调用vector类内置函数std::vector<int> myVector = {1, 2, 3, 4, 5};
}int main(int argc, char const *argv[])
{VectorApiTest(); // 创建对象，调用构造函数，初始化对象，调用析构函数，销毁对象std::cout << std::endl;VectorApiTest2(); // 深拷贝对象return 0;
}

1.2 String（不想说了）

1.2.1 概述

• 特性：

  • 专门存储字符序列： 本质上就是一个专门用来存放char（或wchar_t等）的vector！它继承了vector的核心特性（动态数组、连续内存、随机访问、尾部高效）。

  • 丰富的字符串操作： 提供了大量方便的方法来处理文本：连接(+, append)、查找(find, rfind)、子串(substr)、比较(compare)、替换(replace)、插入(insert)、删除(erase)、大小写转换等。这些是普通vector没有的。

  • C风格兼容： 可以用c_str()方法获得一个指向内部字符数组的const char*指针，以便与旧的C库函数交互。

  • 自动内存管理： 和vector一样，自动处理内存的分配和释放。

• 适用场景： 所有需要存储和操作文本（字符串）的地方。它是C++处理字符串的首选工具。

• 新手注意： 把它当作一个功能超级强大的字符数组或字符串类型来用就行了。它的底层就是vector，所以随机访问快，尾部操作快，中间操作慢的特点同样适用。

1.3 Deque(序列式容器)

1.3.1 概述

• 特性：

  • 双端队列： 全称是“Double-Ended Queue”。想象成可以在头尾两端都进行高效操作的动态数组。

  • 头尾高效： 在头部(push_front, pop_front) 和尾部(push_back, pop_back) 添加/删除元素都非常快（O(1)复杂度）。这是它相对于vector的最大优势。

  • 随机访问： 支持通过[]或at()进行随机访问，速度接近vector（也是O(1)，但常数时间可能略慢一点点）。

  • 中间低效： 在中间插入(insert)或删除(erase)元素比较慢（O(n)复杂度），需要移动元素。

  • 内存结构： 内部通常由多块连续的内存块（称为“缓冲区”或“块”）和一个中央索引（称为“映射器”）组成。元素不是存储在单一连续内存块中，而是分布在多个连续块里。这使得它在头尾增长时不需要像vector那样大规模复制整个数组（只需分配新块或释放空块）。

• 适用场景： 需要频繁在头部和尾部添加/删除元素，并且还需要随机访问时（例如：实现一个排队系统，人可以从队尾加入，也可以从队头离开；实现一个滑动窗口算法）。

• 新手注意： 如果你主要在头尾操作，选它比vector好。内存不是完全连续的（虽然分段连续），这点和vector不同。随机访问速度依然很快，不用担心。

1.3.2 deque容器的构造函数：

    初始化列表构造函数：deque(initializer_list<T> init); 
    该构造函数允许使用初始化列表来创建deque容器，方便一次性初始化多个元素。例如：deque<int> d = {1, 2, 3}; 会创建一个包含元素1、2、3的deque容器。
1. 默认构造函数：创建一个空的deque容器，模板参数T指定容器中元素的类型。
    例如：deque<int> d;  会创建一个存储int类型元素的空容器。

2. 范围构造函数：deque(d.begin(), d.end()); 
    该构造函数会将另一个deque容器d中从开始迭代器d.begin()到结束迭代器d.end()之间的所有元素拷贝到新创建的deque容器中。

3. 填充构造函数：deque(n, elem); 
    此构造函数会创建一个包含n个元素的deque容器，每个元素的值都为elem。

4. 拷贝构造函数：deque(const deque &d); 
    用于创建一个新的deque容器，该容器是另一个deque容器d的副本。

1.3.3 deque的赋值操作：

1. 重载等号操作符：deque& operator = (const deque &d); 
    允许将一个deque容器赋值给另一个deque容器，会将d中的元素复制到当前容器中。

2. assign(beg, end); 
    将从迭代器beg到end之间的元素拷贝赋值给当前deque容器。

3. assign(n, elem); 
    将n个值为elem的元素赋值给当前deque容器。

1.3.4 deque容器和大小的操作：

1. empty(); 
    用于判断deque容器是否为空，如果容器中没有元素，返回true，否则返回false。

2. size(); 
    返回deque容器中当前实际存储的元素个数。
    
3. resize(int num); 
    重新指定容器的长度为num。如果num大于当前容器的大小，容器会变长，新增的位置会用默认值填充；
    如果num小于当前容器的大小，容器会变短，末尾超出容器长度的元素会被删除。

4. resize(int num, elem); 
    同样是重新指定容器的长度为num，但当容器变长时，新增的位置会用elem值填充。

1.3.5 deque的插入和删除操作：

1. push_back(elem); 
   在deque容器的尾部插入一个新元素elem。

2. push_front(elem); 
   在deque容器的头部插入一个新元素elem。

3. pop_back(); 
   删除deque容器的最后一个元素。

4. pop_front(); 
   删除deque容器的第一个元素。

5. insert(const_iterator pos, elem); 
   在迭代器pos指向的位置插入一个元素elem。

6. insert(const_iterator pos, int count, elem); 
   在迭代器pos指向的位置插入count个元素elem。

7. erase(const_iterator pos); 
   删除迭代器pos指向的元素。

8. erase(const_iterator start, const_iterator end); 
   删除从迭代器start到end之间的所有元素。

9. clear(); 
   删除deque容器中的所有元素，使容器变为空容器。

1.3.6 deque容器中的数据存取操作：

1. at(int idx); 
   返回索引idx所指的数据，如果索引越界，会抛出out_of_range异常。

2. operator[]; 
   同样返回索引idx所指的数据，但不进行越界检查，使用时需要确保索引在有效范围内。

3. front(); 
   返回deque容器中第一个数据元素。
4. back(); 
   返回deque容器中最后一个数据元素。

1.3.7 deque互换容器操作：

swap(d); 
   将当前deque容器与另一个deque容器d中的元素进行互换。

 1.3.8 代码示例：

#include <iostream>
#include <deque>
using namespace std;void printDeque(const deque<int> &d)
{for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{deque<int> d1;for (int i = 0; i < 10; i++){d1.push_back(i);}printDeque(d1);deque<int> d2(d1.begin(), d1.end());printDeque(d2);deque<int> d3(5, 100);printDeque(d3);deque<int> d4(d3);printDeque(d4);return 0;
}

1.4 Stack 容器适配器 - 通常基于deque/list/vector)

1.4.1 概述

• 特性：

  • 后进先出 (LIFO)： 像一摞盘子。你只能访问或拿走最顶上的那个盘子（最后放上去的）。

  • 限制接口： 只允许在栈顶进行操作：

    • push(): 将元素压入栈顶 (入栈)

    • pop(): 移除栈顶元素 (出栈) - 注意：它不返回被移除的元素值！ 需要先用top()获取。

    • top(): 获取栈顶元素的引用（不删除）

    • empty(): 检查栈是否为空

    • size(): 获取栈中元素数量

  • 底层容器： stack本身不管理内存，它是对底层容器（默认是deque，也可以用list或vector）的封装，只暴露栈的操作接口。底层容器决定了内存管理的细节。

• 适用场景： 任何需要LIFO行为的地方：函数调用栈、表达式求值（如括号匹配）、撤销操作(Undo)、深度优先搜索(DFS)。

• 新手注意： pop()不返回值！先用top()拿到值，再pop()移除它。理解LIFO思想是关键。它只是个适配器，底层可以是deque、list或vector（默认deque性能最好）。

1.4.2 stack容器的构造函数：

### 默认构造函数：stack<T, Container = deque<T>> s; 
    创建一个空的stack容器，模板参数T指定容器中元素的类型，Container指定底层容器的类型，默认使用deque。
    例如：stack<int> s;  会创建一个存储int类型元素的空栈，底层使用deque。

1.4.3 stack的赋值操作：

由于 `stack` 没有提供直接的赋值操作符重载，但可以通过创建新的 `stack` 并复制元素来实现赋值。

1.4.4 stack容器和大小的操作：

1. empty(); 
    用于判断stack容器是否为空，如果栈中没有元素，返回true，否则返回false。

2. size(); 
    返回stack容器中当前实际存储的元素个数。

1.4.5 stack的插入和删除操作：

1. push(elem); 
   在stack容器的栈顶插入一个新元素elem。

2. pop(); 
   删除stack容器的栈顶元素。

1.4.6 stack容器中的数据存取操作：

1. top(); 
   返回stack容器中栈顶的数据元素，但不删除该元素。

 1.4.7 代码示例

    #include <iostream>#include <stack>using namespace std;void printStack(const stack<int>& s) {stack<int> tmp = s;while (!tmp.empty()) {cout << tmp.top() << " ";tmp.pop();}cout << endl;}int main() {stack<int> s;s.push(1);s.push(2);s.push(3);printStack(s);cout << s.size() << endl;cout << s.top() << endl;s.pop();printStack(s);}

1.5 Queue

1.5.1 概述

• 特性：

  • 先进先出 (FIFO)： 像排队买票。先来的人站在队头，先买到票离开。

  • 限制接口： 操作限定在队尾添加，队头移除：

    • push() / enqueue(): 在队尾添加元素 (入队)

    • pop() / dequeue(): 从队头移除元素 (出队) - 同样不返回移除的元素值！

    • front(): 获取队头元素的引用（不删除）

    • back(): 获取队尾元素的引用（不删除）

    • empty(), size()

  • 底层容器： 需要底层容器支持高效的前端删除(pop_front) 和尾部添加(push_back)。默认是deque（因为头尾操作都高效）。也可以用list（头尾操作也高效）。不能用vector做默认底层容器，因为vector的头部删除(pop_front)效率太低(O(n))！

• 适用场景： 任何需要FIFO行为的地方：消息队列、任务调度、广度优先搜索(BFS)、打印任务队列。

• 新手注意： pop()不返回值！先用front()拿到队头值，再pop()移除它。理解FIFO思想。底层默认是deque，也可以用list，不能用vector。

1.5.2 queue容器的构造函数：

### 默认构造函数：queue<T, Container = deque<T>> q; 
    创建一个空的queue容器，模板参数T指定容器中元素的类型，Container指定底层容器的类型，默认使用deque。
    例如：queue<int> q;  会创建一个存储int类型元素的空队列，底层使用deque。

1.5.3 queue的赋值操作：

由于 `queue` 没有提供直接的赋值操作符重载，但可以通过创建新的 `queue` 并复制元素来实现赋值。

1.5.4 queue容器和大小的操作：

1. empty(); 
    用于判断queue容器是否为空，如果队列中没有元素，返回true，否则返回false。

2. size(); 
    返回queue容器中当前实际存储的元素个数。

1.5.5 queue的插入和删除操作：

1. push(elem); 
   在queue容器的队尾插入一个新元素elem。

2. pop(); 

1.5.6 queue容器中的数据存取操作：

1. front(); 
   返回queue容器中队头的数据元素，但不删除该元素。

2. back(); 
   返回queue容器中队尾的数据元素，但不删除该元素。

1.5.7 代码示例

#include <iostream>
#include <queue>
using namespace std;
void printQueue(const queue<int> &q)
{queue<int> tmp = q;while (!tmp.empty()){cout << tmp.front() << " ";tmp.pop();}cout << endl;
}
int main()
{queue<int> q;q.push(1);q.push(2);q.push(3);printQueue(q);cout << q.size() << endl;cout << q.front() << endl;cout << q.back() << endl;q.pop();printQueue(q);// queue的常用接口// 构造函数queue<int> q1;queue<int> q2(q1);queue<int> q3(5, 100);// 赋值操作queue<int> q4;q4 = q3;// 大小操作cout << q4.size() << endl;// 判空操作cout << q4.empty() << endl;// 入队操作q4.push(100);printQueue(q4);// 出队操作q4.pop();printQueue(q4);// 访问队头元素cout << q4.front() << endl;// 访问队尾元素cout << q4.back() << endl;// 交换操作queue<int> q5;q5.push(1000);q5.push(2000);printQueue(q5);q4.swap(q5);printQueue(q4);printQueue(q5);
}

1.6 List(序列式容器)

1.6.1 概述

• 特性：

  • 双向链表： 想象成一串珍珠项链。每个元素（珍珠）都包含数据和两个指针，分别指向前一个元素和后一个元素。

  • 任意位置高效插入/删除： 在任何位置（包括头部和尾部）插入(insert)或删除(erase)一个元素都非常快（O(1)复杂度），只要你知道位置（迭代器）。因为只需要修改几个指针，不需要移动其他元素。这是它最大的优势！

  • 不支持随机访问： 不能用[]或at()瞬间跳到第n个元素。要访问第n个元素，必须从链表头（或尾）开始一个一个（O(n)复杂度）遍历过去。

  • 额外操作： 提供链表特有的高效操作：

    • splice(): 把另一个链表的一部分（或全部）移动到当前链表的指定位置（只改指针，超快）。

    • merge(): 合并两个已排序链表（高效）。

    • sort(): 链表自身的排序算法（通常比algorithm里的std::sort对链表更高效，因为std::sort需要随机访问）。

    • unique(): 移除连续的重复元素（常与sort()配合使用去重）。

  • 内存开销： 每个元素除了数据本身，还需要额外的空间存储前后指针（通常是两个指针的大小）。

  • 内存不连续： 元素分散在内存各处，对CPU缓存不友好（相比vector, deque）。

• 适用场景： 需要频繁在任意位置（尤其是中间）插入或删除元素，并且不需要随机访问时（例如：实现一个随时可能插入删除中间项的播放列表、实现LRU缓存淘汰算法）。

• 新手注意： 随机访问很慢！遍历用迭代器，别尝试用下标。插入删除快是优势。内存开销比vector大。forward_list是单向链表（只支持向前遍历），开销更小，但功能也少些。

1.6.2 list容器的构造函数：

### 初始化列表构造函数：list(initializer_list<T> init); 
    该构造函数允许使用初始化列表来创建list容器，方便一次性初始化多个元素。例如：list<int> l = {1, 2, 3}; 会创建一个包含元素1、2、3的list容器。
1. 默认构造函数：创建一个空的list容器，模板参数T指定容器中元素的类型。
    例如：list<int> l;  会创建一个存储int类型元素的空容器。

2. 范围构造函数：list(l.begin(), l.end()); 
    该构造函数会将另一个list容器l中从开始迭代器l.begin()到结束迭代器l.end()之间的所有元素拷贝到新创建的list容器中。

3. 填充构造函数：list(n, elem); 
    此构造函数会创建一个包含n个元素的list容器，每个元素的值都为elem。

4. 拷贝构造函数：list(const list &l); 
    用于创建一个新的list容器，该容器是另一个list容器l的副本。

1.6.3 list的赋值操作：

1. 重载等号操作符：list& operator = (const list &l); 
    允许将一个list容器赋值给另一个list容器，会将l中的元素复制到当前容器中。

2. assign(beg, end); 
    将从迭代器beg到end之间的元素拷贝赋值给当前list容器。

3. assign(n, elem); 
    将n个值为elem的元素赋值给当前list容器。

1.6.4 list容器和大小的操作：

1. empty(); 
    用于判断list容器是否为空，如果容器中没有元素，返回true，否则返回false。

2. size(); 
    返回list容器中当前实际存储的元素个数。
    
3. resize(int num); 
    重新指定容器的长度为num。如果num大于当前容器的大小，容器会变长，新增的位置会用默认值填充；
    如果num小于当前容器的大小，容器会变短，末尾超出容器长度的元素会被删除。

4. resize(int num, elem); 
    同样是重新指定容器的长度为num，但当容器变长时，新增的位置会用elem值填充。

1.6.5 list的插入和删除操作：

1. push_back(elem); 
   在list容器的尾部插入一个新元素elem。

2. push_front(elem); 
   在list容器的头部插入一个新元素elem。

3. pop_back(); 
   删除list容器的最后一个元素。

4. pop_front(); 
   删除list容器的第一个元素。

5. insert(const_iterator pos, elem); 
   在迭代器pos指向的位置插入一个元素elem。

6. insert(const_iterator pos, int count, elem); 
   在迭代器pos指向的位置插入count个元素elem。

7. erase(const_iterator pos); 
   删除迭代器pos指向的元素。

8. erase(const_iterator start, const_iterator end); 
   删除从迭代器start到end之间的所有元素。

9. clear(); 
   删除list容器中的所有元素，使容器变为空容器。

1.6.6 list容器中的数据存取操作：

由于 `list` 不支持随机访问，没有 `at()` 和 `operator[]` 操作。可以通过迭代器访问元素。
1. front(); 
   返回list容器中第一个数据元素。
   
2. back(); 
   返回list容器中最后一个数据元素。

1.6.7 list互换容器操作：

swap(l); 
   将当前list容器与另一个list容器l中的元素进行互换。

1.6.8 代码示例 

#include <iostream>
#include <list>
using namespace std;
void printList(const list<int> &l)
{list<int> tmp = l;while (!tmp.empty()){cout << tmp.front() << " ";tmp.pop_front();}cout << endl;
}
int main()
{list<int> l1;for (int i = 0; i < 10; i++){l1.push_back(i);}printList(l1);// 构造函数list<int> l2(l1.begin(), l1.end());printList(l2);// 赋值操作list<int> l3;l3 = l2;printList(l3);// 大小操作cout << l3.size() << endl;// 判空操作cout << l3.empty() << endl;// 插入操作l3.push_back(10);printList(l3);l3.push_front(20);printList(l3);// 删除操作l3.pop_back();printList(l3);l3.pop_front();printList(l3);// 插入操作l3.insert(l3.begin(), 100);printList(l3);// 删除操作l3.erase(l3.begin());printList(l3);// 清空操作l3.clear();printList(l3);// 反转操作l3.reverse();printList(l3);// 排序操作l3.sort();printList(l3);// 合并操作list<int> l4;l4.push_back(100);l4.push_back(200);l4.push_back(300);printList(l4);// 交换操作l3.swap(l4);printList(l3);printList(l4);// 移除操作l3.remove(100);printList(l3);// 拷贝操作list<int> l5(l3);printList(l5);// 赋值操作l5 = l3;printList(l5);// 比较操作cout << (l3 == l5) << endl;cout << (l3 != l5) << endl;cout << (l3 < l5) << endl;cout << (l3 > l5) << endl;cout << (l3 <= l5) << endl;cout << (l3 >= l5) << endl;// 访问操作cout << l3.front() << endl;cout << l3.back() << endl;// 迭代器操作list<int>::iterator it = l3.begin();while (it != l3.end()){cout << *it << " ";it++;}cout << endl;// 反向迭代器操作list<int>::reverse_iterator rit = l3.rbegin();while (rit != l3.rend()){cout << *rit << " ";rit++;}
}

1.7 MultiSet/Set 

1.7.1 概述

• 特性 (Set):

  • 唯一键集合： 存储唯一的Key。每个元素就是键本身(Key = Value)。

  • 自动排序： 元素总是按键(Key)自动升序排序（默认<比较，可自定义比较规则）。你无法控制元素的物理存储顺序。

  • 高效查找： 基于排序，查找(find(), count(), lower_bound(), upper_bound())一个元素的速度非常快（O(log n)复杂度），使用二分查找思想。

  • 插入/删除效率： 插入(insert)和删除(erase)元素也是O(log n)复杂度，因为需要维护排序和树的平衡。

  • 键不可修改： 一旦元素插入，其键值(Key)就不能被直接修改（因为会破坏排序）。要修改，通常需要先删除旧元素，再插入新元素。

• 特性 (MultiSet):

  • 多重键集合： 允许存储多个值相同的元素（多个相同的Key)。

  • 除了允许重复键之外，其他特性（自动排序、高效查找、O(log n)插入删除）与set完全相同。

  • 查找时count(key)可能大于1，equal_range(key)返回一个包含所有该key的迭代器范围。

• 底层结构： 通常实现为红黑树（一种自平衡的二叉搜索树），这保证了操作的O(log n)复杂度。

• 适用场景 (Set): 需要存储唯一值并需要快速查找、自动排序（例如：维护一个不重复的用户ID集合、字典单词集合）。

• 适用场景 (MultiSet): 需要存储可能重复的值并需要快速查找、自动排序（例如：统计成绩，允许有多个相同分数；记录日志时间戳，允许重复时间）。

• 新手注意： 元素自动排序！set里元素唯一，multiset允许重复。查找插入删除都很快(O(log n))。键值不可直接改。理解“键(Key)”就是元素本身。

 1.7.2 

1.7.3 

1.7.4 

1.7.5 

1.7.6 

1.7.7

1.7.8 

1.7.9

1.7.10 

1.8 MultiMap/Map

 1.7.2 

1.7.3 

1.7.4 

1.7.5 

1.7.6 

1.7.7

1.7.8 

1.7.9

1.7.10 

1.8.1 概述

• 特性 (Map):

  • 键值对集合： 存储的元素是pair<const Key, Value>。Key是键，用于查找和排序；Value是与键关联的值。

  • 唯一键： 每个Key在map中必须是唯一的。

  • 按键自动排序： 元素总是按键(Key)自动升序排序（默认<比较，可自定义）。

  • 高效查找： 基于键(Key)进行查找(find(), count(), operator[], at(), lower_bound(), upper_bound())非常快（O(log n)复杂度）。

  • 插入/删除效率： 插入(insert)和删除(erase)也是O(log n)复杂度。

  • 键不可修改： 插入后，元素的键(Key)是const的，不能被修改（会破坏排序）。值(Value)可以修改。

  • operator[]: map[key] 是一个强大的操作：

    • 如果key存在，返回对应Value的引用。

    • 如果key不存在，则自动插入一个pair<key, Value()>（用Value类型的默认构造函数创建新值），然后返回这个新Value的引用。这个特性使得用map计数 (map[key]++) 非常方便，但也容易不小心插入新元素。

  • at(): map.at(key) 会检查key是否存在。存在则返回Value的引用；不存在则抛出std::out_of_range异常。更安全。

• 特性 (MultiMap):

  • 多重键键值对集合： 允许多个元素拥有相同的键(Key)，但它们的值(Value)可以不同（也可以相同）。

  • 除了允许重复键之外，其他特性（按键排序、高效查找、O(log n)插入删除）与map完全相同。

  • 查找时count(key)可能大于1，equal_range(key)返回一个包含所有该key的键值对的迭代器范围。

• 底层结构： 通常也实现为红黑树。

• 适用场景 (Map): 需要建立唯一键(Key)到值(Value) 的映射关系，并需要按键快速查找、自动按键排序（例如：电话簿<姓名, 号码>、学生信息系统<学号, 学生信息>、单词计数器<单词, 出现次数>）。

• 适用场景 (MultiMap): 需要建立键(Key)到值(Value) 的映射关系，且一个键可能对应多个值，并需要按键快速查找、自动按键排序（例如：作者著作索引<作者名, 书名>、日期事件记录<日期, 事件描述>）。

• 新手注意： 存储的是键值对(key-value pair)。map键唯一，multimap键可重复。按键自动排序！查找插入删除都很快(O(log n))。键(Key)不可修改。map[key]会创建新元素，map.at(key)更安全。理解键(Key)和值(Value)的区别。

1.9 总结 

容器	类型	顺序/排序	主要特性	插入/删除效率 (典型)	查找效率 (典型)	随机访问	重复元素	备注
vector	序列式	插入顺序	动态数组，连续内存，尾快，随机访问快	尾: O(1) 中/头: O(n)	O(n)	O(1)	允许	最常用，随机访问首选
string	序列式	插入顺序	字符专用的vector，丰富字符串操作	尾: O(1) 中/头: O(n)	O(n)	O(1)	允许	文本处理核心
deque	序列式	插入顺序	双端队列，头尾操作都快，分段连续内存，随机访问接近vector	头/尾: O(1) 中: O(n)	O(n)	~O(1)	允许	头尾操作频繁时选它
stack	适配器	LIFO (后进先出)	只允许在栈顶操作 (push, pop, top)	O(1) (顶)	-	No	允许	基于deque(默认)/list/vector
queue	适配器	FIFO (先进先出)	只允许队尾加(push)，队头删(pop) (front, back)	O(1) (尾加/头删)	-	No	允许	基于deque(默认)/list
list	序列式	插入顺序	双向链表，任意位置插入删除快，内存不连续	任意位置: O(1) (已知迭代器)	O(n)	No	允许	中间频繁插入删除时选它
set	关联式	按键自动排序	唯一Key集合 (Key=Value)，自动排序，查找快	O(log n)	O(log n)	No	No	唯一键集合，排序，查找
multiset	关联式	按键自动排序	多重Key集合 (Key=Value)，自动排序，查找快	O(log n)	O(log n)	No	允许	可重复键集合，排序，查找
map	关联式	按键自动排序	唯一Key到Value的映射，自动按键排序，按键查找快	O(log n)	O(log n) (by Key)	No	No (Key)	键值对，键唯一，按键排序查找
multimap	关联式	按键自动排序	多重Key到Value的映射，自动按键排序，按键查找快	O(log n)	O(log n) (by Key)	No	允许 (Key)	键值对，键可重复，按键排序查找

2. 算法

2.1 查找算法

2.1.1 概述

STL 查找算法详解
 一、线性查找算法
1. std::find
- 特点 ：通用的查找算法，对容器中的元素逐个进行比较，直至找到目标元素或者遍历完整个容器。不要求容器中的元素有序，实现简单，但在数据量较大时效率较低。
- 底层原理 ：借助迭代器从容器的起始位置开始，逐个访问元素并和目标值进行比较，直到找到匹配元素或者到达容器末尾。
- 分类 ：线性查找算法。
- 使用方法 ：需要包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器以及要查找的目标值。函数返回一个迭代器，若找到目标值，该迭代器指向目标元素；若未找到，则返回结束迭代器。
- 要求 ：容器需提供双向迭代器或者前向迭代器。

2. std::find_if
- 特点 ：能够使用自定义的谓词函数来查找满足特定条件的元素，同样不要求容器元素有序。可根据不同的查找条件灵活使用。
- 底层原理 ：使用迭代器遍历容器，对每个元素调用谓词函数，直到找到使谓词函数返回 true 的元素或者遍历完整个容器。
- 分类 ：线性查找算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器以及一个一元谓词函数。返回一个迭代器，指向第一个使谓词函数返回 true 的元素，若未找到则返回结束迭代器。
- 要求 ：容器需提供双向迭代器或者前向迭代器，谓词函数必须是一元函数。

二、二分查找算法
1. std::binary_search
- 特点 ：要求容器元素已经按照升序排列，通过不断将搜索区间缩小一半来查找目标元素，查找效率较高，时间复杂度为 $O(log n)$。
- 底层原理 ：每次把搜索区间分成两部分，比较中间元素和目标值的大小，依据比较结果缩小搜索区间，直到找到目标元素或者搜索区间为空。
- 分类 ：二分查找算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器以及要查找的目标值。函数返回一个布尔值，表示是否找到目标元素。
- 要求 ：容器元素必须有序，容器需提供随机访问迭代器。

### 2. std::lower_bound
- 特点 ：返回第一个不小于目标值的元素的迭代器，要求容器元素有序。可用于查找满足特定条件的最小元素。
- 底层原理 ：基于二分查找算法，不断缩小搜索区间，最终找到第一个不小于目标值的元素。
- 分类 ：二分查找算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器以及目标值。返回一个迭代器，指向第一个不小于目标值的元素。
- 要求 ：容器元素必须有序，容器需提供随机访问迭代器。

### 3. std::upper_bound
- 特点 ：返回第一个大于目标值的元素的迭代器，要求容器元素有序。可用于查找满足特定条件的最小上界。
- 底层原理 ：基于二分查找算法，不断缩小搜索区间，最终找到第一个大于目标值的元素。
- 分类 ：二分查找算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器以及目标值。返回一个迭代器，指向第一个大于目标值的元素。
- 要求 ：容器元素必须有序，容器需提供随机访问迭代器。

## 三、其他查找算法
### 1. std::find_end
- 特点 ：在一个序列中查找最后一次出现的子序列，不要求序列有序。适用于查找子序列最后一次出现的位置。
- 底层原理 ：从主序列的末尾开始，逐个检查是否存在与子序列匹配的部分。
- 分类 ：子序列查找算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入主序列的起始迭代器、结束迭代器，以及子序列的起始迭代器、结束迭代器。返回一个迭代器，指向主序列中最后一次出现子序列的起始位置。
- 要求 ：主序列和子序列需提供双向迭代器。

### 2. std::find_first_of
- 特点 ：在一个序列中查找第一个出现在另一个序列中的元素，不要求序列有序。可用于查找两个序列中的公共元素。
- 底层原理 ：遍历第一个序列，对于每个元素，检查是否存在于第二个序列中。
- 分类 ：元素查找算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，以及第二个序列的起始迭代器、结束迭代器。返回一个迭代器，指向第一个序列中第一个出现在第二个序列中的元素。
- 要求 ：两个序列需提供前向迭代器。

 2.1.2 代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void printVector(vector<int> &v)
{for (int data : v){cout << data << "\t";}cout << endl;
}int MultiNum(int num)
{return num * 10;
}
int main()
{vector<int> v = {10, 20, 30, 40, 50};// 常用查找算法/*find-在容器中查找指定数据需要指定条件  find(v.begin(), v.end(), 30)1. v.begin()迭代器起始 v.end()迭代器结束2 .30是要查找的数据*/vector<int>::iterator it = find(v.begin(), v.end(), 30);if (it == v.end()){cout << "没有找到" << endl;}else{cout << "找到了" << endl;}/*find_if1. 查找指定条件的数据2. 查找条件需要自己定义3. 函数对象 仿函数  函数指针  匿名函数  都可以作为find_if的第三个参数find_if(v.begin(), v.end(), [](int num));*/vector<int>::iterator it2 = find_if(v.begin(), v.end(), [](int num){ return num > 20; });if (it2 == v.end()){cout << "没有找到" << endl;}else{cout << "找到了" << endl;}/*
adjacent_find1.查找相邻重复元素2.返回相邻元素的第一个位置的迭代器3.如果找不到返回最后一个元素的迭代器，即v.end()adjacent_find(v.begin(), v.end())*/vector<int>::iterator it3 = adjacent_find(v.begin(), v.end());if (it3 == v.end()){cout << "没有找到" << endl;}else{cout << "找到了" << endl;}/*
binary_search1.二分查找法2.在有序序列中查找指定元素3.找到返回true，否则返回false4.底层是利用lower_bound实现的5.binary_search(v.begin(), v.end(), 30) 30为要查找的元素*/bool ret = binary_search(v.begin(), v.end(), 30);if (ret){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}/*count1.统计元素个数2.count(v.begin(), v.end(), 30) 30为要查找的元素3.返回为找找的元素个数，返回值为int*/int num = count(v.begin(), v.end(), 30);cout << "num = " << num << endl;// count_ifint num2 = count_if(v.begin(), v.end(), [](int num){ return num > 20; });cout << "num2 = " << num2 << endl;/*transform1.搬运容器到另一个容器中2.需要指定源容器和目标容器的起始迭代器3.需要指定要执行的操作4.需要指定容器的大小*/vector<int> v2;v2.resize(v.size());transform(v.begin(), v.end(), v2.begin(), MultiNum);printVector(v2);/*for_each1.遍历容器2.需要指定容器的起始迭代器和结束迭代器3.需要指定要执行的操作4.不需要指定容器的大小for_each(v2.begin(), v2.end(), [](int &num);[*/for_each(v2.begin(), v2.end(), [](int &num){ num *= 10; });printVector(v2);printVector(v2);
}

2.2 遍历算法

2.2.1 概述

# STL 遍历算法详解
## 一、基本遍历算法
### 1. std::for_each
- 特点 ：对容器中的每个元素应用指定的函数，不修改容器中的元素，适用于对容器元素进行批量处理。实现简单，使用灵活。
- 底层原理 ：借助迭代器遍历容器，对每个元素调用指定的函数对象。
- 分类 ：基本遍历算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器以及一个函数对象。函数返回传入的函数对象。
- 要求 ：容器需提供前向迭代器。

### 2. std::transform
- 特点 ：可以将一个或两个序列中的元素通过指定的操作转换到另一个序列中，支持原地转换和目标序列转换。可用于对容器元素进行批量修改。
- 底层原理 ：使用迭代器遍历源序列，对每个元素应用指定的操作，并将结果存储到目标序列中。
- 分类 ：转换遍历算法。
- 使用方法 ：包含 <algorithm> 头文件，对于单序列转换，调用时传入源序列的起始迭代器、结束迭代器，目标序列的起始迭代器以及一个一元操作函数；对于双序列转换，还需传入第二个源序列的起始迭代器和一个二元操作函数。返回指向目标序列中最后一个被写入元素的下一个位置的迭代器。
- 要求 ：源序列需提供前向迭代器，目标序列需提供可写的前向迭代器。

## 二、并行遍历算法（C++17 及以后）
### 1. std::for_each_n
- 特点 ：对序列中的前 n 个元素应用指定的函数，可用于部分遍历。
- 底层原理 ：使用迭代器遍历序列的前 n 个元素，对每个元素调用指定的函数对象。
- 分类 ：部分遍历算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、元素数量 n 以及一个函数对象。函数返回传入的函数对象。
- 要求 ：序列需提供前向迭代器。

### 2. std::for_each_parallel
- 特点 ：并行地对容器中的每个元素应用指定的函数，可提高处理效率，适用于大规模数据处理。
- 底层原理 ：将容器划分为多个子区间，并行地对每个子区间中的元素调用指定的函数对象。
- 分类 ：并行遍历算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入执行策略（如 `std::execution::par`）、容器的起始迭代器、结束迭代器以及一个函数对象。函数返回传入的函数对象。
- 要求 ：容器需提供随机访问迭代器，函数对象需是可并行执行的。

2.2.2 代码示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
遍历算法for_each: 遍历容器transform: 搬运容器到另一个容器中
*/
int main()
{vector<int> v = {10, 20, 30, 40, 50};// 使用lambda表达式遍历容器for_each(v.begin(), v.end(), [](int value) -> void{ cout << value << "\t"; });cout << endl;// 使用transform搬运容器到另一个容器中vector<int> v2;v2.resize(v.size()); // 需要提前使用v1的容量开辟空间。transform(v.begin(), v.end(), v2.begin(), [](int value) -> int{ return value; });for_each(v2.begin(), v2.end(), [](int value) -> void{ cout << value << "\t"; });
}

2.3 排序算法

2.3.1 概述

# STL 排序算法详解
## 一、基本排序算法
### 1. std::sort
- 特点 ：对容器中的元素进行升序排序，使用快速排序、堆排序和插入排序的混合算法，平均时间复杂度为 $O(n log n)$。排序效率较高，但会改变元素的相对顺序。
- 底层原理 ：根据数据规模和分布情况，选择合适的排序算法。当数据规模较小时，使用插入排序；当数据规模较大时，使用快速排序；当快速排序的递归深度过大时，使用堆排序。
- 分类 ：基本排序算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器，也可以传入一个比较函数来指定排序规则。函数无返回值。
- 要求 ：容器需提供随机访问迭代器。

### 2. std::stable_sort
- 特点 ：对容器中的元素进行升序排序，保证相等元素的相对顺序不变，使用归并排序算法，时间复杂度为 $O(n log n)$。排序效率较高，但空间复杂度较高。
- 底层原理 ：将容器划分为多个子区间，对每个子区间进行排序，然后将排序好的子区间合并。
- 分类 ：稳定排序算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、结束迭代器，也可以传入一个比较函数来指定排序规则。函数无返回值。
- 要求 ：容器需提供随机访问迭代器。

## 二、部分排序算法
### 1. std::partial_sort
- 特点 ：对容器中的前 n 个元素进行排序，将最小的 n 个元素放到容器的前 n 个位置，时间复杂度为 $O(n log n)$。适用于只需要部分排序的场景。
- 底层原理 ：使用堆排序算法，维护一个大小为 n 的最大堆，遍历容器中的元素，将比堆顶元素小的元素替换堆顶元素，并调整堆。
- 分类 ：部分排序算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、指向第 n 个元素的迭代器、结束迭代器，也可以传入一个比较函数来指定排序规则。函数无返回值。
- 要求 ：容器需提供随机访问迭代器。

### 2. std::nth_element
- 特点 ：将容器中的第 n 个元素放到其排序后的位置，使得该位置之前的元素都小于等于它，之后的元素都大于等于它，时间复杂度为 $O(n)$。适用于查找第 n 小的元素。
- 底层原理 ：使用快速选择算法，通过不断划分区间，缩小查找范围，直到找到第 n 个元素。
- 分类 ：选择排序算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入容器的起始迭代器、指向第 n 个元素的迭代器、结束迭代器，也可以传入一个比较函数来指定排序规则。函数无返回值。
- 要求 ：容器需提供随机访问迭代器。

2.3.2 代码示例

2.4 拷贝与替换算法

2.4.1 概述

# STL 拷贝与替换算法详解
## 一、拷贝算法
### 1. std::copy
- 特点 ：将一个序列中的元素复制到另一个序列中，不改变源序列中的元素，适用于序列元素的复制。
- 底层原理 ：使用迭代器遍历源序列，将每个元素复制到目标序列中。
- 分类 ：基本拷贝算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入源序列的起始迭代器、结束迭代器，以及目标序列的起始迭代器。返回指向目标序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：源序列需提供输入迭代器，目标序列需提供输出迭代器。

### 2. std::copy_n
- 特点 ：将源序列中的前 n 个元素复制到目标序列中，适用于部分元素的复制。
- 底层原理 ：使用迭代器遍历源序列的前 n 个元素，将每个元素复制到目标序列中。
- 分类 ：部分拷贝算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入源序列的起始迭代器、元素数量 n 以及目标序列的起始迭代器。返回指向目标序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：源序列需提供输入迭代器，目标序列需提供输出迭代器。

## 二、替换算法
### 1. std::replace
- 特点 ：将序列中的所有等于指定值的元素替换为另一个值，适用于批量替换元素。
- 底层原理 ：使用迭代器遍历序列，将所有等于指定值的元素替换为另一个值。
- 分类 ：基本替换算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、结束迭代器、要被替换的值以及替换后的值。函数无返回值。
- 要求 ：序列需提供前向迭代器。

### 2. std::replace_if
- 特点 ：将序列中所有满足指定谓词条件的元素替换为另一个值，可根据自定义条件进行替换。
- 底层原理 ：使用迭代器遍历序列，对每个元素调用谓词函数，将满足条件的元素替换为另一个值。
- 分类 ：条件替换算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、结束迭代器、一个一元谓词函数以及替换后的值。函数无返回值。
- 要求 ：序列需提供前向迭代器，谓词函数必须是一元函数。

2.4.2 代码示例

2.5 算术生成算法

2.5.1 概述

# STL 算术生成算法详解
## 一、求和算法
### 1. std::accumulate
- 特点 ：对序列中的元素进行累加操作，也可以自定义二元操作进行元素的累积计算。适用于计算序列元素的总和或其他累积结果。
- 底层原理 ：使用迭代器遍历序列，将初始值与序列中的元素依次进行二元操作，最终得到累积结果。
- 分类 ：基本求和算法。
- 使用方法 ：包含 <numeric> 头文件，调用时传入序列的起始迭代器、结束迭代器以及初始值，也可以传入一个自定义的二元操作函数。返回累积结果。
- 要求 ：序列需提供输入迭代器，二元操作函数必须是二元函数。

### 2. std::partial_sum
- 特点 ：计算序列中元素的部分和，将结果存储在另一个序列中。可以自定义二元操作进行部分累积计算。
- 底层原理 ：使用迭代器遍历序列，依次计算并存储部分和，每一步的结果是当前元素与之前所有元素的累积和（或自定义操作结果）。
- 分类 ：部分求和算法。
- 使用方法 ：包含 <numeric> 头文件，调用时传入输入序列的起始迭代器、结束迭代器以及输出序列的起始迭代器，也可以传入一个自定义的二元操作函数。返回输出序列的结束迭代器。
- 要求 ：输入序列需提供输入迭代器，输出序列需提供输出迭代器，二元操作函数必须是二元函数。

### 3. std::adjacent_difference
- 特点 ：计算序列中相邻元素的差值（或自定义二元操作结果），将结果存储在另一个序列中。
- 底层原理 ：使用迭代器遍历序列，计算相邻元素的差值（或自定义操作结果）并存储在输出序列中。
- 分类 ：相邻元素操作算法。
- 使用方法 ：包含 <numeric> 头文件，调用时传入输入序列的起始迭代器、结束迭代器以及输出序列的起始迭代器，也可以传入一个自定义的二元操作函数。返回输出序列的结束迭代器。
- 要求 ：输入序列需提供输入迭代器，输出序列需提供输出迭代器，二元操作函数必须是二元函数。

### 4. std::inner_product
- 特点 ：计算两个序列的内积（对应元素相乘后累加），也可以自定义二元操作进行计算。
- 底层原理 ：使用迭代器同时遍历两个序列，将对应元素进行自定义操作（默认是相乘），然后将结果进行累积操作（默认是相加）。
- 分类 ：序列内积算法。
- 使用方法 ：包含 <numeric> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，第二个序列的起始迭代器，初始值，还可以传入两个自定义的二元操作函数（分别用于元素操作和累积操作）。返回累积结果。
- 要求 ：序列需提供输入迭代器，自定义的二元操作函数必须是二元函数。

## 二、填充算法
### 1. std::fill
- 特点 ：将序列中的所有元素设置为指定的值，适用于批量初始化序列元素。
- 底层原理 ：使用迭代器遍历序列，将每个元素赋值为指定的值。
- 分类 ：基本填充算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、结束迭代器以及要填充的值。函数无返回值。
- 要求 ：序列需提供前向迭代器。

### 2. std::fill_n
- 特点 ：将序列中的前 n 个元素设置为指定的值，适用于部分初始化序列元素。
- 底层原理 ：使用迭代器遍历序列的前 n 个元素，将每个元素赋值为指定的值。
- 分类 ：部分填充算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、元素数量 n 以及要填充的值。函数无返回值。
- 要求 ：序列需提供前向迭代器。

### 3. std::generate
- 特点 ：将序列中的每个元素设置为一个生成器函数的返回值，适用于批量生成有规律的元素。
- 底层原理 ：使用迭代器遍历序列，对每个元素调用生成器函数，并将返回值赋值给该元素。
- 分类 ：生成填充算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、结束迭代器以及一个生成器函数。函数无返回值。
- 要求 ：序列需提供前向迭代器，生成器函数必须是无参数的可调用对象。

### 4. std::generate_n
- 特点 ：将序列中的前 n 个元素设置为一个生成器函数的返回值，适用于部分生成有规律的元素。
- 底层原理 ：使用迭代器遍历序列的前 n 个元素，对每个元素调用生成器函数，并将返回值赋值给该元素。
- 分类 ：部分生成填充算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入序列的起始迭代器、元素数量 n 以及一个生成器函数。函数无返回值。
- 要求 ：序列需提供前向迭代器，生成器函数必须是无参数的可调用对象。

## 三、随机数生成算法
### 1. std::iota
- 特点 ：将序列中的元素依次设置为从指定值开始的连续递增的值，适用于生成连续数值序列。
- 底层原理 ：使用迭代器遍历序列，将每个元素依次赋值为从指定值开始的连续递增的值。
- 分类 ：序列生成算法。
- 使用方法 ：包含 <numeric> 头文件，调用时传入序列的起始迭代器、结束迭代器以及起始值。函数无返回值。
- 要求 ：序列需提供前向迭代器。

## 四、其他算术相关算法
### 1. std::sample
- 特点 ：从输入序列中随机选取指定数量的元素，存储到输出序列中。适用于随机抽样场景。
- 底层原理 ：使用随机数生成器，通过蓄水池抽样算法等方式从输入序列中随机选取元素。
- 分类 ：随机抽样算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入输入序列的起始迭代器、结束迭代器，输出序列的起始迭代器、结束迭代器，抽样数量以及一个随机数生成器。返回指向输出序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：输入序列需提供输入迭代器，输出序列需提供输出迭代器，随机数生成器需满足相应要求。

2.5.2 代码示例

2.6 集合算法

2.6.1 概述

# STL 集合算法详解
## 一、集合合并算法
### 1. std::merge
- 特点 ：将两个有序序列合并为一个有序序列，不改变原序列中的元素，适用于合并有序序列。
- 底层原理 ：使用迭代器遍历两个有序序列，比较元素大小，将较小的元素依次放入目标序列中。
- 分类 ：基本合并算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，第二个序列的起始迭代器、结束迭代器，以及目标序列的起始迭代器，也可以传入一个比较函数来指定排序规则。返回指向目标序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：两个原序列需提供输入迭代器，目标序列需提供输出迭代器，且两个原序列必须是有序的。

## 二、集合查找算法
### 1. std::includes
- 特点 ：判断一个有序序列是否包含另一个有序序列中的所有元素，适用于判断集合的包含关系。
- 底层原理 ：使用迭代器遍历两个有序序列，比较元素大小，判断是否所有元素都被包含。
- 分类 ：集合包含判断算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，第二个序列的起始迭代器、结束迭代器，也可以传入一个比较函数来指定排序规则。返回一个布尔值，表示第一个序列是否包含第二个序列中的所有元素。
- 要求 ：两个序列需提供输入迭代器，且两个序列必须是有序的。

## 三、集合运算算法
### 1. std::set_difference
- 特点 ：计算两个有序序列的差集，即存在于第一个序列但不存在于第二个序列中的元素组成的集合，适用于计算集合的差集。
- 底层原理 ：使用迭代器遍历两个有序序列，比较元素大小，将只存在于第一个序列中的元素放入目标序列中。
- 分类 ：集合差集算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，第二个序列的起始迭代器、结束迭代器，以及目标序列的起始迭代器，也可以传入一个比较函数来指定排序规则。返回指向目标序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：两个原序列需提供输入迭代器，目标序列需提供输出迭代器，且两个原序列必须是有序的。

### 2. std::set_intersection
- 特点 ：计算两个有序序列的交集，即同时存在于两个序列中的元素组成的集合，适用于计算集合的交集。
- 底层原理 ：使用迭代器遍历两个有序序列，比较元素大小，将同时存在于两个序列中的元素放入目标序列中。
- 分类 ：集合交集算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，第二个序列的起始迭代器、结束迭代器，以及目标序列的起始迭代器，也可以传入一个比较函数来指定排序规则。返回指向目标序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：两个原序列需提供输入迭代器，目标序列需提供输出迭代器，且两个原序列必须是有序的。

### 3. std::set_symmetric_difference
- 特点 ：计算两个有序序列的对称差集，即存在于第一个序列但不存在于第二个序列，或者存在于第二个序列但不存在于第一个序列中的元素组成的集合，适用于计算集合的对称差集。
- 底层原理 ：使用迭代器遍历两个有序序列，比较元素大小，将只存在于一个序列中的元素放入目标序列中。
- 分类 ：集合对称差集算法。
- 使用方法 ：包含 <algorithm> 头文件，调用时传入第一个序列的起始迭代器、结束迭代器，第二个序列的起始迭代器、结束迭代器，以及目标序列的起始迭代器，也可以传入一个比较函数来指定排序规则。返回指向目标序列中最后一个被复制元素的下一个位置的迭代器。
- 要求 ：两个原序列需提供输入迭代器，目标序列需提供输出迭代器，且两个原序列必须是有序的。

2.6.2 代码示例

3. 迭代器

1. 迭代器是什么？为什么需要它？

• 是什么？ 迭代器是一个对象（或者行为类似指针的对象），它指向容器中的一个元素（或尾后位置）。你可以把它想象成一个智能指针，封装了对容器内部元素的访问细节。

• 为什么需要？

  • 统一访问接口： STL的核心思想是泛型编程。算法（如 sort, find, copy）需要能处理任何容器。如果没有迭代器，每个算法都要为 vector, list, map 等写不同的版本。迭代器提供了访问容器元素的标准方法，算法只需要操作迭代器，就能作用于不同的容器。

  • 遍历容器： 这是迭代器最基本、最常用的功能。无论容器内部是连续内存(vector)、链表(list)还是树(map)，你都可以用相似的 ++it, *it 语法遍历所有元素。

  • 访问元素： 通过解引用迭代器(*it)，你可以读取或修改它指向的元素的值。

  • 连接容器与算法： 几乎所有STL算法都通过迭代器范围 [begin, end) 来操作容器。begin 指向第一个元素，end 指向最后一个元素之后的位置（尾后迭代器）。这个左闭右开区间 [begin, end) 是STL的标准约定。

2. 迭代器的核心操作（基础语法）

迭代器的行为模仿指针，支持以下基本操作：

• *it：解引用。获取迭代器 it 指向元素的引用。可以读值也可以赋值修改值。

• it->member： 如果迭代器指向的是一个结构体或类对象，可以用 -> 直接访问其成员（等价于 (*it).member）。

• ++it / it++：前缀/后缀递增。将迭代器移动到指向容器中的下一个元素。（最常见操作）

• --it / it--：前缀/后缀递减（仅适用于双向和随机访问迭代器）。将迭代器移动到指向容器中的上一个元素。

• it1 == it2 / it1 != it2：比较。判断两个迭代器是否指向同一个元素（或是否都是尾后迭代器）。通常用 != 作为循环结束条件。

• =：赋值。将一个迭代器的值赋给另一个迭代器（让它们指向同一个位置）。

3. 如何获取迭代器？

每个STL容器都提供了成员函数来获取迭代器：

• .begin()： 返回指向容器第一个元素的迭代器。

• .end()： 返回指向容器最后一个元素之后位置的迭代器（尾后迭代器）。重要！end() 指向的不是最后一个元素本身！ 它标志着容器的结束。

• .cbegin() / .cend()： 返回 const 迭代器。通过它们只能读取元素，不能修改元素（类似指向常量的指针 const T*）。

• .rbegin() / .rend()： 返回反向迭代器。rbegin() 指向最后一个元素，rend() 指向第一个元素之前的位置。++ 操作会使反向迭代器向前（即容器顺序的逆序）移动。

• .crbegin() / .crend()： 返回 const 反向迭代器。

4. 迭代器分类（类别/能力）

不是所有迭代器的能力都一样！STL根据迭代器支持的操作，将它们分为5类（能力从弱到强）：

1. 输入迭代器 (Input Iterator):

   • 能力： 只能单向向前移动 (++it)，只能读取元素 (*it)，且只能读取一次（就像一个只读的单向数据流，如从键盘读取）。

   • 不支持： 写操作、递减(--)、随机访问。

   • 示例： 读取文件流 (istream_iterator)。

2. 输出迭代器 (Output Iterator):

   • 能力： 只能单向向前移动 (++it)，只能写入元素 (*it = value)，且通常只能写入一次（就像一个只写的单向数据流，如写入屏幕）。

   • 不支持： 读操作（解引用只能出现在赋值左边）、递减(--)、随机访问。

   • 示例： 写入文件流 (ostream_iterator)。

3. 前向迭代器 (Forward Iterator):

   • 能力： 单向向前移动 (++it)，可以多次读写同一个元素 (*it)。它组合了输入和输出迭代器的功能，并且支持多次读写。

   • 不支持： 递减(--)、随机访问。

   • 示例： forward_list (单向链表) 的迭代器。

4. 双向迭代器 (Bidirectional Iterator):

   • 能力： 在前向迭代器基础上，增加了向后移动 (--it / it--) 的能力。

   • 不支持： 随机访问（不能瞬间跳到任意位置）。

   • 示例： list, set, multiset, map, multimap, deque 的迭代器。deque 虽然支持随机访问，但其迭代器通常被归类为双向以满足最低要求（实际实现可能更强）。

5. 随机访问迭代器 (Random Access Iterator):

   • 能力： 在双向迭代器基础上，提供了完整的指针算术运算能力，就像操作普通数组指针一样：

     • 瞬间跳到任意位置：it + n, it - n, it += n, it -= n

     • 计算距离：it1 - it2

     • 下标访问：it[n] (等价于 *(it + n))

     • 比较大小：it1 < it2, it1 > it2, it1 <= it2, it1 >= it2

   • 示例： vector, deque, array, string 的迭代器。原生数组指针也是随机访问迭代器。

为什么分类重要？

• 算法选择： STL算法会指定它需要什么类别的迭代器。例如：

  • sort 需要随机访问迭代器（因为它需要快速跳到中间元素）。

  • list::sort 是 list 的成员函数，它只需要双向迭代器（链表不能随机访问）。

  • find 只需要输入迭代器（它顺序查找）。

• 效率提示： 随机访问迭代器支持的操作通常是最快的（O(1)），而前向或双向迭代器的移动是线性的（O(n)）。

5. 迭代器失效：一个极其重要的陷阱！

• 问题： 当你对容器进行修改操作（如插入、删除）时，指向容器元素的迭代器可能会变得无效！继续使用这些失效的迭代器会导致未定义行为（程序崩溃、数据错误等）。

• 原因： 修改操作可能改变容器的内部结构：

  • vector/string： 在中间或头部 insert/erase，或者 push_back 导致内存重分配 (reallocation)，会使所有指向该容器元素的迭代器、引用和指针失效！重分配后，即使尾后迭代器 .end() 也失效。

  • deque： 在中间 insert/erase 会使所有迭代器失效。在头尾 push/pop 通常只使指向被操作元素的迭代器失效（但 push 可能导致内存块分配，使所有迭代器失效，具体实现相关）。

  • list/forward_list/关联容器(set, map等)： insert 操作不会使任何现有迭代器失效。erase 操作仅使指向被删除元素的迭代器失效。指向其他元素的迭代器仍然有效。

• 如何避免？

  1. 修改后更新： 在对容器进行修改操作（尤其是 insert, erase, push_back/pop_back 可能引发重分配时）之后，如果需要继续使用迭代器，重新获取迭代器（如 it = vec.begin();）。

  2. 使用返回值： erase 操作通常会返回一个迭代器，指向被删除元素之后的位置。利用这个返回值更新你的循环迭代器：

for (auto it = myList.begin(); it != myList.end(); /* 这里不写 ++it */) {if (condition(*it)) {it = myList.erase(it); // erase 返回下一个有效迭代器} else {++it;}
}

• 1. 警惕循环内修改： 在遍历容器（特别是 vector, deque, string）的循环中修改容器（插入/删除）要格外小心，很容易导致迭代器失效。优先考虑使用上述 erase 返回值的模式。

  2. 使用算法： 尽可能使用 remove_if 配合 erase (擦除-移除惯用法) 来删除元素，或使用 C++11 的范围 for 循环（但其内部也是迭代器，修改容器同样会导致迭代器失效！范围 for 中一般不应修改容器结构）。

6. 迭代器与范围 for 循环 (C++11)

C++11 引入的范围 for 循环 (for (auto element : container)) 是遍历容器的简洁语法糖。底层就是使用迭代器实现的！ 编译器会自动将其展开为类似下面的代码：

{auto && __range = container; // 获取容器引用auto __begin = __range.begin(); // 获取起始迭代器auto __end = __range.end();   // 获取尾后迭代器for (; __begin != __end; ++__begin) {auto element = *__begin; // 解引用迭代器得到元素 (注意这里是拷贝!)// 循环体}
}

• 优点： 语法极其简洁清晰，不易出错（只要不在循环体内修改容器结构导致迭代器失效）。

• 注意：

  • element 默认是容器元素的拷贝。如果想避免拷贝，使用引用 for (auto &element : container)。如果元素不可修改，使用 const 引用 for (const auto &element : container)。

  • 在范围 for 循环体内，绝对不要对正在遍历的容器进行添加或删除元素的操作！ 这会直接导致底层迭代器失效，引发未定义行为。如果需要修改容器结构，请使用显式的迭代器循环和上述 erase 返回值的技巧。

7. 总结：

• 迭代器是通用指针： 它是访问和遍历所有STL容器的标准方式。

• 核心操作： *it, it->member, ++it, --it (部分), it1 == it2, it1 != it2。

• 获取方式： .begin(), .end(), .cbegin(), .cend(), .rbegin(), .rend()。

• 分类重要： 理解5类迭代器（输入、输出、前向、双向、随机访问）及其能力差异，这决定了哪些算法能用。

• 失效陷阱： 时刻警惕修改容器（插入、删除、可能导致重分配的push_back）导致的迭代器失效！这是STL编程中最常见的错误来源之一。修改后及时重新获取迭代器或使用 erase 的返回值。

• 优先用范围 for： 对于简单的遍历，优先使用范围 for 循环，语法简洁不易错（但同样要避免在循环内修改容器结构）。

• auto 是好帮手： 声明迭代器时多用 auto (如 auto it = vec.begin();)，省去冗长的类型书写。

• 比较用 !=： 循环条件判断一般用 it != container.end()，而不是 <（只有随机访问迭代器才支持 <）。

• 实践出真知： 多写代码，尝试用迭代器遍历不同的容器 (vector, list, map)，使用不同的算法 (find, sort - 注意 sort 需要随机访问)，体会迭代器的用法和失效的场景。

4. 仿函数

5. 适配器

1.适配器概述

使用场景：当一个函数有三个参数，你想传入四个参数，这时候，就可以使用适配器

2. 适配器

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;// 修改函数名，避免与标准库函数冲突
bool isEqual(int a, int b)
{return a == b;
}int main()
{vector<int> v = {10, 20, 30, 40, 50};// 正确使用 bind 绑定器，将二元谓词转换为一元谓词auto it = bind(isEqual, placeholders::_1, 10);// 修改变量名，避免命名冲突auto result = find_if(v.begin(), v.end(), it);if (result != v.end()){cout << "找到值了" << endl;}else{// 修正拼写错误cout << "无值" << endl;}return 0;
}

3. 成员函数适配器

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>// 重载小括号的类，被称为函数对象（仿函数）
class Demo
{
public:int id;Demo(int id = 0) : id(id){this->id = id;}void PrintData(int value){std::cout << this->id * value << std::endl;}
};int main()
{std::vector<Demo> v;v.push_back(Demo(1));v.push_back(Demo(2));v.push_back(Demo(3));v.push_back(Demo(4));v.push_back(Demo(5));auto res = std::bind(Demo::PrintData, std::placeholders::_1, 10);for_each(v.begin(), v.end(), res);return 0;
}

4. 函数对象适配器

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>// 重载小括号的类，被称为函数对象（仿函数）
class Demo
{
public:void operator()(int value, int num) const{value *= num; // value = value * num;std::cout << value << "\t";}
};int main()
{std::vector<int> v = {10, 20, 30, 40, 50};// 修正语法错误，添加分号auto res = std::bind(Demo(), std::placeholders::_1, 10);std::for_each(v.begin(), v.end(), res);std::cout << std::endl;return 0;
}

6. 空间配置器（无）

三. Lanmda（c++11新特性）

1. 概述

Lambda表达式是现代C++在C ++ 11和更高版本中的一个新的语法糖 ，在C++11、C++14、C++17和C++20中Lambda表达的内容还在不断更新。 lambda表达式（也称为lambda函数）是在调用或作为函数参数传递的位置处定义匿名函数对象的便捷方法。通常，lambda用于封装传递给算法或异步方法的几行代码 。本文主要介绍Lambda的工作原理以及使用方法。

2. 捕获列表

捕获列表用于指定拉姆达表达式可以访问的外部变量。捕获列表有以下几种形式：

• []：不捕获任何变量。

• [var]：按值捕获变量var。

• [&var]：按引用捕获变量var。

• [=]：按值捕获所有外部变量。

• [&]：按引用捕获所有外部变量。

• [this]：按值捕获当前的this指针。

5. 代码示例： 

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;void test()
{// lambda表达式,其实就是匿函数/*[](){};[]: 捕获列表,空的即为不捕获任何变量[]: 捕获外部变量,可以捕获局部变量,也可以捕获全局变量,也可以捕获this指针[=]: 捕获外部变量,以值的方式捕获,不可以修改外部变量[&]: 捕获外部变量,以引用的方式捕获,可以修改外部变量外部的定义为lambda表达式以外的()：参数列表{}: 函数体;: 函数结尾*/auto add = [](int a, int b) -> int{return a + b;};cout << add(10, 20) << endl;
}//& 捕获外部变量,以引用的方式捕获,可以修改外部变量
void test1()
{int a = 10;int b = 20;auto add = [&](int x = 50, int y = 100) -> int{a = 100;b = 200;return x + y;};cout << add() << endl;
}//= 捕获外部变量,以值的方式捕获,不可以修改外部变量
void test3()
{int a = 10;int b = 20;auto add = [=](int x = 50, int y = 100) -> int{// a = 100; // 错误,不能修改外部变量// b = 200; // 错误,不能修改外部变量return x + y;};
}// 使用lambda遍历容器
void test4()
{vector<int> v = {10, 20, 30, 40, 50};// 使用lambda表达式,遍历容器for_each(v.begin(), v.end(), [](int data) -> void{ cout << data << "\t"; });
}// 使用lambda表达式利用transform把值赋予v2
void test5()
{vector<int> v = {10, 20, 30, 40, 50};vector<int> v2;// 必须要先resize,否则会报错，resize作用是为v2开辟空间v2.resize(v.size());// 使用lambda表达式,遍历容器transform(v.begin(), v.end(), v2.begin(), [](int value) -> int{ return value; });for_each(v2.begin(), v2.end(), [](int value) -> void{ cout << value << "\t"; });
}int main(int argc, char const *argv[])
{test5();return 0;
}