【C++】C++基础记录（二）

02 Jul 2025 in 博客目录

本文记录了我学习C++的一些基础条目知识

本文是C++扫盲的第二篇记录，从STL标准模板往后的一些进阶内容。

前面的相关文章：

C++基础记录

【算法刷题】C++常见容器使用集合

STL容器

STL 顺序容器 如下所示。

• std::vector：操作与动态数组一样，在最后插入数据；可将 vector 视为书架，您可在一端添加和拿走图书。
• std::deque：与 std::vector 类似，但允许在开头插入或删除元素。
• std::list：操作与双向链表一样。可将它视为链条，对象被连接在一起，您可在任何位置添加或删除对象。
• std::forward_list：类似于 std::list，但是单向链表，只能沿一个方向遍历。

STL 提供的 关联容器 如下所示。

• std::set：存储各不相同的值，在插入时进行排序；容器的复杂度为对数。
• std::unordered_set：存储各不相同的值，在插入时进行排序；容器的复杂度为常数。这种容器是 C++11 新增的。
• std::map：存储键-值对，并根据唯一的键排序；容器的复杂度为对数。
• std::unordered_map：存储键-值对，并根据唯一的键排序；容器的复杂度为对数。这种容器是C++11 新增的。
• std::multiset：与 set 类似，但允许存储多个值相同的项，即值不需要是唯一的。
• std::unordered_multiset：与 unordered_set 类似，但允许存储多个值相同的项，即值不需要是唯一的。这种容器是 C++11 新增的。
• std::multimap：与 map 类似，但不要求键是唯一的。
• std::unordered_multimap：与 unordered_map 类似，但不要求键是唯一的。这种容器是 C++11新增的。

容器适配器（Container Adapter） 是顺序容器和关联容器的变种，其功能有限，用于满足特定的需 求。主要的适配器类如下所示。

• std::stack：以 LIFO（后进先出）的方式存储元素，让您能够在栈顶插入（压入）和删除（弹出）元素。
• std::queue：以 FIFO（先进先出）的方式存储元素，让您能够删除最先插入的元素。
• std::priority_queue：以特定顺序存储元素，因为优先级最高的元素总是位于队列开头。

迭代器

在C++中，迭代器（Iterator） 是一种通用概念，它提供了一种访问容器（如数组、列表、树等）中元素的方式，而无需暴露容器的底层实现细节。你可以把它想象成一个“智能指针”，它指向容器中的某个元素，并且可以向前或向后移动来遍历容器中的所有元素。

迭代器的主要作用就是将算法和容器分离。这样，你可以编写通用的算法（如排序、查找），这些算法可以应用于任何支持迭代器的容器，而不需要为每一种容器类型（如 std::vector 或 std::list）重复编写相同的代码。

迭代器的核心功能

一个典型的迭代器通常会提供以下操作：

• 解引用操作符 (*)：获取迭代器当前指向的元素。
• 自增操作符 (++)：将迭代器移动到下一个元素。
• 相等/不相等比较操作符 (==, !=)：判断两个迭代器是否指向同一个位置。
• 自减操作符 (--)：将迭代器移动到上一个元素（仅限部分类型）。

---

STL 迭代器

STL (Standard Template Library) 迭代器 是 C++ 标准库中定义的一组特定的迭代器，它们是STL容器和算法之间的桥梁。

STL迭代器不是一个单一的类，而是一组概念和接口的集合。它们被分为五种主要类型，每种类型都有不同的功能，可以用于不同的场景：

1. 输入迭代器 (Input Iterator)
   • 用途： 只能向前遍历容器一次，用于读取数据。
   • 例子： 输入流迭代器 (std::istream_iterator)。
2. 输出迭代器 (Output Iterator)
   • 用途： 只能向前遍历容器一次，用于写入数据。
   • 例子： 输出流迭代器 (std::ostream_iterator)。
3. 前向迭代器 (Forward Iterator)
   • 用途： 只能向前遍历容器，可以遍历多次。
   • 例子： std::forward_list 的迭代器。
4. 双向迭代器 (Bidirectional Iterator)
   • 用途： 可以向前和向后遍历容器。
   • 例子： std::list 和 std::set 的迭代器。
5. 随机访问迭代器 (Random Access Iterator)
   • 用途： 功能最强大，可以像指针一样进行任意位置的跳转。支持+, -, []等操作。
   • 例子： std::vector, std::string, std::deque 和 C 风格数组的迭代器。

为什么 STL 迭代器如此重要？

STL 迭代器的存在使得 STL 算法库非常强大和灵活。例如，std::sort 算法要求其参数是随机访问迭代器，因为它需要随机访问元素以进行高效的排序。而 std::find 算法只需要输入迭代器，因为它只需要从头到尾遍历一次即可。

总结来说，C++ 迭代器是一个通用的抽象概念，而 STL 迭代器是这个概念在 C++ 标准库中的具体实现，它们是连接 STL 容器和算法的通用接口，是 C++ 泛型编程的基石。

STL算法

查找、排序和反转等都是标准的编程需求，不应让程序员重复实现这样的功能。因此 STL 以 STL 算法的方式提供这些函数，通过结合使用这些函数和迭代器，程序员可对容器执行一些最常见的操作。 最常用的 STL 算法如下所示。

• std::find：在集合中查找值。
• std::find_if：根据用户指定的谓词在集合中查找值。
• std::reverse：反转集合中元素的排列顺序。
• std::remove_if：根据用户定义的谓词将元素从集合中删除。
• std::transform：使用用户定义的变换函数对容器中的元素进行变换。 这些算法都是 std 命名空间中的模板函数，要使用它们，必须包含标准头文件<algorithm>。

举例从vector中查找元素及其下标

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

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // 查找元素
    int value_to_find = 30;
    auto it = std::find(vec.begin(), vec.end(), value_to_find);

    if (it != vec.end()) {
        std::cout << "Found value: " << *it << std::endl;
        // 获取下标
        int index = std::distance(vec.begin(), it);
        std::cout << "Index of value: " << index << std::endl;
    } else {
        std::cout << "Value not found." << std::endl;
    }

    return 0;
}

在 C++ 标准库中，std::distance是一个定义在 <iterator> 头文件中的函数模板，用于计算两个迭代器之间的距离。它主要用于确定从一个迭代器到另一个迭代器之间有多少个元素。

对比

字符串使用演进

C++中字符串的使用经历了从C风格字符串到C++标准库字符串类的演进，主要包括以下几个阶段：

1. C风格字符串（C-Style Strings）：
   • 这是最早的字符串表示方式，使用字符数组和空字符（'\0'）来表示字符串的结束。
   • 例如：char str[] = "Hello, World!";
   • 缺点：容易出现缓冲区溢出、内存管理复杂、操作不便等问题。
   • 优点：兼容性好，与C语言库函数兼容。

C++支持动态分配内存，使用new和delete运算符可以在运行时分配和释放内存。

比如使用 char * dynamicName = new char[arrayLen] 来定义一个动态分配的字符数组，其中 arrayLen 是一个整数，用于指定动态分配的字符数组的长度。

然而，如果要在运行阶段改变数组的长度，必须首先释放以前分 配给它的内存，再重新分配内存来存储数据。

如果将 char*用作类的成员属性，情况将更复杂。将对象赋给另一个对象时，如果编写正确的复制构造函数和赋值运算符，两个对象将包含同一个指针的拷贝，该指针指向相同的缓冲区。其结果是，两个对象的字符串指针存储的地址相同，指向同一个内存单元。其中一个对象被销毁时，另一个对象中的指针将非法，让应用程序面临崩溃的危险。

1. C++标准库字符串类（std::string）：
   • 这是C++标准库提供的字符串类，使用起来更加方便和安全。
   • 例如：std::string str = "Hello, World!";
   • 优点：自动管理内存、提供丰富的操作方法、支持字符串拼接、比较等。
   • 缺点：与C风格字符串相比，性能较低。

string实例化和复制

string 类提供了很多重载的构造函数，因此可以多种方式进行实例化和初始化。例如，可使用常量字符串初始化 STL string 对象或将常量字符串赋给 STL std::string 对象：

const char* constCStyleString = "Hello String!";
std::string strFromConst (constCStyleString);

或：

std::string strFromConst = constCStyleString;
// 上述代码与下面的代码类似：
std::string str2 ("Hello String!"); 

同样，可使用一个 string 对象来初始化另一个：

std::string str2Copy (str2);

可让 string 的构造函数只接受输入字符串的前 n 个字符：

// Initialize a string to the first 5 characters of another
std::string strPartialCopy (constCStyleString, 5);

还可这样初始化 string 对象，即使其包含指定数量的特定字符：

// Initialize a string object to contain 10 'a's
std::string strRepeatChars (10, 'a'); 

string元素访问

第一种：使用[]运算符

std::string str = "Hello, World!";
char ch = str[7]; // ch now holds 'W'
// 遍历
for (size_t i = 0; i < str.size(); ++i) {
    std::cout << str[i] << ' ';
}

这种方式来访问string内容时，需要注意的是，访问的下标必须在字符串的有效范围内，否则会导致未定义行为。

第二种：使用迭代器

std::string str = "Hello, World!";
// 遍历
for (std::string::iterator it = str.begin(); it != str.end(); ++it) {
    std::cout << *it << ' ';
}

这种方式更加灵活，可以方便地进行各种操作，如插入、删除等。迭代器很重要，因为很多 string 成员函数都以迭代器的方式返回其结果。

拼接string

可以使用+运算符或append方法来拼接字符串。

std::string str1 = "Hello, ";
std::string str2 = "World!";
std::string str3 = str1 + str2; // str3 now holds "Hello, World!"

std::string str1 = "Hello, ";
std::string str2 = "World!";
str1.append(str2); // str1 now holds "Hello, World!"

string中字符和子字符串的查找

可以使用find方法来查找字符或子字符串。

std::string str = "Hello, World!";
size_t pos = str.find("World"); // pos now holds 7
if (pos != std::string::npos) {
    std::cout << "Found at position: " << pos << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

find方法返回子字符串首次出现的位置，如果未找到则返回std::string::npos。

在C++的 std::string 类中， string::npos 是一个静态成员常量，它的值是 string::size_type 类型所能表示的最大值。它的主要作用是作为一个 “未找到”（”not found”）的标志。当你在使用 std::string 的查找方法（如 find() 或 rfind()）时，如果子字符串或字符没有被找到，这些方法就会返回 string::npos。

如果string中有不止一个的子字符串，find方法只会返回第一个子字符串的位置。如果要查找所有子字符串的位置，需要使用循环来实现。

std::string str = "Hello, World! World!";
size_t pos = str.find("World");
while (pos != std::string::npos) {
    std::cout << "Found at position: " << pos << std::endl;
    pos = str.find("World", pos + 1);
}

string的截断

如果是获取子字符串，可以使用substr方法来截取字符串的一部分。

std::string str = "Hello, World!";
std::string subStr = str.substr(7, 5); // subStr now holds "World"

如果是直接对原字符串操作，可以使用 erase() 方法来删除指定位置的字符或子字符串。

STL string 类提供了 erase()函数，具有以下用途。

• 在给定偏移位置和字符数时删除指定数目的字符。

string sampleStr ("Hello String! Wake up to a beautiful day!");
sampleStr.erase (13, 28); // Hello String!

• 在给定指向字符的迭代器时删除该字符。

sampleStr.erase (iCharS); // iterator points to a specific character

• 在给定由两个迭代器指定的范围时删除该范围内的字符。

sampleStr.erase (sampleStr.begin (), sampleStr.end ()); // erase from begin

例如：

std::string str = "Hello, World!";
// 删除从位置 7 开始的 5 个字符
str.erase(7, 5); // str now holds "Hello!"

删除某一个字符：

std::string str = "Hello, World!";
auto iChar = str.find('W');
if (iChar != std::string::npos) {
    str.erase(iChar, 1); // 删除第一个 'W'
}
std::cout << str << std::endl; // 输出 "Hello, orld!"

删除指定迭代器范围内的所有字符：

std::string str = "Hello, World!";
auto iStart = str.begin() + 7;
auto iEnd = str.begin() + 12;
str.erase(iStart, iEnd); // str now holds "Hello!"

字符串反转

有时需要反转字符串的内容。假设要判断用户输入的字符串是否为回文，方法之一是将其反转，再与原来的字符串进行比较。反转 STL string 很容易，只需使用泛型算法 std::reverse() 即可：

string sampleStr ("Hello String! We will reverse you!");
reverse (sampleStr.begin (), sampleStr.end ());

std::reverse()算法根据两个输入参数指定的边界反转边界内的内容。在这里，两个边界分别是 string 对象的开头和末尾，因此整个字符串都被反转。只要提供合适的输入参数，也可将字符串的一部分反转。注意，边界不能超过 end()。

大小写转换

要对字符串进行大小写转换，可使用算法 std::transform() 来实现。

下面这个例子，将用户输入的字符串分别进行大写和小写转换：

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

int main() {
    std::string input;
    std::cout << "Enter a string: ";
    std::getline(std::cin, input);

    // 转换为大写
    std::string upperCaseStr = input;
    std::transform(upperCaseStr.begin(), upperCaseStr.end(), upperCaseStr.begin(), ::toupper);

    // 转换为小写
    std::string lowerCaseStr = input;
    std::transform(lowerCaseStr.begin(), lowerCaseStr.end(), lowerCaseStr.begin(), ::tolower);

    std::cout << "Uppercase: " << upperCaseStr << std::endl;
    std::cout << "Lowercase: " << lowerCaseStr << std::endl;

    return 0;
}

C++14引入的操作符””s

C++14引入了一个新的操作符""s，它可以直接将字符串字面量转换为std::string类型。这使得字符串的创建更加简洁和直观。

如果字面量字符串中包含了空字符，需要使用""s操作符来创建字符串。

#include <iostream>
#include <string>

using namespace std;

int main() {
    string str1("Hello \0 World!");
    cout << str1 << endl;
    // 输出：Hello

    string str2("Hello \0 World!"s);
    cout << str2 << endl;
    // 输出：Hello \0 World!

    return 0;
}

vector

vector 是一个模板类，提供了动态数组的通用功能，具有如下特点：

• 在数组末尾添加元素所需的时间是固定的，即在末尾插入元素的所需时间不随数组大小而异，在末尾删除元素也如此；
• 在数组中间添加或删除元素所需的时间与该元素后面的元素个数成正比；
• 存储的元素数是动态的，而 vector 类负责管理内存。

vector实例化

vector是一个模板类，需要指定元素类型。

vector<int> dynamicIntArray;
vector<string> stringArray;
vector<double> doubleArray;

声明const迭代器可以这样写：

vector<int>::const_iterator iter = dynamicIntArray.cbegin();

如果需要可修改值的迭代器，需要使用iterator而不是const_iterator。

vector<int>::iterator iter = dynamicIntArray.begin();

其他实例化方式：

// 初始化列表
vector<int> dynamicIntArray = {1, 2, 3, 4, 5};

// 指定大小，默认初始化元素为0
vector<int> dynamicIntArray(5);

// 指定大小，指定初始化元素，内部元素均为50
vector<int> dynamicIntArray(5, 50);

// 通过另一个vector初始化
vector<int> dynamicIntArray2(dynamicIntArray);

// 通过迭代器，使用另一个数组的一部分来初始化
vector<int> dynamicIntArray3(dynamicIntArray.begin(), dynamicIntArray.begin() + 3);

vector使用 push_back() 添加元素 和 pop_back() 删除元素

添加元素：

vector<int> dynamicIntArray;
dynamicIntArray.push_back(10);
dynamicIntArray.push_back(20);
dynamicIntArray.push_back(30);

// size() 函数返回vector中元素的个数
for (int i = 0; i < dynamicIntArray.size(); i++)
{
    cout << dynamicIntArray[i] << endl;
}

使用 pop_back() 将元素从 vector 中删除所需的时间是固定的，即不随 vector 存储的元素个数而异。例如：

dynamicIntArray.pop_back(); // 删除最后一个元素
// 现在 dynamicIntArray 只包含 10 和 20

vector使用 insert() 指定位置插入元素

有好几个重载版本：

1. 插入指定位置，例如在开头插入一个元素：

vector<int> dynamicIntArray = {10, 20, 30};
dynamicIntArray.insert(dynamicIntArray.begin(), 5); // 在开头插入5
// 结果： 5 10 20 30

1. 指定插入位置，元素数量，元素数值（数值相同）：

vector<int> dynamicIntArray = {10, 20, 30};
dynamicIntArray.insert(dynamicIntArray.begin() + 1, 2, 15); // 在第二个位置插入两个15
// 结果： 10 15 15 20 30

1. 将另一个vector插入指定位置：

vector<int> dynamicIntArray1 = {10, 20, 30};
vector<int> dynamicIntArray2 = {40, 50};
dynamicIntArray1.insert(dynamicIntArray1.begin() + 1, dynamicIntArray2.begin(), dynamicIntArray2.end());
// 结果： 10 40 50 20 30

vector使用数组语法访问元素

可以使用数组语法来访问 vector 中的元素：

vector<int> dynamicIntArray = {10, 20, 30};
cout << dynamicIntArray[0] << endl; // 输出 10
cout << dynamicIntArray[1] << endl; // 输出 20
cout << dynamicIntArray[2] << endl; // 输出 30

// 循环
for (int i = 0; i < dynamicIntArray.size(); i++)
{
    cout << dynamicIntArray[i] << endl;
}

vector使用at()访问元素

at() 方法提供了边界检查，如果访问越界会抛出异常。

vector<int> dynamicIntArray = {10, 20, 30};
cout << dynamicIntArray.at(0) << endl; // 输出 10
cout << dynamicIntArray.at(1) << endl; // 输出 20
cout << dynamicIntArray.at(2) << endl; // 输出 30

使用指针语法访问vector元素

可以使用迭代器以类似指针的方式访问vector元素：

vector<int> dynamicIntArray = {10, 20, 30};
vector<int>::const_iterator it = dynamicIntArray.begin();

cout << *it << endl; // 输出 10

// 遍历
for (it = dynamicIntArray.begin(); it != dynamicIntArray.end(); it++)
{
    cout << *it << endl;
}

这里使用了 ++ 运算符移动位置，使用了 * 运算符解引用迭代器。

vector的大小和容量

size() 方法返回 vector 中元素的个数，而 capacity() 方法返回 vector 分配的内存大小（即可以容纳的元素个数）。

vector<int> dynamicIntArray = {10, 20, 30};
cout << "Size: " << dynamicIntArray.size() << endl; // 输出 3
cout << "Capacity: " << dynamicIntArray.capacity() << endl; // 输出 3 或更大

如果 vector 需要频繁地给其内部动态数组重新分配内存，将对性能造成一定的影响。在很大程度上说，这种问题可以通过使用成员函数 reserve (number) 来解决。reserve 函数的功能基本上是增加分配给内部数组的内存，以免频繁地重新分配内存。通过减少重新分配内存的次数，还可减少复制对象的时间，从而提高性能，这取决于存储在 vector 中的对象类型。

vector<int> dynamicIntArray;
dynamicIntArray.reserve(100); // 预留空间以容纳100个元素
dynamicIntArray.push_back(10);
dynamicIntArray.push_back(20);
dynamicIntArray.push_back(30);
cout << "Size: " << dynamicIntArray.size() << endl; // 输出 3
cout << "Capacity: " << dynamicIntArray.capacity() << endl; // 输出 100

deque

deque（double-ended queue）是一个模板类，提供了双端队列的通用功能，除了兼顾 vector 的随机访问能力，还支持在队列的前端进行快速的插入和删除操作。

对比两种结构的底层实现：

vector和deque实现对比

C++ 的 std::vector 和 std::deque 都是标准模板库（STL）中的容器，它们在底层使用了不同的数据结构来存储元素，这导致了它们在性能特性上的差异。

std::vector

std::vector 的底层实现是一个动态数组（Dynamic Array）。它的所有元素都存储在一段连续的内存块中。

• 优点：
  • 快速随机访问： 由于内存连续，通过索引访问任何元素的时间复杂度为 $O(1)$，因为它只需要简单的指针算术运算。
  • 缓存友好： 连续的内存布局使得它在遍历元素时具有很好的 CPU 缓存局部性（cache locality），这通常能带来更好的性能。
• 缺点：
  • 插入和删除开销大： 在数组的中间或开头插入或删除元素需要移动其后的所有元素，时间复杂度为 $O(n)$。
  • 扩容开销： 当动态数组的容量不足时，vector 需要分配一块更大的新内存，将所有旧元素复制到新内存中，然后释放旧内存。这个操作的时间复杂度也是 $O(n)$。

std::deque

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。

为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址。

也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间。

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。

换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

有读者可能会问，如果 map 数组满了怎么办？很简单，再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧的空间。

deque 容器的分段存储结构，提高了在序列两端添加或删除元素的效率，但也使该容器迭代器的底层实现变得更复杂。

deque使用 push_front() 和 push_back()

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> myDeque;

    // 在队列末尾添加元素
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // 在队列前端添加元素
    myDeque.push_front(5);
    myDeque.push_front(1);

    // 当前deque内容: 1 5 10 20 30

    // 删除队列末尾的元素
    myDeque.pop_back();

    // 删除队列前端的元素
    myDeque.pop_front();

    // 修改后的deque内容: 5 10 20

    return 0;
}

deque的两种遍历方式

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> myDeque = {10, 20, 30, 40, 50};

    // 使用索引遍历
    cout << "Using index:" << endl;
    for (size_t i = 0; i < myDeque.size(); ++i) {
        cout << myDeque[i] << " ";
    }
    cout << endl;

    // 使用迭代器遍历
    cout << "Using iterator:" << endl;
    for (deque<int>::iterator it = myDeque.begin(); it != myDeque.end(); ++it) {
        // 使用distance计算偏移位置
        size_t offset = distance(myDeque.begin(), it);
        cout << "Offset: " << offset << ", Value: " << *it << " ";
    }
    cout << endl;

    return 0;
}

size_t 是无符号整数类型，用于表示对象的大小或索引。

清空vector和deque

可以使用 clear() 方法清空 vector 和 deque，可以使用 empty() 来判断容器是否为空的。

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    vector<int> myVector = {1, 2, 3, 4, 5};
    deque<int> myDeque = {10, 20, 30, 40, 50};

    // 清空vector
    myVector.clear();
    if (myVector.empty()) {
        cout << "Vector is empty." << endl;
    } else {
        cout << "Vector is not empty." << endl;
    }

    // 清空deque
    myDeque.clear();
    if (myDeque.empty()) {
        cout << "Deque is empty." << endl;
    } else {
        cout << "Deque is not empty." << endl;
    }

    return 0;
}

应该	不应该
在不知道需要存储多少个元素时，务必使用动态数组 vector 或 deque。	使用固定大小的数组，可能会浪费内存或导致溢出。
请牢记，vector 只能在一端扩容，为此可使用函数 push_back( )。	试图在 vector 的前端插入元素，可能导致性能问题。
请牢记，deque 可在两端扩容，为此可使用函数 push_back( )和 push_front( )。	忘记 deque 的双端特性，导致不必要的复杂操作。
访问动态数组时，不要跨越其边界。	使用索引访问时不检查边界，可能导致未定义行为。
使用迭代器遍历容器，确保代码的通用性和安全性。	直接使用指针操作容器，可能导致错误和不安全的代码。

别忘了，函数 pop_back() 删除集合中的最后一个元素。函数 pop_front() 删除 deque 的第一个元素。

std::list

std::list 在C++中是一个双向链表（doubly linked list），它的核心实现依赖于节点（node）和指针（pointer）。

std::list 通常使用一个 虚拟的头节点（sentinel node） 来简化操作。这个节点不存储任何实际数据，它的作用是：

• next指针永远指向链表的第一个真实节点。
• prev指针永远指向链表的最后一个真实节点。
• 当链表为空时，这个虚拟头节点的next和prev都指向它自己。

使用虚拟头节点的好处是，无论是插入、删除还是遍历，你都不需要对链表为空或在头尾进行特殊判断，所有操作都可以用统一的方式处理，这大大简化了代码逻辑。

要实例化模板 list，需要指定要在其中存储的对象类型，因此实例化 list 的语法类似于下面这样：

std::list<int> linkInts; // list containing integers
std::list<float> listFloats; // list containing floats
std::list<Tuna> listTunas; // list containing objects of type Tuna 

要声明一个指向 list 中元素的迭代器，可以像下面这样做：

std::list<int>::const_iterator elementInList;

如果需要一个这样的迭代器，即可以使用它来修改值或调用非 const 函数，可将 const_iterator 替换为 iterator。

list实例化方式

#include <iostream>
#include <list>
using namespace std;
int main() {
    // 使用初始化列表
    list<int> myList = {1, 2, 3, 4, 5};

    // 使用默认构造函数
    list<string> stringList;

    // 使用指定大小和初始值
    list<double> doubleList(5, 3.14); // 包含5个3.14

    // 使用另一个list初始化
    list<int> anotherList(myList);

    // 使用vector的元素来实例化一个list
    vector<int> vec = {10, 20, 30, 40, 50};
    list<int> listFromVec(vec.cbegin(), vec.cend());

    return 0;
}

begin() 返回一个普通的可读写迭代器 (iterator)。这意味着你可以通过这个迭代器来读取或修改容器中的元素。 cbegin() 返回一个常量迭代器 (const_iterator)。这个迭代器只能用来读取容器中的元素，但不能修改它们。end同理。

您首先实例化了一个 vector，接下来，实例化了一个 list，它包含从 vector 复制而来的元素，这是使用 C++11 新增的 vector::cbegin() 和 vector::cend() 返回的 const 迭代器复制的。该程序清单表明，迭代器让容器的实现彼此独立，其通用功能让您能够使用 vector 中的值实例化 list。

list的开头和末尾插入元素

可以使用 push_front() 方法在 list 的开头插入元素，使用 push_back() 方法在 list 的末尾插入元素。

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> myList;

    // 在开头插入元素
    myList.push_front(10);
    myList.push_front(20);

    // 在末尾插入元素
    myList.push_back(30);
    myList.push_back(40);

    // 输出列表内容
    for (const auto& elem : myList) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}

list中间插入元素

可以使用 insert() 方法在 list 的中间插入元素。

成员函数 list::insert()有 3 种版本。

• 第 1 种版本：

    iterator insert(iterator pos, const T& x)
  

  在这里，insert 函数接受的第 1 个参数是插入位置，第 2 个参数是要插入的值。该函数返回一个迭代器，它指向刚插入到 list 中的元素。

• 第 2 种版本：

    void insert(iterator pos, size_type n, const T& x)
  

  该函数的第 1 个参数是插入位置，最后一个参数是要插入的值，而第 2 个参数是要插入的元素个数。

• 第 3 种版本：

    template <class InputIterator>
    void insert(iterator pos, InputIterator f, InputIterator l)
  

  该重载版本是一个模板函数，除一个位置参数外，它还接受两个输入迭代器，指定要将集合中相应范围内的元素插入到 list 中。注意，输入类型 InputIterator 是一种模板参数化类型，因此可指定任何集合（数组、vector 或另一个 list）的边界。

使用举例：

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> myList = {10, 20, 30, 40};

    // 在第二个位置插入元素
    auto it = myList.begin();
    advance(it, 1); // 移动到第二个位置
    myList.insert(it, 15); // 在第二个位置插入15

    // 此时的列表内容 10 15 20 30 40

    // 在第二个位置插入多个元素
    it = myList.begin();
    advance(it, 1); // 移动到第二个位置
    myList.insert(it, 2, 25); // 在第二个位置插入2个25

    // 此时的列表内容 10 15 25 25 20 30 40

    // 在第二个位置插入数组元素
    int arr[] = {35, 45};
    it = myList.begin();
    advance(it, 1); // 移动到第二个位置
    myList.insert(it, arr, arr + 2); // 在第二个位置插入数组元素

    // 此时的列表内容 10 15 25 25 35 45 20 30 40

    return 0;
}

list删除元素

erase() 方法用于删除 list 中的元素。有两个重载版本：

• 接受一个迭代器参数，删除指定位置的元素；
• 接受两个迭代器参数，删除指定范围内的元素。

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> myList = {10, 20, 30, 40, 50};

    // 删除第二个元素
    auto it = myList.begin();
    advance(it, 1); // 移动到第二个位置
    myList.erase(it); // 删除第二个元素

    // 此时的列表内容 10 30 40 50

    // 删除第二个元素到第四个元素
    it = myList.begin();
    advance(it, 1); // 移动到第二个位置
    auto endIt = myList.begin();
    advance(endIt, 3); // 移动到第四个位置
    myList.erase(it, endIt); // 删除第二个元素到第四个元素

    // 此时的列表内容: 10 50

    for (const auto& elem : myList) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}

需要注意的是， list::erase(first, last) 删除的是 [first, last) 范围内的元素，即包含 first 指向的元素，但不包含 last 指向的元素。这也是为什么第二次删除会移除 30 和 40，而保留 50（在执行第二次删除前的列表中）。因为尾迭代器 endIt 指向的为50这个元素。

区分于it.end() ，it.end() 指向的其实是最后一个元素的下一个位置，所以使用it.end()来删除元素时，会删除到最后一个元素。

list元素反转

可以使用 reverse() 方法来反转 list 中的元素。

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> myList = {10, 20, 30, 40, 50};

    // 反转列表元素
    myList.reverse();

    // 输出列表内容
    for (const auto& elem : myList) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}

list进行排序

可以使用 sort() 方法对 list 中的元素进行排序。 有两个重载方法：

• 单独一个sort()方法，默认以升序排序
• 接受一个比较函数作为参数，以指定的标准排序

#include <iostream>
#include <list>
using namespace std;

bool SortPredicate_Descending(const int& a, const int& b) {
    return a > b; // 降序排序
}

int main() {
    list<int> myList = {40, 10, 30, 20, 50};

    // 默认升序排序
    myList.sort();

    cout << "Sorted in ascending order: ";
    for (const auto& elem : myList) {
        cout << elem << " ";
    }
    cout << endl;

    // 降序排序
    myList.sort(SortPredicate_Descending);

    cout << "Sorted in descending order: ";
    for (const auto& elem : myList) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}

定义了函数 SortPredicate_Descending ，它是一个二元谓词，帮助 list 的 sort() 函数判断一个元素是否比另一个元素小。如果不是，则交换这两个元素的位置。换句话说，您告诉了 list 如何解释小于，就这里而言，小于的含义是第一个参数大于第二个参数。这个谓词仅在第一个值比第二个值大时返回 true。也就是说，使用该谓词时，仅当第一个元素（lsh）的数字值比第二个元素（rsh）大时，sort()才认为第一个元素比第二个元素小。基于这种解释，sort()交换元素的位置，以满足谓词指定的标准。

包含对象的list进行排序

实际使用中，很少使用list来存储int等简单内置类型，而是存储自定义的类型，这是如何排序呢？

答案是采取下面两种方式之一：

• 在 list 包含的对象所属的类中，实现运算符<；
• 提供一个排序二元谓词—一个这样的函数，即接受两个输入值，并返回一个布尔值，指出第一个值是否比第二个值小。

#include <iostream>
#include <list>
#include <string>

using namespace std;


class Tuna {
    int age;
    string name;
public:
    Tuna(int age, string name) {
        this->age = age;
        this->name = name;
    }
    int getAge() const {
        return age;
    }
    string getName() const {
        return name;
    }
    // 实现<操作符函数，实现按照名称name的长度升序排序
    bool operator<(const Tuna& other) const {
        return name.size() < other.name.size();
    }
};

bool SortPredicate_Age(const Tuna& a, const Tuna& b) {
    return a.getAge() < b.getAge(); // 按年龄升序排序
}

int main() {
    list<Tuna> tunaList;
    tunaList.push_back(Tuna(1, "Tunadfbdbn1"));
    tunaList.push_back(Tuna(2, "Tunafbdfbdbfsddvw2"));
    tunaList.push_back(Tuna(3, "Tuna3"));

    // 按年龄排序
    tunaList.sort(SortPredicate_Age);

    cout << "Sorted Tuna List by Age:" << endl;
    for (const auto& tuna : tunaList) {
        cout << "Name: " << tuna.getName() << ", Age: " << tuna.getAge() << endl;
    }

    tunaList.sort();
    cout << "Sorted Tuna List by < oprator:" << endl;
    for (const auto& tuna : tunaList) {
        cout << "Name: " << tuna.getName() << ", Age: " << tuna.getAge() << endl;
    }

    return 0;
}

包含对象的list进行删除

这时候需要使用list的 remove() 方法，但是需要注意的是，需要给 remove() 方法指定标准。在类中实现 == 比较运算符。

#include <iostream>
#include <list>
#include <string>
using namespace std;

class Human {
    string name;
    int age;
public:
    Human(string name, int age) {
        this->name = name;
        this->age = age;
    }
    string getName() const {
        return name;
    }
    int getAge() const {
        return age;
    }
    bool operator==(const Human& other) {
        return name == other.name;
    }
};

int main() {
    list<Human> humanList;
    humanList.push_back(Human("张三", 18));
    humanList.push_back(Human("李四", 20));
    humanList.push_back(Human("王五", 22));

    for (const auto& human : humanList) {
        cout << "Name: " << human.getName() << ", Age: " << human.getAge() << endl;
    }

    humanList.remove(Human("李四", 20));

    cout << "=======> After remove: 李四 <==========" << endl;
    for (const auto& human : humanList) {
        cout << "Name: " << human.getName() << ", Age: " << human.getAge() << endl;
    }

    return 0;
}

实现的 Human::operator==将该对象与 list 中的元素进行比较。该运算符在姓名相同时返回 true，向 list::remove( )指出了匹配标准。

std::forward_list

std::forward_list 是 C++11 引入的一个单向链表容器，提供了类似于 std::list 的功能，但只支持单向遍历。它的底层实现依赖于节点（node）和指针（pointer）。

forward_list 的用法与 list 很像，但只能沿一个方向移动迭代器，且插入元素时只能使用函数 push_front()，而不能使用 push_back()。当然，总是可以使用 insert() 及其重载版本在指定位置插入元素。

下列代码演示了 forward_list 的实例化，添加元素和单向遍历：

#include <iostream>
#include <forward_list>
using namespace std;
int main() {
    forward_list<int> myList;
    myList.push_front(1);
    myList.push_front(2);
    myList.push_front(3);
    // 现在 myList 包含 3, 2, 1
    for (const auto& elem : myList) {
        cout << elem << " ";
    }
    cout << endl;

    auto it = myList.begin();
    myList.insert_after(it, 4);
    // 现在 myList 包含 3, 4, 2, 1
    for (auto singleIt = myList.begin(); singleIt != myList.end(); singleIt++) {
        cout << *singleIt << " ";
    }
    cout << endl;

    return 0;
}

鉴于 forward_list 不支持双向迭代，因此只能对迭代器使用运算符++，而不能使用–。

列表总结：

• 如果需要频繁地插入或删除元素（尤其是在中间插入或删除时），应使用 std::list，而不是 std::vetor。因为在这种情况下，vector 需要调整其内部缓冲区的大小，以支持数组语法，还需执行开销高昂的复制操作，而 list 只需建立或断开链接。

• 请记住，可使用成员方法 push_front() 和 push_back() 分别在 list 开头和末尾插入元素。

• 对于要使用 list 等 STL 容器存储其对象的类，别忘了在其中实现运算符<和==，以提供默认的排序和删除谓词。

• 请记住，像其他 STL 容器类一样，总是可以使用 list::size() 来确定 list 包含多少个元素。

• 请记住，像其他 STL 容器类一样，可使用方法 list::clear() 清空 list。

• 无需频繁在两端插入或删除元素，且不用在中间插入或删除元素时，请不要使用 list；在这些情况下，vector 和 deque 的速度要快得多。

• 如果不想根据默认标准进行删除或排序，别忘了给 sort() 和 remove() 提供一个谓词函数。

std::set和std::multiset

set 是 C++ 标准库中的一个关联容器，用于存储唯一的元素，自动排序。它基于红黑树实现，提供了快速的插入、删除和查找操作。

multiset 是 set 的一个变体，允许存储重复的元素。

set 的常用方法包括：

• insert()：插入元素。
• erase()：删除元素。
• find()：查找元素。
• size()：返回元素数量。
• empty()：检查是否为空。
• clear()：清空容器。

multiset 的常用方法与 set 类似，只是允许存储重复元素。

为了实现快速搜索，STL set 和 multiset 的内部结构像二叉树，这意味着将元素插入到 set 或 multiset时将对其进行排序，以提高查找速度。这还意味着不像 vector 那样可以使用其他元素替换给定位置的元素，位于 set 中特定位置的元素不能替换为值不同的新元素，这是因为 set 将把新元素同内部树中的其他元素进行比较，进而将其放在其他位置。

set和multiset的实例化

可以使用以下方式实例化：

set<int> mySet;
multiset<int> myMultiset;

set<Tuna> myTunaSet;
multiset<Tuna> myTunaMultiset;

鉴于 set 和 multiset 都是在插入时对元素进行排序的容器，如果您没有指定排序标准，它们将使用默认谓词 std::less，确保包含的元素按升序排列。

要创建二元排序谓词，可在类中定义一个 operator()，让它接受两个参数（其类型与集合存储的数据类型相同），并根据排序标准返回 true。下面是一个这样的排序谓词，它按降序排列元素：

// used as a template parameter in set / multiset instantiation
template <typename T>
struct SortDescending
{
 bool operator()(const T& lhs, const T& rhs) const
 {
     return (lhs > rhs);
 }
};

然后，在实例化 set 或 multiset 时指定该谓词，如下所示：

// a set and multiset of integers (using sort predicate)
set <int, SortDescending<int>> setInts;
multiset <int, SortDescending<int>> msetInts; 

也可以使用迭代器来通过另一个容器的元素来初始化 set 或 multiset，如下所示：

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main(){
    vector<int> vec = {1, 2, 3, 4, 5};
    set<int> setInts(vec.cbegin(), vec.cend());
    for (auto it = setInts.begin(); it != setInts.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

set和multiset的插入元素

#include <iostream>
#include <set>
#include <vector>
using namespace std;

template <typename T>
void DisplayContents(const T& container)
{
    for (auto element = container.cbegin(); element != container.cend(); element++)
    {
        cout << *element << " ";
    }
    cout << endl;
}

int main()
{
    // 使用 insert() 方法插入单个元素
    set<int> setInts;
    setInts.insert(1);
    setInts.insert(2);
    setInts.insert(3);
    DisplayContents(setInts);

    cout << endl;

    // 使用 insert() 方法插入多个元素
    cout << "======>use another insert to add item<======" << endl;
    vector<int> vec = {4, 5, 6};
    set<int> setInts2;
    setInts2.insert(vec.cbegin(), vec.cend());
    DisplayContents(setInts2);
    cout << endl;

    return 0;
}

DisplayContents这个模板方法，用来打印一个容器里的内容。它接受一个容器作为参数，使用迭代器遍历容器中的元素，并打印每个元素。

multiset 中计算一个元素的数量有多少

使用 count() 函数可以计算 multiset 中特定元素的数量。

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> myMultiset = {1, 2, 2, 2, 3, 4, 5};

    // 计算元素3的数量
    int count = myMultiset.count(2);
    cout << "Count of 2 in set: " << count << endl;   // 输出 3
    // 尝试计算一个不存在的元素
    count = myMultiset.count(6);
    cout << "Count of 6 in set: " << count << endl;  // 输出 0

    return 0;
}

set、multiset、map、multimap中查找元素

诸如 set、multiset、map 和 multimap 等关联容器都提供了成员函数 find() ，它让您能够根据给定的键来查找值：

auto elementFound = setInts.find (-1);
// Check if found...
if (elementFound != setInts.end ())
 cout << "Element " << *elementFound << " found!" << endl;
else
 cout << "Element not found in set!" << endl; 

multiset 可包含多个值相同的元素，因此对于 multiset，这个函数查找第一个与给定键匹配的元素。

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> myMultiset = {1, 2, 2,3, 4, 2, 5};

    // 查找元素2
    auto it = myMultiset.find(2);
    if (it != myMultiset.end()) {
        cout << "Found element: " << *it << endl; // 输出 2
    } else {
        cout << "Element not found." << endl;
    }

    // 继续查找下一个元素2
    int count = myMultiset.count(2);
    for (int i = 0; i < count - 1; i++) {
        it++;
        cout << "Found another qualified element: " << *it << endl; // 输出 2
    }

    return 0;
}

鉴于 multiset 可能在 相邻的位置 存储多个值相同的元素，为了访问所有这些元素，可使用 find() 返回的迭代器，并将迭代器前移 count()-1 次。

set、multiset、map、multimap中删除元素

诸如 set、multiset、map 和 multimap 等关联容器都提供了成员函数 erase() ，它有三种重载方法。

• 您能够根据键删除值：

    setObject.erase (key);
  

• erase()函数的另一个版本接受一个迭代器作为参数，并删除该迭代器指向的元素：

    setObject.erase (element);
  

• 通过使用迭代器指定的边界，可将指定范围内的所有元素都从 set 或 multiset 中删除：

    setObject.erase (iLowerBound, iUpperBound); 
  

使用实例：

#include <iostream>
#include <set>
using namespace std;

template <typename T>
void DisplayContents(const T& container)
{
    for (auto element = container.cbegin(); element !=container.cend(); element++)
    {
        cout << *element << " ";
    }
    cout << endl;
}

int main() {
    multiset<int> myMultiset = {1, 2, 2, 3, 4, 2, 5};

    // 删除元素2
    myMultiset.erase(2);

    // 输出删除后的内容
    cout << "After erasing 2: ";
    DisplayContents(myMultiset);

    // 删除一个不存在的元素（不会报错）
    myMultiset.erase(6); // 不存在的元素

    auto it = myMultiset.find(3);
    myMultiset.erase(it);

    // 输出删除后的内容
    cout << "After erasing 3: ";
    DisplayContents(myMultiset);

    return 0;
}

使用set实现的简要电话薄

#include <iostream>
#include <set>
#include <string>
using namespace std;

template <typename T>
void DisplayContents(const T& container)
{
    for (auto element = container.cbegin(); element !=container.cend(); element++)
    {
        cout << *element << " ";
    }
    cout << endl;
}

struct ContactItem {
    string name;
    string phone;
    string displayAs;

    ContactItem(string n, string p) : name(n), phone(p) {
        displayAs = name + "(" + phone + ")";
    }

    bool operator<(const ContactItem& other) const {
        return name < other.name;
    }

    bool operator==(const ContactItem& other) const {
        return name == other.name;
    }

    // Used in DisplayContents via cout
    operator const char*() const{
        return displayAs.c_str();
    }
};

int main () {
    set<ContactItem> setContacts;
    setContacts.insert(ContactItem("张三", "123456"));
    setContacts.insert(ContactItem("李四", "654321"));
    setContacts.insert(ContactItem("王五", "112233"));
    DisplayContents(setContacts);

    cout << "Enter a name you wish to delete: ";
    string nameToDelete;
    getline(cin, nameToDelete);
    
    auto contactFound = setContacts.find(ContactItem(nameToDelete, ""));
    if (contactFound != setContacts.end()) {
        setContacts.erase(contactFound);
        cout << "Contact deleted." << endl;
    } else {
        cout << "Contact not found." << endl;
    }

    DisplayContents(setContacts);
    return 0;
}

unordered_set和unordered_multiset

底层实现

• set: 底层基于红黑树 (Red-Black Tree) 实现。红黑树是一种自平衡二叉查找树，它能保证插入、删除和查找操作的时间复杂度为 O(logN)。

• unordered_set: 底层基于哈希表 (Hash Table) 实现。它使用哈希函数将元素映射到哈希表的桶 (bucket) 中，通过哈希冲突处理机制来解决多个元素映射到同一个桶的情况。

元素存储顺序

• set: 元素是有序存储的。它会根据元素的键值进行排序（默认是升序）。当你遍历 set 中的元素时，你会得到一个有序的序列。

• unordered_set: 元素是无序存储的。元素的存储位置由其哈希值决定，因此遍历 unordered_set 得到的元素顺序是不确定的。

性能

• set:
  • 平均时间复杂度: 插入、删除、查找操作的时间复杂度都是 O(logN)。
  • 最坏时间复杂度: 也是 O(logN)，因为红黑树是自平衡的。
• unordered_set:
  • 平均时间复杂度: 插入、删除、查找操作的时间复杂度都是 O(1)。
  • 最坏时间复杂度: 在哈希冲突严重的情况下，所有元素都映射到同一个桶，哈希表会退化成链表，此时操作的时间复杂度会降为 O(N)。不过这种情况非常罕见，通常可以通过选择好的哈希函数和管理哈希表大小来避免。

使用 std::unordered_set 及其方法 insert( )、find( )、size( )、max_bucket_count( )、load_factor( )和 max_load_factor( )

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> mySet;

    // 插入元素
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);

    // 查找元素
    auto it = mySet.find(20);
    if (it != mySet.end()) {
        cout << "Element found: " << *it << endl;
    } else {
        cout << "Element not found." << endl;
    }

    // 元素数量
    cout << "Size: " << mySet.size() << endl;

    // 最大桶数量
    cout << "Max bucket count: " << mySet.max_bucket_count() << endl;

    // 负载因子
    cout << "Load factor: " << mySet.load_factor() << endl;

    // 最大负载因子
    cout << "Max load factor: " << mySet.max_load_factor() << endl;

    return 0;
}

程序方法解释：

---

unordered_set 和 unordered_map 的哈希表性能在很大程度上取决于其内部管理机制，max_bucket_count、load_factor 和 max_load_factor 就是其中几个关键参数。

1. max_bucket_count

• 作用：表示容器所能容纳的最大桶（bucket）数量。
• 解释：这是一个只读成员函数，用于获取哈希表当前能支持的最大桶数。这个值通常由 C++ 标准库实现决定，并不会轻易改变。它代表了容器容量的一个上限，保证哈希表不会无限膨胀。当容器需要重新哈希（rehash）时，它会选择一个新的桶数，但这个新桶数不会超过 max_bucket_count。

2. load_factor

• 作用：衡量哈希表的拥挤程度。
• 计算方式：load_factor = 元素数量（size） / 桶数量（bucket_count）
• 解释：load_factor 是一个动态变化的指标。它告诉你平均每个桶里有多少个元素。
  • 低 load_factor：哈希表很稀疏，冲突少，查询速度快，但会占用更多内存。
  • 高 load_factor：哈希表很拥挤，冲突多，查询速度变慢，但内存利用率高。

3. max_load_factor

• 作用：控制哈希表自动重新哈希的阈值。
• 解释：这是一个可读写的参数，可以由你手动设置。当哈希表的 load_factor 超过 max_load_factor 时，容器会自动进行重新哈希（rehash）操作。
• 重新哈希：这是一种代价较高的操作。容器会创建一个新的、更大的哈希表（通常桶数量是之前的两倍），然后把旧哈希表中的所有元素重新插入到新哈希表中。这个过程会消耗较多时间和计算资源。

---

三者关系及实际应用

这三个参数共同协作来平衡 unordered_set 的性能和内存使用：

1. 你通过 max_load_factor 设定一个“拥挤”的上限。
2. 容器在插入新元素时，会实时计算 load_factor。
3. 一旦 load_factor 超过你设定的 max_load_factor，容器就会触发重新哈希。
4. 重新哈希时，容器会增加桶的数量 (bucket_count)，从而降低 load_factor，使其重新回到 max_load_factor 以下。新的桶数不会超过 max_bucket_count。

对于 Android 开发者来说，如果你在 C++ 项目中使用了 unordered_set 或 unordered_map，并遇到了性能瓶颈，通常可以通过手动调整 max_load_factor 来优化。如果你的数据量是已知的，或者对性能要求极高，你可以在容器初始化时使用 reserve() 函数预留足够的空间，避免频繁的重新哈希，这比动态调整 max_load_factor 更高效。

疑问：load_factor太大表示每个桶内元素过于拥挤时，重新hash为什么可以解决这个问题？

当哈希表的 max_load_factor（最大负载因子）被超过时，确实需要进行重新哈希（Rehashing），而不仅仅是简单地移动元素。这是因为哈希函数通常依赖于哈希表的容量。一个简单的哈希函数可能是 hash(key) % capacity 。当 capacity 改变时，同一个 key 得到的哈希值也就不一样了，即当容量增大后，即使是哈希值相同的两个键，在新的哈希表中也可能被分配到不同的位置，从而显著降低冲突的概率。

• 请牢记，STL set 和 multiset 容器针对频繁查找 的情形进行了优化。
• 请牢记，std::multiset 可存储多个值相同的元素 （键），而 std::set 只能存储不同的值。
• 务必使用 multiset::count(value)确定有多少个元 素包含特定的值。
• 请牢记，set::size( )和 multiset::size( )指出容器包 含多少个元素。
• 对于其对象将存储在 set 或 multiset 等容器中的类，别忘了在其中实现运算符<和==。前者将成为排序谓词，而后者将用于 set::find( )等函数。
• 在需要频繁插入而很少查找的情形下，不要使用 std::set 或 std::multiset；在这种情形下，std::vector和 std::list 通常更适合。

STL map和multimap

map 和 multimap 之间的区别在于，后者能够存储重复的键，而前者只能存储唯一的键。

为了实现快速查找，STL map 和 multimap 的内部结构看起来像棵二叉树。这意味着在 map 或 multimap 中插入元素时将进行排序。

map的实例化

典型的 map 实例化语法如下：

#include <map>
using namespace std;
...
map <keyType, valueType, Predicate=std::less <keyType>> mapObj;
multimap <keyType, valueType, Predicate=std::less <keyType>> mmapObj;

第三个模板参数是可选的。如果您值指定了键和值的类型，而省略了第三个模板参数，std::map 和 std::multimap 将把 std::less<> 用作排序标准。

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }
    return 0;
}

map中插入元素

可以使用 insert() 方法插入元素，例如：

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap.insert(pair<int, string>(1, "one"));
    myMap.insert(pair<int, string>(2, "two"));
    myMap.insert(pair<int, string>(3, "three"));

    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }
    return 0;
}

也可以采用数组方式添加元素，例如：

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }
    return 0;
}

类似于multiset，multimap中也可以使用 multimap::count() 指出有多少个元素包含指定的键。

map使用find()查找元素

find()函数总是返回一个迭代器。首先检查该迭代器，确保 find( )已成功，再使用它来访问找到的值。

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    map<int, string>::iterator it = myMap.find(2);
    if (it != myMap.end()) {
        cout << "Found: " << it->first << " => " << it->second << endl;
    } else {
        cout << "Not found" << endl;
    }
    return 0;
}

如果使用的是 multimap，容器可能包含多个键相同的键-值对，因此需要找到与指定键对应的所有值。为此，可使用 multimap::count( ) 确定有多少个值与指定的键对应，再对迭代器递增，以访问这些相邻的值：

#include <map>
#include <iostream>
using namespace std;

int main() {
    multimap<int, string> myMap;
    myMap.insert(pair<int, string>(1, "one"));
    myMap.insert(pair<int, string>(2, "two"));
    myMap.insert(pair<int, string>(2, "two2"));
    myMap.insert(pair<int, string>(3, "three"));

    // 查找键为2的元素
    multimap<int, string>::iterator it = myMap.find(2);
    if (it != myMap.end()) {
        cout << "Found: " << it->first << " => " << it->second << endl;
    } else {
        cout << "Not found" << endl;
    }
    // 查找键为2的元素的数量
    int count = myMap.count(2);
    cout << "Count: " << count << endl;
    for (int i = 0; i < count; i++) {
        cout << "Found Again: " << it->first << " => " << it->second << endl;
        it++;
    }
    return 0;
}

使用erase()删除元素

类似于set，multimap也可以使用erase()删除元素。并且都是有三种类似的重载函数。

直接接收元素，接收迭代器，接收两个迭代器中间的范围：

#include <map>
#include <iostream>
using namespace std;

int main() {
    multimap<int, string> myMap;
    myMap.insert(pair<int, string>(1, "one"));
    myMap.insert(pair<int, string>(2, "two"));
    myMap.insert(pair<int, string>(2, "two2"));
    myMap.insert(pair<int, string>(3, "three"));

    // 删除键为2的元素
    myMap.erase(2);

    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }

    auto it3 = myMap.find(3);
    // 删除迭代器指向的元素
    myMap.erase(it3);

    cout << "======>erase 3<========" << endl;

    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }

    // 删除迭代器范围指向的元素
    myMap.erase(myMap.begin(), myMap.end());

    cout << "======>erase all<========" << endl;

    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }

    return 0;
}

map编写排序谓词

要提供不同的排序标准，可编写一个二元谓词—实现了 operator() 的类或结构：

template<typename keyType>
struct Predicate
{
 bool operator()(const keyType& key1, const keyType& key2)
 {
 // your sort priority logic here
 }
};

例如一个电话薄场景，要求姓名 string 来对比的时候，不区分大小写，那么就可以编写一个谓词来实现：

#include <iostream>
#include <map>
#include <string>
#include<algorithm> 
using namespace std;

struct PredIgnoreCase
{
    bool operator()(const string& s1, const string& s2) const
    {
        string s1Lower = s1;
        string s2Lower = s2;
        transform(s1Lower.begin(), s1Lower.end(), s1Lower.begin(), ::tolower);
        transform(s2Lower.begin(), s2Lower.end(), s2Lower.begin(), ::tolower);
        return s1Lower < s2Lower;
    }
};

int main() {
    map<string, string> contactMap;
    contactMap["John"] = "123456";
    contactMap["jane"] = "789012";
    contactMap["alice"] = "345678";
    contactMap["Amy"] = "124525";

    for (auto it = contactMap.begin(); it != contactMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }

    // 按照姓名排序
    cout << "======>sort by name<========" << endl;
    map<string, string, PredIgnoreCase> sortedMap(contactMap.begin(), contactMap.end());
    for (auto it = sortedMap.begin(); it != sortedMap.end(); ++it) {
        cout << it->first << " => " << it->second << endl;
    }
    return 0;
}

unordered_map

类似于unordered_set，unordered_map也可以使用哈希函数来存储元素，并且也可以使用自定义的哈希函数。

鉴于 unordered_map 将键-值对存储在桶中，在元素数达到或接近桶数时，它将自动执行负载均衡：

cout << "Load factor: " << umapIntToStr.load_factor() << endl;
cout << "Max load factor = " << umapIntToStr.max_load_factor() << endl;
cout << "Max bucket count = " << umapIntToStr.max_bucket_count() << endl;

load_factor() 指出了 unordered_map 桶的填满程度。因插入元素导致 load_factor() 超过 max_load_factor() 时，unordered_map 将重新组织以增加桶数，并重建散列表。

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, string> umapIntToStr;
    umapIntToStr.insert(pair<int, string>(1, "one"));
    umapIntToStr.insert(pair<int, string>(2, "two"));
    umapIntToStr.insert(pair<int, string>(3, "three"));
    umapIntToStr.insert(pair<int, string>(4, "four"));
    umapIntToStr.insert(pair<int, string>(5, "five"));
    umapIntToStr.insert(pair<int, string>(6, "six"));
    umapIntToStr.insert(pair<int, string>(7, "seven"));
    umapIntToStr.insert(pair<int, string>(8, "eight"));
    umapIntToStr.insert(pair<int, string>(9, "nine"));
    umapIntToStr.insert(pair<int, string>(10, "ten"));
    umapIntToStr.insert(pair<int, string>(11, "eleven"));
    umapIntToStr.insert(pair<int, string>(12, "twelve"));
    umapIntToStr.insert(pair<int, string>(13, "thirteen"));
    
    cout << "Load factor: " << umapIntToStr.load_factor() << endl;
    cout << "Bucket Count:" << umapIntToStr.bucket_count() << endl;
    cout << "Max load factor = " << umapIntToStr.max_load_factor() << endl;
    cout << "Max bucket count = " << umapIntToStr.max_bucket_count() << endl;

    cout << "add 14th item" << endl;
 
    umapIntToStr.insert(pair<int, string>(14, "fourteen"));
    umapIntToStr.insert(pair<int, string>(15, "fifteen"));
    cout << "Load factor: " << umapIntToStr.load_factor() << endl;
     cout << "Bucket Count:" << umapIntToStr.bucket_count() << endl;
    cout << "Max load factor = " << umapIntToStr.max_load_factor() << endl;
    cout << "Max bucket count = " << umapIntToStr.max_bucket_count() << endl;
    return 0;
}

根据打印调整元素数量，一开始分配了13个bucket，当插入14个元素时，触发了rehash，分配了29个bucket。

注意：

• 无论使用的键是什么，都不要编写依赖于 unordered_map 中元素排列顺序的代码。在unordered_map 中，元素相对顺序取决于众多因素，其中包括键、插入顺序、桶数等。这些容器为提高查找性能进行了优化，遍历其中的元素时，不要依赖于元素的排列顺序。
• 在不发生冲突的情况下，std::unordered_map 的插入和查找时间几乎是固定的，不受包含的元素数的影响。然而，这并不意味着它优于在各种情形下复杂度都为对数的std::map。在包含的元素不太多的情况下，固定时间可能长得多，导致std::unordered_map 的速度比std::map 慢。选择容器类型时，务必执行模拟实际情况的基准测试。

map小结

• 需要存储键-值对且键是唯一的时，务必使用map。
• 需要存储键-值对且键可能重复时（如电话簿），务必使用 multimap。
• 请牢记，与其他 STL 容器一样，map 和 multimap 都有成员方法 size() ，它指出容器包含多少个键-值对。
• 必须确保插入和查找时间固定时（通常是包含的元素非常多时），务必使用 unordered_map 或unordered_multimap。
• 别忘了， multimap::count(key) 指出容器中有多少个元素的键为 key。
• 别忘了检查 find() 的返回值—将其与容器的 end() 进行比较。

函数对象

函数对象（Function Object）是 C++ 中的一种特殊类型的对象，它重载了 operator()，使得该对象可以像函数一样被调用。函数对象通常用于 STL 算法和容器中，以提供自定义的行为。

从概念上来说，函数对象是用作函数的对象；但从实现上说，函数对象是实现了 operator()的类的对象。虽然函数和函数指针也可归为函数对象，但实现了 operator()的类的对象才能保存状态（即类的成员属性的值），才能用于标准模板库（STL）算法。

C++程序员常用于 STL 算法的函数对象可分为下列两种类型。

• 一元函数：接受一个参数的函数，如 f(x) 。如果一元函数返回一个布尔值，则该函数称为谓词。
• 二元函数：接受两个参数的函数，如 f(x, y) 。如果二元函数返回一个布尔值，则该函数称为二元谓词。

返回布尔类型的函数对象通常用于需要进行判断的算法，如前面介绍的 find()和 sort()。组合两个函数对象的函数对象称为自适应函数对象。

一元函数

只对一个参数进行操作的函数称为一元函数。一元函数的功能可能很简单，如在屏幕上显示元素，如下所示：

// A unary function
template <typename elementType>
void FuncDisplayElement (const elementType& element)
{
    cout << element << ' ';
}; 

该函数也可采用另一种表现形式，即其实现 包含在类或结构的operator() 中：

// Struct that can behave as a unary function
template <typename elementType>
struct DisplayElement
{
 void operator () (const elementType& element) const
 {
 cout << element << ' ';
 }
}; 

这种形式的函数对象可以存储状态（即类的成员变量），并且可以在 STL 算法中使用。使用举例：

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

using namespace std;

template <typename T>
struct DisplayElement {
    void operator() (const T& element) const {
        cout << element << "" << endl;
    }
};

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    for_each(vec.begin(), vec.end(), DisplayElement<int>());

    list<char> list = {'a', 'b', 'c', 'd', 'e'};
    for_each(list.begin(), list.end(), DisplayElement<char>());
    cout << "using lambda" << endl;
    for_each(vec.begin(), vec.end(), [](int element) {
        cout << element << "" << endl;
    });
    cout << "using lambda" << endl;
    for_each(list.begin(), list.end(), [](char element) {
        cout << element << "" << endl;
    });
    return 0;
}

我们使用定义的这个结构体函数对象来打印int和char类型，最后的两个打印操作，使用到了lambda表达式，可以不用提前定义函数对象。

插入：操作符函数

操作符函数是重载了特定操作符的函数对象。通过重载操作符，可以使得对象能够像内置类型一样使用操作符进行操作。

例如之前用到的，对自定义的 MyString 类进行拼接时，重写 + 操作符，就可以直接使用 + 来操作对象。

class MyString {
public:
    ...

    MyString(const char* str) : data(str) {}

    // 重载 + 操作符
    MyString operator+(const MyString& other) const {
        return MyString((data + other.data).c_str());
    }

    ...
}

还有 == 操作符，用于对两个对象进行比较时来判断。例如在list中进行remove操作时。

这里的就是 () 操作符，在函数声明时用来定义 函数调用运算符 operator() 的。

结构中定义的优势

如果能够使用结构的对象来存储信息，则使用在结构中实现的函数对象的优点将显现出来。

我们设计一个结构，可以计算自己的 operator() 函数被调用的次数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
struct DisplayAndCount 
{
    int count;

    DisplayAndCount() : count(0) {}

    void operator() (const T& element) {
        cout << element << "" << endl;
        count++;
    }
};

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    DisplayAndCount<int> displayAndCount;
    displayAndCount = for_each(vec.begin(), vec.end(), DisplayAndCount<int>());
    cout << "count: " << displayAndCount.count << endl;
    return 0;
}

对于displayAndCount = for_each(vec.begin(), vec.end(), DisplayAndCount<int>());这行代码，我们可以分步来理解：

1. for_each 函数的作用

首先，std::for_each 是 C++ 标准库中的一个算法，它的作用是对一个范围内的每个元素应用一个操作。

它的函数签名大致是这样的： for_each(InputIterator first, InputIterator last, UnaryFunction f)

• first 和 last：表示要遍历的范围，例如 vec.begin() 和 vec.end()。
• f：一个可调用的对象（函数、函数指针、Lambda表达式或函数对象），它会对范围内的每个元素执行一次操作。

for_each 函数的一个关键特性是它的返回值：它返回它所传入的那个可调用对象的拷贝。

2. DisplayAndCount<int>()

这部分代码创建了一个 DisplayAndCount<int> 类型的临时匿名对象。这个对象在作为第三个参数传递给 for_each 函数时，会发生以下过程：

1. for_each 接收这个对象的一个拷贝。
2. for_each 遍历 vec 中的每个元素（1, 2, 3, 4, 5）。
3. 对于每个元素，它都会调用这个拷贝对象的 operator() 方法。
4. 在每次调用时，这个拷贝对象的 count 成员变量会递增。

3. for_each 的返回值

当 for_each 遍历完所有元素后，它会将 它内部那个 DisplayAndCount<int> 对象的拷贝 返回。此时，这个被返回的对象中的 count 已经变为了 5。

4. 赋值操作

最后，这个 for_each 返回的、count 值为 5 的临时对象，通过赋值操作符 = 赋给了你在 main 函数中创建的 displayAndCount 对象。

思考：是否可以使用按引用传递的方式来传递这个函数对象，而不用接收匿名对象的拷贝？

回答：可以的，我们使用for_each算法时，将函数对象的参数使用 std::ref() 包裹起来，这样就可以避免拷贝构造函数的调用。但是为什么 STL 算法通过返回值来传递结果是一种常见模式，这在 C++ 标准库中非常普遍。

使用值传递拷贝并返回，而不是按引用。设计上的考量主要有三点：

• 一是优化和内联，像这种轻量级的函数对象，可以很轻松的内联避免函数调用开销。并且在运行过程中，这个对象就成了栈上的局部变量，可以进行更激进的寄存器分配和优化。如果使用引用传递，编译器在优化时会变得更保守，因为它必须考虑到你传入的这个引用可能指向一个全局变量、堆内存或其他地方，这会使得它无法像处理局部变量那样简单地进行优化。
• 二是线程安全考虑，如果 for_each 默认使用引用传递，那么在多线程环境中调用它会变得很危险。多个线程可能会同时使用同一个仿函数对象，导致数据竞争（data race），因为它们都在试图修改同一个 count 变量，从而产生未定义的行为。而值传递方案则能天然地解决这个问题。每个线程调用 for_each 时，都会得到一个独立的、属于它自己的仿函数副本。这个副本只会在该线程内部被修改，因此不同线程之间不会互相干扰，实现了线程安全。
• 第三是设计模式，在函数式编程中，函数不应该有副作用（side effect），即不应该修改传入的参数或者任何外部状态。for_each 通过值传递仿函数，并返回一个新对象来承载结果，这种模式很好地遵循了这一原则。

一元谓词

一元谓词是接受一个参数并返回布尔值的函数对象。它通常用于 STL 算法中进行条件判断。

下面这个例子，设计一个IsMultiple类，用于判断一个数是否是另一个数的倍数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
struct IsMultiple {
    T multiple;
    IsMultiple(T multiple) : multiple(multiple) {}
    bool operator() (T element) const {
        return ((element % multiple) == 0);
    }
};

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    
    int divisor = 2;

    auto it = find_if(vec.begin(), vec.end(), IsMultiple<int>(divisor));

    if (it != vec.end()) {
        cout << "找到第一个倍数: " << *it << endl;
    } else {
        cout << "没有找到倍数" << endl;
    }

    return 0;
}

find_if() 使用了一元谓词，这里将函数对象 IsMutilple 初始化为用户提供的除数， find_if() 对指定范围内的每个元素调用一元谓词 IsMutilple::operator() 。当 operator() 返回 true（即元素可被用户提供的除数整除）时，find_if() 返回一个指向该元素的迭代器。然后，将 find_if() 操作的结果与容器的 end() 进行比较，以核实是否找到了满足条件的元素，接下来使用迭代器 iElement 显示该元素的值。

一元谓词被大量用于 STL 算法中。例如，算法 std::partition() 使用一元谓词来划分范围，算法 stable_partition() 也使用一元谓词来划分范围，但保持元素的相对顺序不变。诸如 std::find_if() 等查找函数以及 std::remove_if() 等删除元素的函数也使用一元谓词，其中 std::remove_if() 删除指定范围内满足谓词条件的元素。

二元函数

二元函数是接受两个参数并返回一个值的函数对象。它通常用于 STL 算法中进行元素操作。

下面这个例子，设计一个 Multiply 结构体，来计算两个数的乘积。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
struct Multiply 
{
    T operator() (const T& a, const T& b) const {
        return a * b;
    }
};

int main() {
    vector<int> vec = {0, 1, 2, 3, 4};
    vector<int> vec2 = {1, 2, 3, 4, 5};
    vector<int> vecResult;
    vecResult.resize(vec2.size());
    
    transform(vec.begin(), vec.end(), vec2.begin(), vecResult.begin(), Multiply<int>());
    cout << "vecResult: " << endl;
    for (int i : vecResult) {
        cout << i << endl;
    }

    return 0;
}

二元谓词

二元谓词是接受两个参数并返回布尔值的函数对象。它通常用于 STL 算法中进行比较操作。

举之前的一个例子，接受两个字符串，进行不区分大小写的比较。常用于电话簿，app列表等。

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

template <typename S>
struct CompareStringNoCase
{
    bool operator() (const S& a, const S& b) const
    {
        string aLower;
        string bLower;
        aLower.resize(a.size());
        bLower.resize(b.size());
        transform(a.begin(), a.end(), aLower.begin(), ::tolower);
        transform(b.begin(), b.end(), bLower.begin(), ::tolower);
        return aLower < bLower;
    }
};

int main()
{
    set<string, CompareStringNoCase<string>> setContacts;
    setContacts.insert("Amy");
    setContacts.insert("Bob");
    setContacts.insert("Caroline");
    setContacts.insert("alice");
    setContacts.insert("dave");
    setContacts.insert("Eve");
    setContacts.insert("carl");

    for (const string& contact : setContacts)
    {
        cout << contact << endl;
    }

    return 0;
}

lambda 表达式

可将 lambda 表达式视为包含公有 operator() 的匿名结构（或类），从这种意义上说，lambda 表达式属于前面介绍的函数对象。

例如将之前的 DisplayElement 类，用 lambda 表达式来实现。

// struct that behaves as a unary function
template <typename elementType>
struct DisplayElement
{
 void operator () (const elementType& element) const
 {
 cout << element << ' ';
 }
};

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    for_each(vec.begin(), vec.end(), [](int element) {
        cout << element << "" << endl;
    });
    return 0;
}

编译器见到上述lambda表达式，会将其转换为一个匿名的函数对象，该函数对象的 operator() 函数体就是lambda表达式的函数体。

struct NoName
{
 void operator () (const int& element) const
 {
 cout << element << ' ';
 }
}; 

一元函数的lambda表达式

与一元 operator(Type) 对应的 lambda 表达式接受一个参数，其定义如下：

[](Type paramName) { 
    // lambda expression code here;
}

请注意，如果您愿意，也可按引用传递参数：

[](Type& paramName) { 
    // lambda expression code here;
} 

另外，lambda表达式的参数声明中，也可以直接使用auto，编译器会根据lambda表达式的参数类型，自动推导参数类型。

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> vec = {1, 2, 3, 4, 5};
    for_each(vec.begin(), vec.end(), [](auto element) {
        cout << element << "" << endl;
    });

    list<char> charList = {'a', 'b', 'c', 'd', 'e'};
    for_each(charList.begin(), charList.end(), [](auto element) {
        cout << element << "" << endl;
    });
    return 0;
}

这个 lambda 表达式通过关键字 auto 利用了编译器的类型自动推断功能。遵循 C++14 的编译器都支持这种对 lambda 表达式的改进。

一元谓词的lambda表达式

例如判断一个整数是否是偶数，在返回结果里写成是否可以被2整除。编译器可以自动判断返回值为bool。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> vec = {1, 2, 3, 4, 5};
    auto it = find_if(vec.begin(), vec.end(), [](const int& element) {
       return element % 2 == 0;
    });
    if (it != vec.end()) {
        cout << "找到第一个偶数: " << *it << endl;
    } else {
        cout << "没有找到偶数" << endl;
    }
    return 0;
}

插入：符号[]的作用

C++ lambda 表达式中的 [] 叫做 capture clause（捕获子句），它的作用是让 lambda 表达式能够访问其创建时上下文（surrounding scope）中的变量。即用于指定在 lambda 表达式中可以访问的变量或对象。它主要有以下几种用法：

1. 不捕获任何变量 []

这是最基本的形式，表示 lambda 表达式不访问任何外部变量。

#include <iostream>

int main() {
    int x = 10;
    auto my_lambda = []() {
        // 无法访问 x，因为没有加入捕获
        std::cout << "Hello, World!" << std::endl;
    };
    my_lambda();
    return 0;
}

2. 按值捕获 [var] 或 [=]

• 按值捕获单个变量： [x]
  • x 的值在 lambda 创建时被 复制 到 lambda 内部。
  • 即使外部的 x 后来改变了，lambda 内部的 x 也不会受影响。

#include <iostream>

int main() {
    int x = 10;
    auto my_lambda = [x]() {
        // x 的值是 10
        std::cout << "The value of x is: " << x << std::endl;
    };
    x = 20; // 改变外部的 x
    my_lambda(); // 输出依然是 10
    return 0;
}

• 按值捕获所有变量： [=]
  • 捕获 其所在作用域中 所有被 lambda 内部使用的局部变量。
  • 同样是值复制，不会随外部变量变化。

#include <iostream>
int main() {
    int a = 1, b = 2;
    auto my_lambda = [=]() {
        // a 和 b 的值在 lambda 创建时被复制
        std::cout << "The value of a is: " << a << std::endl;
        std::cout << "The value of b is: " << b << std::endl;
    };
    a = 3; // 改变外部的 a
    my_lambda(); // 输出依然是 1 和 2
    return 0;
}

3. 按引用捕获 [&var] 或 [&]

• 按引用捕获单个变量： [&x]
  • x 的引用被传递到 lambda 内部。
  • 这意味着 lambda 内部对 x 的任何修改都会影响到外部的 x。
  • 当外部 x 的值改变时，lambda 内部也能看到最新的值。

#include <iostream>

int main() {
    int x = 10;
    auto my_lambda = [&x]() {
        // 访问的是外部的 x
        x += 5; // 修改了外部的 x
        std::cout << "The value of x inside lambda is: " << x << std::endl;
    };
    my_lambda(); // x 变为 15
    std::cout << "The value of x outside lambda is: " << x << std::endl; // 输出 15
    return 0;
}

• 按引用捕获所有变量： [&]
  • 捕获其所在作用域中所有被 lambda 内部使用的局部变量的引用。
  • 这种方式非常方便，但要小心，因为它可能导致悬空引用（dangling reference）问题，特别是当 lambda 的生命周期比它捕获的变量更长时。

4. 混合捕获 [&, x] 或 [=, &x]

你可以混合使用值捕获和引用捕获：

• [&, x]： 默认按引用捕获所有变量，但 x 单独按值捕获。
• [=, &x]： 默认按值捕获所有变量，但 x 按引用捕获。

#include <iostream>

int main() {
    int a = 1, b = 2;
    // 默认按值捕获，但 b 按引用捕获
    auto my_lambda = [=, &b]() {
        // a 是值捕获，不能修改
        std::cout << "The value of a is: " << a << std::endl;
        // b 是引用捕获，可以修改
        b = 3;
    };
    my_lambda();
    std::cout << "The value of b outside lambda is: " << b << std::endl; // 输出 3
    return 0;
}

总而言之，[] 括号就是 C++ 中 lambda 表达式的 捕获列表 ，它决定了 lambda 如何与外部世界的变量进行交互。正确使用捕获子句是编写强大、灵活的 lambda 表达式的关键。

例如，除了找到列表中能被 2 整除的数，我们希望可以由用户指定除数，增加灵活性。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int divisor = 0;
    cout << "请输入除数：" << endl;
    cin >> divisor;

    auto it = find_if(numVec.begin(), numVec.end(), [divisor](int num) {
        return num % divisor == 0;
    });

    if (it != numVec.end())
    {
        cout << "找到第一个能被" << divisor << "整除的数: " << *it << endl;
    }
    else
    {
        cout << "没有找到能被" << divisor << "整除的数" << endl;
    }
    return 0;
}

二元函数的lambda表达式

二元函数接受两个参数，可以返回一个值。

例如，将两个vector中的各个元素对应相加，并将结果存储到第三个vector中。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> vec1 = {1, 2, 3, 4, 5};
    vector<int> vec2 = {0, 1, 2, 3, 4};
    
    vector<int> vecResult;
    vecResult.resize(vec2.size());
    
    transform(vec1.begin(), vec1.end(), vec2.begin(), vecResult.begin(), [](const int& a, const int& b) {
        return a+b;
    });
    
    for(auto it = vecResult.begin();it!=vecResult.end(); it++){
        cout << *it <<" ";
    }
    cout << endl;
    
    return 0;
}

定义Lambda表达式时，习惯性在末尾加上了const。导致报错，原因如下：Lambda 表达式末尾的 const 是用来修饰 lambda 本身的，表示这个 lambda 是一个“常量”函数对象。它主要用于确保 lambda 内部不会改变其按值捕获的变量。当你没有按值捕获变量时，这个 const 并没有太大意义。 std::transform 等标准库算法所期望的函数对象通常不带这个 const 修饰符，所以加上它会导致签名不匹配的编译错误。

二元谓词对应的 lambda 表达式

返回 true 或 false、可帮助决策的二元函数被称为二元谓词。这种谓词可用于 std::sort() 等排序算法中，这些算法对容器中的两个值调用二元谓词，以确定将哪个放在前面。与二元谓词等价的 lambda 表达式的通用语法如下：

[...](Type1& param1Name, Type2& param2Name) { 
    // return bool expression; 
} 

例如，对一个姓名数组中的元素进行排序，忽略大小写按照字母表顺序：

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

using namespace std;


int main()
{
    vector<string> nameVec = {"Stephenie", "Amy", "Bob", "Cindy", "David", "Eva"};

    sort(nameVec.begin(), nameVec.end(), [](const string& a, const string& b) {
        string aLower = a;
        string bLower = b;
        transform(aLower.begin(), aLower.end(), aLower.begin(), ::tolower);
        transform(bLower.begin(), bLower.end(), bLower.begin(), ::tolower);
        return aLower < bLower;
    });

    for(auto it = nameVec.begin();it!=nameVec.end(); it++){
        cout << *it <<"\t";
    }
    cout << endl;

    return 0;
}

lambda小结

• 请牢记，lambda 表达式总是以[]或 [state1,state2,…] 打头。
• 请牢记，除非使用关键字 mutable 进行指定，否则不能修改捕获列表中指定的状态变量。
• 别忘了，lambda 表达式是实现了 operator( )的匿名类（或结构）。

• 编写 lambda 表达式时，别忘了使用 const 对参数进行限定：

    [](const T& value) {
        // lambdaexpression; 
    }
  

• lambda 表达式的语句块（{}）包含多条语句时，别忘了显式地指定返回类型。
• 不要使用很长（包含多条语句）的 lambda 表达式，而应转而使用函数对象，因为每次使用 lambda 表达式时，都需要重新定义它，这无助于提高代码 的可重用性。

STL算法

查找、搜索、删除和计数是一些通用算法，其应用范围很广。STL 通过通用的模板函数提供了这些算法以及其他的很多算法，可通过迭代器对容器进行操作。要使用 STL 算法，程序员必须包含头文件<algorithm>。

STL 算法通常分为两大类：非变序算法（Non-modifying Algorithms） 和 变序算法（Modifying Algorithms）。

非变序算法 (Non-modifying Algorithms)

非变序算法不会改变它们操作的元素的值或顺序。它们主要用于查询、计数、查找和比较操作。

常见示例：

• std::for_each(): 对范围内的每个元素执行一个指定的函数。虽然它本身不改变容器的结构，但你传递给它的函数可以修改元素的值。
• std::find(): 在一个范围内查找第一个匹配给定值的元素。
• std::find_if(): 在一个范围内查找第一个满足特定条件的元素。
• find_end(): 在指定范围内搜索最后一个满足特定条件的元素。
• std::count(): 计算一个范围内某个特定值的出现次数。
• std::count_if(): 计算一个范围内满足特定条件的元素的数量。
• std::equal(): 检查两个范围内的元素是否完全相等。
• std::all_of(): 检查一个范围内所有元素是否都满足某个条件。
• std::any_of(): 检查一个范围内是否有任何元素满足某个条件。
• std::none_of(): 检查一个范围内是否没有任何元素满足某个条件。
• std::mismatch(): 比较两个范围，返回第一个不匹配的元素对。
• search_n() 在目标范围内搜索与指定值相等或满足指定谓词的 n 个元素
• find_first_of(): 在目标范围内搜索指定序列中的任何一个元素第一次出现的位置；在另一个重载版本中，它搜索满足指定条件的第一个元素
• adjacent_find(): 在集合中搜索两个相等或满足指定条件的元素

比较算法

• equal(): 比较两个元素是否相等或使用指定的二元谓词判断两者是否相等
• mismatch(): 使用指定的二元谓词找出两个元素范围的第一个不同的地方
• lexicographical_compare(): 比较两个序列中的元素，以判断哪个序列更小

---

变序算法 (Modifying Algorithms)

变序算法会改变它们操作的元素的值或顺序。这包括排序、复制、替换、删除和排列等操作。

常见示例：

初始化算法

• fill(): 将指定值分配给指定范围中的每个元素
• fill_n(): 将指定值分配给指定范围中的前 n 个元素
• generate(): 将指定函数对象的返回值分配给指定范围中的每个元素
• generate_n(): 将指定函数的返回值分配给指定范围中的前 n 个元素 修改算法
• for_each(): 对指定范围内的每个元素执行指定的操作。当指定的参数修改了范围时，for_each 将是变序算法
• transform(): 对指定范围中的每个元素执行指定的一元函数复制算法
• copy(): 将一个范围复制到另一个范围
• copy_backward(): 将一个范围复制到另一个范围，但在目标范围中将元素的排列顺序反转

删除算法

• remove(): 将指定范围中包含指定值的元素删除
• remove_if(): 将指定范围中满足指定一元谓词的元素删除
• remove_copy(): 将源范围中除包含指定值外的所有元素复制到目标范围
• remove_copy_if(): 将源范围中除满足指定一元谓词外的所有元素复制到目标范围
• unique(): 比较指定范围内的相邻元素，并删除重复的元素。该算法还有一个重载版本，它使用二元谓词来判断要删除哪些元素
• unique_copy(): 将源范围内的所有元素复制到目标范围，但相邻的重复元素除外

替换算法

• replace(): 用一个值来替换指定范围中与指定值匹配的所有元素
• replace_if(): 用一个值来替换指定范围中满足指定条件的所有元素

排序算法

• sort(): 使用指定的排序标准对指定范围内的元素进行排序，排序标准由二元谓词提供。排序可能改变相等元素的相对顺序
• stable_sort(): 类似于 sort，但在排序时保持相对顺序不变
• partial_sort(): 将源范围内指定数量的元素排序
• partial_sort_copy(): 将源范围内的元素复制到目标范围，同时对它们排序

分区算法

• partition(): 在指定范围中，将元素分为两组：满足指定一元谓词的元素放在第一个组中，其他元素放在第二组中。不一定会保持集合中元素的相对顺序
• stable_partition(): 与 partition 一样将指定范围分为两组，但保持元素的相对顺序不变 可用于有序容器的算法
• binary_search(): 用于判断一个元素是否存在于一个排序集合中
• equal_range(): 返回一个范围，该范围包含所有与指定值相等的元素
• lower_bound(): 根据元素的值或二元谓词判断元素可能插入到排序集合中的第一个位置，并返回一个指向该位置的迭代器
• upper_bound(): 根据元素的值或二元谓词判断元素可能插入到排序集合中的最后一个位置，并返回一个指向该位置的迭代器

这些只是 STL 算法库中的一部分，但它们是最常用和最基础的。掌握它们可以让你用更简洁、更高效的方式编写 C++ 代码。

使用：查找元素

STL 算法 find() 和 find_if() 用于在 vector 等容器中查找与值匹配或满足条件的元素。find() 的用法如下：

auto element = find (numsInVec.cbegin(), // Start of range
 numsInVec.cend(), // End of range
 numToFind); // Element to find
// Check if find() succeeded
if (element != numsInVec.cend ())
 cout << "Result: Value found!" << endl;

find_if() 的用法与此类似，但需要通过第三个参数提供一个一元谓词（返回 true 或 false 的一元函数）：

auto evenNum = find_if (numsInVec.cbegin(), // Start of range
    numsInVec.cend(), // End of range
    [](int element) { return (element % 2) == 0; } );
    
if (evenNum != numsInVec.cend())
 cout << "Result: Value found!" << endl; 

计算符合条件的元素数量

STL 算法 std::count() 和 count_if() 计算给定范围内的元素数。std::count() 计算包含给定值（使用相等运算符 == 进行测试）的元素数：

size_t numZeroes = count (numsInVec.cbegin (), numsInVec.cend (), 0);
cout << "Number of instances of '0': " << numZeroes << endl;

std::count_if() 计算这样的元素数，即满足通过参数传递的一元谓词（可以是函数对象，也可以是lambda 表达式）：

// Unary predicate:
template <typename elementType>
bool IsEven (const elementType& number)
{
 return ((number % 2) == 0); // true, if even
}
...
// Use the count_if algorithm with the unary predicate IsEven:
size_t numEvenNums = count_if (numsInVec.cbegin (),
 numsInVec.cend (), IsEven <int> );
cout << "Number of even elements: " << numEvenNums << endl; 

使用举例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename elementType>
bool IsEven (const elementType& number)
{
 return ((number % 2) == 0); // true, if even
}

int main() {
    vector<int> numsInVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    size_t numZeroes = count (numsInVec.cbegin (), numsInVec.cend (), 0);
    cout << "Number of instances of '0': " << numZeroes << endl;

    size_t numEvenNums = count_if (numsInVec.cbegin (),
     numsInVec.cend (), IsEven <int> );
    cout << "Number of even elements: " << numEvenNums << endl; 

    return 0;
}

搜索元素或者序列

STL 算法 search() 用于在一个范围内搜索另一个范围的序列。它有两个重载版本：

template <typename ForwardIterator1, typename ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);
template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>

ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred);

第一个版本使用相等运算符==来比较元素，第二个版本使用传递的二元谓词来比较元素。

auto range = search (numsInVec.cbegin(), // Start range to search in
 numsInVec.cend(), // End range to search in
 numsInList.cbegin(), // start range to search
 numsInList.cend() ); // End range to search for 

算法 search_n() 用于在一个范围内搜索指定数量的连续元素，该元素与指定值匹配或满足指定条件。

auto partialRange = search_n (numsInVec.cbegin(), // Start range
                            numsInVec.cend(), // End range
                             3, // num items to be searched for
                             9  // value to search for
);

这两个函数都返回一个迭代器，它指向找到的第一个模式；使用该迭代器之前，务必将其与 end() 进行比较。

用法演示：

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numsInVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    list<int> numsInList = {9, 10, 11};
    list<int> numsInList2 = {9, 10, 11, 12};

    auto range = search (numsInVec.cbegin(), // Start range to search in
                        numsInVec.cend(), // End range to search in
                        numsInList.cbegin(), // start range to search
                        numsInList.cend() ); // End range to search for 

    if (range != numsInVec.cend())
    {
        cout << "Range found at position: " << distance(numsInVec.cbegin(), range) << endl;
    }
    else
    {
        cout << "Range not found" << endl;
    }

    range = search (numsInVec.cbegin(), // Start range to search in
                        numsInVec.cend(), // End range to search in
                        numsInList2.cbegin(), // start range to search
                        numsInList2.cend() ); // End range to search for 
                        
    if (range != numsInVec.cend())
    {
        cout << "Range found at position: " << distance(numsInVec.cbegin(), range) << endl;
    }
    else
    {
        cout << "Range not found" << endl;
    }

    return 0;
}

search_n() 使用举例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numsInVec = {1, 2, 3, 9, 9, 9, 9, 10};

    auto range = search_n(numsInVec.cbegin(), // Start range to search in
                          numsInVec.cend(),   // End range to search in
                          3, 9);              // End range to search for

    if (range != numsInVec.cend())
    {
        cout << "999 found at position: " << distance(numsInVec.cbegin(), range) << endl;
    }
    else
    {
        cout << "Range not found" << endl;
    }

    return 0;
}

使用fill

STL 算法 fill() 和 fill_n() 用于将指定范围的内容设置为指定值。fill() 将指定范围内的元素设置为指定值：

vector <int> numsInVec (3);
// fill all elements in the container with value 9
fill (numsInVec.begin (), numsInVec.end (), 9);

顾名思义，fill_n() 将 n 个元素设置为指定的值，接受的参数包括起始位置、元素数以及要设置 的值：

fill_n (numsInVec.begin () + 3, /*count*/ 3, /*fill value*/ -9); 

使用示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void DisplayContents(const T& container)
{
    for(auto it = container.begin(); it != container.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

int main()
{
    vector<int> numsInVec(3);

    fill(numsInVec.begin(), numsInVec.end(), 9);

    DisplayContents(numsInVec);
    // Output: 9 9 9

    numsInVec.resize(6);

    fill_n(numsInVec.begin() + 3, 3, 7);
    // Output: 9 9 9 7 7 7

    DisplayContents(numsInVec);

    return 0;
}

fill函数要修改容器的元素值，就不可以使用cbegin()常量迭代器，cbegin()不能用于修改容器的元素值。

使用 std::generate() 将元素设置为运行阶段生成的值

std::generate() 是 C++ 标准库 <algorithm> 中的一个泛型算法，它的主要作用是根据一个生成器函数（generator function）来为指定范围内的所有元素赋值。

简单来说，它的功能就是：用一个函数不断地生成值，并把这些值依次填充到一个容器或数组中。

std::generate() 的工作流程非常直接：

1. 它从 first 迭代器指向的元素开始。
2. 对范围中的每一个元素，它都会调用一次你提供的 Generator g。
3. g 的返回值会被赋给当前元素。
4. 它将迭代器向前移动，然后重复这个过程，直到到达 last 迭代器为止。

1. 使用 Lambda 表达式生成递增序列

这个例子使用一个 Lambda 表达式作为生成器，每次调用时让一个变量加2。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numsInVec(5);

    int start_value = 2;

    generate(numsInVec.begin(), numsInVec.end(), [&]()
             { return start_value += 2; });

    for_each(numsInVec.begin(), numsInVec.end(), [](int &n)
             { cout << n << endl; });

    return 0;
}

• 这里的 Lambda 表达式捕获了外部变量 start_value 的引用，每次被调用时都会返回 start_value 的当前值，然后将其递增。

注意细节，符号运算 += 和 ++ 不可混淆，后置自增（i++）是先创建一个副本，再增加原始变量，最后返回副本，所以看起来像是先返回再计算。而这个 += 符号就是直接运算，然后返回计算后的结果。

2. 使用函数生成随机数

这个例子使用一个自定义函数作为生成器来填充随机数。

#include <iostream>
#include <vector>
#include <algorithm>
#include <random> // C++11 之后的标准库随机数生成

// 生成随机数的函数
int generate_random_number() {
    static std::mt19937 generator(std::random_device{}()); // 静态生成器，只初始化一次
    static std::uniform_int_distribution<int> distribution(1, 100); // 1到100的均匀分布
    return distribution(generator);
}

int main() {
    std::vector<int> random_numbers(5);

    // 将函数名作为生成器传递给 generate()
    std::generate(random_numbers.begin(), random_numbers.end(), generate_random_number);

    for (int num : random_numbers) {
        std::cout << num << " "; // 输出类似: 56 12 87 34 99
    }
    std::cout << std::endl;

    return 0;
}

• generate() 的第三个参数可以接受任何可调用对象，这里我们直接传入了函数名 generate_random_number。

总结

std::generate() 是一个非常有用的工具，当你需要用重复的、有规律的或随机的方法来填充一个序列时，它比手写一个 for 循环要更简洁、更具表达力。

对于生成递增或递减的序列，C++ 标准库还提供了更专用的 std::iota() 函数，它在某些场景下会更清晰。但 generate() 的优势在于其通用性，你可以用它来处理任何可以通过一个无参数函数来生成值的场景。

使用 for_each() 处理指定范围内的元素

算法 for_each() 对指定范围内的每个元素执行指定的一元函数对象，其用法如下：

fnObjType retValue = for_each (start_of_range,
 end_of_range,
 unaryFunctionObject);

也可使用接受一个参数的 lambda 表达式代替一元函数对象。

返回值表明，for_each() 返回用于对指定范围内的每个元素进行处理的函数对象（functor）。这意味着使用结构或类作为函数对象可存储状态信息，并在 for_each() 执行完毕后查询这些信息。

实例，打印列表内每一个元素，并计算打印了多少次：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

template <typename T>
struct DisplayAndCount
{
    int count = 0;
    DisplayAndCount() : count(0) {}
    void operator()(const T &value)
    {
        cout << value << " ";
        count++;
    }
};

int main()
{
    vector<int> numbers = {1, 2, 3, 4, 5};
    DisplayAndCount<int> displayAndCount;
    displayAndCount = for_each(numbers.cbegin(), numbers.cend(), DisplayAndCount<int>());
    cout << endl;
    cout << "Count: " << displayAndCount.count << endl;

    string text = "we are the world.";
    for_each(text.cbegin(), text.cend(), [](const char &c)
             { cout << c << " "; });
    cout << endl;

    return 0;
}

后面演示了使用lambda表达式来遍历操作每个元素的方式。

使用 std::transform() 对范围进行变化

std::for_each() 和 std::transform() 很像，都对源范围内的每个元素调用指定的函数对象。然而， std::transform() 有两个版本，第一个版本一个接受一元函数，常用于将字符串转换为大写或小写（使用的一元函数分别是 toupper() 和 tolower() ）：

string str ("THIS is a TEst string!");
transform (str.cbegin(), // start source range
 str.cend(), // end source range
 strLowerCaseCopy.begin(), // start destination range
 ::tolower); // unary function

第二个版本接受一个二元函数，让 transform() 能够处理一对 来自两个不同范围的元素 ：

// sum elements from two vectors and store result in a deque
transform (numsInVec1.cbegin(), // start of source range 1
 numsInVec1.cend(), // end of source range 1
 numsInVec2.cbegin(), // start of source range 2
 sumInDeque.begin(), // store result in a deque
 plus<int>()); // binary function plus

不像 for_each() 那样只处理一个范围，这两个版本的 transform() 都将指定变换函数的结果赋给指定的目标范围。

使用 std::transform() ，对两个列表的元素进行相加的实例。之前已经写过这个例子，有意思的是， 如果两个列表的元素数量不一致， transform() 函数的表现是怎样的呢？

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numbersOne = {1, 2, 3, 4, 5};
    vector<int> numbersTwo = {6, 7, 8, 9, 10, 20};

    vector<int> result(10);

    transform(numbersOne.begin(), numbersOne.end(), numbersTwo.begin(), result.begin(), [](int a, int b)
              { return a + b; });

    for (int num : result)
    {
        cout << num << " ";
    }

    return 0;
}

这里的 transform() 函数的行为是，将 numbersOne 和 numbersTwo 中对应位置的元素相加，结果存储在 result 中。如果 numbersOne 和 numbersTwo 的元素数量不一致， transform() 函数会以第一个元素为基准，遍历完第一个列表，第二个列表缺失的话，第二个元素会被置为默认值，例如int元素处理为0，string元素处理为空字符串。

如果承载的容器大小不足，例如result长度设置为 3 会发生什么呢？经运行测试，在 result 装满之后没有自动扩容，也没有报错。

复制元素和删除元素

• copy() 复制元素，copy 沿向前的方向将源范围的内容赋给目标范围：

    auto lastElement = copy (numsInList.cbegin(), // start source range
    numsInList.cend(), // end source range
    numsInVec.begin()); // start dest range
  

• copy_if() 是 C++11 新增的，仅在指定的一元谓词返回 true 时才复制元素：

    // copy odd numbers from list into vector
    copy_if (numsInList.cbegin(), numsInList.cend(),
    lastElement, // copy position in dest range
    [](int element){return ((element % 2) == 1);});
  

• copy_backward() 沿向后的方向将源范围的内容赋给目标范围，这并不是从后往前复制一个翻转的列表，而是将源范围的元素从后往前复制到目标范围的指定位置。主要用于处理 重叠内存区域 ，特别是在你想要将一个序列向后移动（比如在 vector 中间插入一个元素时，需要将后面的元素向后移）。它通过从后往前复制，确保 在将数据复制到新位置之前，旧位置的数据不会被覆盖 。

    copy_backward (numsInList.cbegin (),
    numsInList.cend (),
    numsInVec.end ());
  

• remove( )将容器中与指定值匹配的元素删除：

    // Remove all instances of '0', resize vector using erase()
    auto newEnd = remove (numsInVec.begin (), numsInVec.end (), 0);
    numsInVec.erase (newEnd, numsInVec.end ());
  

• remove_if( )使用一个一元谓词，并将容器中满足该谓词的元素删除：

    // Remove all odd numbers from the vector using remove_if
    newEnd = remove_if (numsInVec.begin (), numsInVec.end (),
    [](int num) {return ((num % 2) == 1);} ); //predicate
    numsInVec.erase (newEnd, numsInVec.end ()); // resizing 
  

使用实例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{ 
    vector<int> numsInVec = {1, 2, 3, 4, 5, 0, 6, 7, 8, 9, 0};

    // Copy elements from numsInVec to another vector
    vector<int> copiedVec(numsInVec.size());
    copy(numsInVec.begin(), numsInVec.end(), copiedVec.begin());

    cout << "Copied Vector: ";
    for (const auto &num : copiedVec)
        cout << num << " ";
    cout << endl;

    // Remove all instances of '0'
    auto newEnd = remove(numsInVec.begin(), numsInVec.end(), 0);
    numsInVec.erase(newEnd, numsInVec.end());

    cout << "After removing '0': ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    // Remove all odd numbers
    newEnd = remove_if(numsInVec.begin(), numsInVec.end(),
                       [](int num) { return (num % 2) == 1; });
    numsInVec.erase(newEnd, numsInVec.end());

    cout << "After removing odd numbers: ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    return 0;
}

为什么每次调完remove() 都要调用erase() ？

因为remove() 函数中，在遍历时，它遍历一个范围内的元素。对于所有不等于你要移除的值的元素，它会 把它们移到范围的前面 。它返回一个迭代器，指向新的“逻辑上”的末尾。这个迭代器后面的元素是“垃圾”，它们仍然在容器中，但它们的值是不确定的，也不再属于有效序列。然后使用容器的 erase() 成员函数，它负责根据第一步返回的迭代器，真正地从容器中删除后面的元素，并调整容器大小。这一步是特定于容器的，所以很高效， 因为它只需要知道一个起点，就可以批量删除。

替换值以及替换满足给定条件的元素

STL算法 replace() 与 replace_if() 分别用于替换集合中等于指定值和满足给定条件的元素。 replace() 根据比较运算符==的返回值来替换元素：

cout << "Using 'std::replace' to replace value 5 by 8" << endl;
replace (numsInVec.begin (), numsInVec.end (), 5, 8);

replace_if( )需要一个用户指定的一元谓词，对于要替换的每个值，该谓词都返回 true：

cout << "Using 'std::replace_if' to replace even values by -1" << endl;
replace_if (numsInVec.begin (), numsInVec.end (),
 [](int element) {return ((element % 2) == 0); }, -1); 

使用示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numsInVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    cout << "Original Vector: ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    // Replace value 5 with 8
    replace(numsInVec.begin(), numsInVec.end(), 5, 8);

    cout << "After replacing 5 with 8: ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    // Replace even values with -1
    replace_if(numsInVec.begin(), numsInVec.end(),
               [](int element) { return (element % 2) == 0; }, -1);

    cout << "After replacing even values with -1: ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    return 0;
}

排序，有序搜索，去重

进行排序，可使用 STL 算法 sort( )：

sort (numsInVec.begin (), numsInVec.end ()); // ascending order

这个版本的 sort( )将 std::less<>用作二元谓词，而该谓词使用 vector 存储的数据类型实现的运算符<。您可使用另一个重载版本，以指定谓词，从而修改排列顺序：

sort (numsInVec.begin (), numsInVec.end (),
 [](int lhs, int rhs) {return (lhs > rhs);} ); // descending order

同样，在显示集合的内容前，需要删除重复的元素。要删除相邻的重复值，可使用 unique( )：

auto newEnd = unique (numsInVec.begin (), numsInVec.end ());
numsInVec.erase (newEnd, numsInVec.end ()); // to resize

要进行快速查找，可使用 STL 算法 binary_search( )，这种算法只能用于有序容器：

bool elementFound = binary_search (numsInVec.begin (), numsInVec.end (), 2011);
if (elementFound)
 cout << "Element found in the vector!" << endl; 

使用实例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
    vector<int> numsInVec = {5, 3, 8, 1, 2, 2, 7, 4, 6, 5, 5};

    cout << "Original Vector: ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    // Sort the vector in ascending order
    sort(numsInVec.begin(), numsInVec.end());

    cout << "Sorted Vector (Ascending): ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    // Remove duplicates
    auto newEnd = unique(numsInVec.begin(), numsInVec.end());
    numsInVec.erase(newEnd, numsInVec.end());

    cout << "After removing duplicates: ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    // Search for an element
    bool elementFound = binary_search(numsInVec.begin(), numsInVec.end(), 4);
    if (elementFound)
        cout << "Element 4 found in the vector!" << endl;
    else
        cout << "Element 4 not found in the vector!" << endl;

    return 0;
}

请注意，与 remove() 一样， unique() 也不调整容器的大小。它将元素前移，但不会减少元素总数。为避免容器末尾包含不想要或未知的值，务必在调用 unique() 后调用 vector::erase() ，并将 unique() 返回的迭代器传递给它。

binary_search( )算法只能用于经过排序的容器，如果将其用于未经排序的 vector，结果可能出乎意料。

stable_sort( )的用法与 sort( )类似，这在前面介绍过。stable_sort( )确保排序后元素的相对顺序保持不变。为了确保相对顺序保持不变，将降低性能，这是一个需要考虑的因素，尤其在元素的相对顺序不重要时。

将范围分区

std::partition() 将输入范围分为两部分：一部分满足一元谓词；另一部分不满足：

bool IsEven (const int& num) // unary predicate
{ 
 return ((num % 2) == 0);
}
...
partition (numsInVec.begin(), numsInVec.end(), IsEven);

然而，std::partition( ) 不保证每个分区中元素的相对顺序不变。在相对顺序很重要，需要保持不变时，应使用 std::stable_partition( ) ：

stable_partition (numsInVec.begin(), numsInVec.end(), IsEven);

使用举例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numsInVec = {5, 3, 8, 1, 2, 2, 7, 4, 6, 5, 5, 9};
    vector<int> vecCopy(numsInVec);

    cout << "Original vector numsInVec: ";
    for (const auto &num : numsInVec)
    {
        cout << num << " ";
    }
    cout << endl;

    cout << "Partitioned vector numsInVec: ";
    auto partitionedEnd = partition(numsInVec.begin(), numsInVec.end(), [](const int &a)
                                    { return ((a % 2) == 0); });

    cout << "Partition Left size: " << distance(numsInVec.begin(), partitionedEnd) << endl;
    cout << "Partition Right size: " << distance(partitionedEnd, numsInVec.end()) << endl;

    for (auto it = numsInVec.cbegin(); it != numsInVec.cend(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;

    cout << "Stable Partitioned vector vecCopy: ";
    stable_partition(vecCopy.begin(), vecCopy.end(), [](const int &a)
                     { return ((a % 2) == 0); });

    for (auto it = vecCopy.cbegin(); it != vecCopy.cend(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

partition() 会返回一个迭代器，指向第一个不满足谓词的元素。就这个例子来说，其指向的就是 1 这个元素。

          丅
6 4 8 2 2 1 7 3 5 5 5 9 

stable_partition() 可以保证元素分区后相对位置不变，其速度比 partition() 慢，因此应只在容器中元素的相对顺序很重要时使用它。

在有序集合中插入元素

将元素插入到有序集合中时，将其插入到正确位置很重要。为了满足这种需求，STL 提供了 std::lower_bound( ) 和 std::upper_bound( ) 等函数：

auto minInsertPos = lower_bound (names.begin(), names.end(),
 "Brad Pitt");
// alternatively:
auto maxInsertPos = upper_bound (names.begin(), names.end(),
 "Brad Pitt");

lower_bound() 和 upper_bound() 都返回一个迭代器，分别指向在不破坏现有顺序的情况下，元素可插入到有序范围内的最前位置和最后位置。

例如，要将 2 插入到1222345中，lower_bound() 会返回指向第一个 2 的迭代器，而 upper_bound() 会返回指向 3 的迭代器。

使用举例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numsInVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Insert an element while maintaining order
    int elementToInsert = 5;
    auto insertPos = lower_bound(numsInVec.begin(), numsInVec.end(), elementToInsert);

    numsInVec.insert(insertPos, elementToInsert);

    cout << "After inserting " << elementToInsert << ": ";
    for (const auto &num : numsInVec)
        cout << num << " ";
    cout << endl;

    return 0;
}

STL 算法小结

• 使用算法 remove() 、remove_if() 或 unique() 后，务必使用容器的成员方法 erase() 调整容器的大小。
• 调用 unique() 删除重复的相邻值之前，别忘了使用 sort() 对容器进行排序。sort() 确保包含相同值的元素彼此相邻，这样 unique() 才能发挥作用。
• 使用 find() 、find_if() 、search() 或 search_n() 返回的迭代器之前，务必将其与容器的 end() 进行比较，以确定它有效。如果迭代器等于 end() ，则表示未找到元素。
• 仅当元素的相对顺序很重要时，才应使用 stable_partition() （而不是 partition() ）和 stable_sort() （而不是 sort() ），因为 stable_* 可能降低应用程序的性能。
• 对于已排序的容器，不要在随机选择的位置插入元素，而应将其插入到 lower_bound() 或 upper_bound() 返回的位置，以确保插入元素后容器依然是有序的。
• 别忘了，binary_search() 只能用于已排序的容器。

栈与队列

栈是 LIFO（后进先出）系统，只能从栈顶插入或删除元素。栈的操作包括 push() （插入）和 pop() （删除）。要使用 std::stack，必须包含头文件 <stack> 。

队列是 FIFO（先进先出）系统，只能从队头删除元素，从队尾插入元素。队列的操作包括 enqueue() （插入）和 dequeue() （删除）。要使用 std::queue，必须包含头文件<queue> 。

栈的使用

在有些 STL 实现中，std::stack 的定义如下：

template <
 class elementType,
 class Container=deque<Type>
> class stack;

参数 elementType 是 stack 存储的对象类型。第二个模板参数 Container 是 stack 使用的默认底层容器实现类。stack 默认在内部使用 std::deque 来存储数据，但 可指定使用 vector 或 list 来存储数据 。因此，实例化整型栈的代码类似于下面这样：

std::stack <int> numsInStack;

要创建存储类（如 Tuna）对象的栈，可使用下述代码：

std::stack <Tuna> tunasInStack;

要创建使用不同底层容器的栈，可使用如下代码：

std::stack <double, vector <double>> doublesStackedInVec; 

各种实例化方式：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main()
{
    // Stack of integers using default deque container
    stack<int> intStack;

    // Stack of strings using default deque container
    stack<string> stringStack;

    // Stack of doubles using vector as the underlying container
    stack<double, vector<double>> doubleStack;

    // initializing one stack to be a copy of another
    stack<int> intStackTwo(intStack);

    return 0;
}

stack常用成员函数

stack 改变了另一种容器（如 deque、list 或 vector）的行为，通过 限制元素插入或删除的方式 实现其功能，从而提供严格遵守栈机制的行为特征。

成员函数	说明
empty()	如果栈为空，返回 true；否则返回 false。
size()	返回栈中元素的数量。
top()	返回栈顶元素的引用。
push(const Type& x)	将元素 x 插入到栈顶。
pop()	删除栈顶元素。

使用举例：

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> numsInStack;

    // Push elements onto the stack
    for (int i = 1; i <= 5; ++i)
    {
        numsInStack.push(i);
        cout << "Pushed: " << i << ", Stack size: " << numsInStack.size() << endl;
    }

    // Access and pop elements from the stack
    while (!numsInStack.empty())
    {
        cout << "Top element: " << numsInStack.top() << endl;
        numsInStack.pop();
        cout << "Popped, Stack size: " << numsInStack.size() << endl;
    }

    return 0;
}

queue队列的使用

STL queue 是一个模板类，要使用它，必须包含头文件。queue 是一个泛型类，只允许在末尾插入元素以及从开头删除元素。queue 不允许访问中间的元素，但可以访问开头和末尾的元素。从这种意义上说，std::queue 的行为与超市收银台前的队列极其相似。

std::queue 的定义如下：

template <
 class elementType,
 class Container = deque<Type>
> class queue;

其中 elementType 是 queue 对象包含的元素的类型。Container 是 std::queue 用于存储其数据的集合类型，可将该模板参数设置为 std::list、vector 或 deque，默认为 deque。

实例化整型 queue 的最简单方式如下：

std::queue <int> numsInQ;

如果要创建这样的 queue，即其元素类型为 double，并使用 std::list（而不是默认的 queue）存储这些元素，可以像下面这样做：

std::queue <double, list <double>> dblsInQInList;

与 stack 一样，也可使用一个 queue 来实例化另一个 queue：

std::queue<int> copyQ(numsInQ);

queue常用成员函数

有以下这些成员函数：

成员函数	说明
empty()	如果队列为空，返回 true；否则返回 false。
size()	返回队列中元素的数量。
front()	返回队列头元素的引用。
back()	返回队列尾元素的引用。
push(const Type& x)	将元素 x 插入到队列尾。
pop()	删除队列头元素。

使用举例：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> numsInQ;

    // Enqueue elements into the queue
    for (int i = 1; i <= 5; ++i)
    {
        numsInQ.push(i);
        cout << "Enqueued: " << i << ", Queue size: " << numsInQ.size() << endl;
    }

    // Access and dequeue elements from the queue
    while (!numsInQ.empty())
    {
        cout << "Front element: " << numsInQ.front() << endl;
        numsInQ.pop();
        cout << "Dequeued, Queue size: " << numsInQ.size() << endl;
    }

    return 0;
}

priority_queue优先级队列

std::priority_queue 是一个特殊类型的队列，它允许你按照优先级来处理元素。它的行为类似于一个最大堆（max-heap），即每次从队列中取出的元素都是当前队列中最大的元素。你可以使用 std::priority_queue 来实现优先队列，例如任务调度、事件处理等。

std::priority_queue 类的定义如下：

template <
 class elementType,
 class Container=vector<Type>,
 class Compare=less<typename Container::value_type>
>
class priority_queue

其中 elementType 是一个模板参数，指定了优先级队列将包含的元素的类型。第二个模板参数指定 priority_queue 在内部将使用哪个集合类来存储数据，第三个参数让程序员能够指定一个二元谓词，以帮助队列判断哪个元素应位于队首。如果没有指定二元谓词，priority_queue 类将默认使用 std::less，它使用运算符<比较对象。

要实例化整型 priority_queue，最简单的方式如下：

std::priority_queue <int> numsInPrioQ;

如果要创建一个这样的 priority_queue，即其元素类型为 double，且按小到大的顺序存储在 std::deque中，则可这样做：

priority_queue <int, deque <int>, greater <int>> numsInDescendingQ;

与 stack 一样，也可使用一个 priority_queue 来实例化另一个 priority_queue：

std::priority_queue <int> copyQ(numsInPrioQ); 

priority_queue常用成员函数

有以下这些成员函数：

成员函数	说明
empty()	如果队列为空，返回 true；否则返回 false。
size()	返回队列中元素的数量。
top()	返回队列头元素的引用。
push(const Type& x)	将元素 x 插入到队列尾。
pop()	删除队列头元素。

使用举例：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    priority_queue<int> pq;

    vector<int> vec = {5, 1, 3, 2, 4};

    for (int num : vec)
    {
        pq.push(num);
    }

    while (!pq.empty())
    {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}

按照51324的顺序插入之后，使用top获取后弹出，打印顺序为54321。可以得知，priority_queue 默认实例里，每次取出的元素都是当前队列中最大的元素。

使用谓词 std::greater <int> 实例化一个 priority_queue。该谓词导致优先级队列认为包含的数字最小的元素为最大的元素，并将其放在队首。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int>> pq;

    vector<int> vec = {5, 1, 3, 2, 4};

    for (int num : vec)
    {
        pq.push(num);
    }

    while (!pq.empty())
    {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}