noi_outline/senior/2.C++程序设计.md

# 类

## 类的概念及简单应用

1. [官方文档解释](https://zh.cppreference.com/w/cpp/language/classes)

   1. > 比较复杂，有些东西用不到，想要深入了解时可以自行学习
      > ![1729576522156](image/2.C++程序设计/1729576522156.png)
      >
2. 通俗的说：

   > C++类就像是“模具”，用来创建“物体”。比如，如果你要建造很多房子，先做一个房子的模具，里面规定了房子有几扇门、几扇窗户。这个模具就是“类”。每次用模具做出来的具体房子就是“对象”。
   >

   > 类里面可以有“属性”（就像房子的面积、颜色）和“方法”（像开门、关窗的操作）。通过这个类，你可以快速制造出多个相似的对象，而不用每次重新定义所有细节。
   >
3. 关于struct 与 class

   1. C++ 中 struct与class没有本质区别，只不过class中默认private,struct中默认public

## 成员函数和运算符重载

1. 程序

```cpp
#include <iostream>
#include <ostream>
#include <string>
#include <utility>

class Student{
private:
    std::string name;
    int age;
public:
    Student(const std::string &name, const int &age):name(name), age(age){ //重定义构造函数
        std::cout<<"Student "<<name<<" is constructing.\n";
    }
    Student(const Student &that){ // 模仿自动生成的拷贝构造函数
        std::cout<<"Copy constructor\n";
        this->name = that.name;
        this->age = that.age;
    }
    Student(Student&&that){//移动构造函数
        std::cout<<"Move constructor\n";
        this->name = that.name;
        this->age = that.age;
        that.name.clear();
        that.age = -1;
    }
    friend std::ostream& operator<<(std::ostream &os,const Student &s){ // 友元函数与运算符重载
        os<<"Student { name:'"<<s.name<<"', age: "<<s.age<<" }\n";
        return os;
    }
    Student operator+(const Student &that)const{ //运算符重载
        return Student(this->name+that.name, this->age+that.age);
    }
    void say_hello()const{ //打招呼，成员函数
        std::cout<<"Hello, my name is "<<this->name<<" .\n";
    }
};

int main(){
    Student Zengtudor("Zengtudor",18);//构造函数
    Zengtudor.say_hello();//成员函数
    Student Alice("Alice",18);//构造函数
    Student fake_Zengtudor = Zengtudor;//拷贝构造函数
    Student new_Zengtudor = std::move(Zengtudor);//移动构造函数，数据移动到新的，销毁旧的
    std::cout<<Alice;//友元函数，运算符重载
    std::cout<<Alice+new_Zengtudor;//运算符重载+
}
```

2. 输出

```
Student Zengtudor is constructing.
Hello, my name is Zengtudor .
Student Alice is constructing.
Copy constructor
Move constructor
Student { name:'Alice', age: 18 }
Student AliceZengtudor is constructing.
Student { name:'AliceZengtudor', age: 36 }
```

# STL模板

## 容器(container)

1. [官方解释](https://zh.cppreference.com/w/cpp/container)
   ![1729578565293](image/2.C++程序设计/1729578565293.png)

## 迭代器(Iterator)

1. [官方解释](https://zh.cppreference.com/w/cpp/iterator)
   ![1729579349732](image/2.C++程序设计/1729579349732.png)
2. 说白了，迭代器就是经过抽象化的指针
   ![1729579725048](image/2.C++程序设计/1729579725048.png)
```cpp
#include <iostream>
#include <set>

#define NV(v)#v<<" :\t"<<(v)
int main(){
    std::set<int> s;
    s.insert({1,2,3});
    auto it = s.find(2);
    std::cout<<NV(*s.begin())<<'\n';
    // std::cout<<*s.end()<<'\n'; 注意不可以访问end
    std::cout<<NV(*s.rbegin())<<'\n';//访问末尾的正确方式
    std::cout<<NV(*it)<<'\n';
    std::cout<<NV(*--it)<<'\n';
    std::cout<<NV(*(++ ++it))<<'\n';
}
```
>输出
```
*s.begin() :    1
*s.rbegin() :   3
*it :   2
*--it : 1
*(++ ++it) :    3
```

## 对(pair)

>在C++中，`std::pair` 是一个模板类，可以将两个数据组合成一个单一的对象，常用于需要将两个相关的数据项捆绑在一起的时候，例如键值对、坐标对等。下面是`std::pair`的重点用法：

### 1. 定义和初始化
`std::pair` 可以通过多种方式进行初始化：

```cpp
#include <iostream>
#include <utility>

int main() {
    // 直接构造
    std::pair<int, std::string> p1(1, "apple");
    
    // 使用make_pair构造（推荐）
    auto p2 = std::make_pair(2, "banana");
    
    // 列表初始化（C++11及之后）
    std::pair<int, double> p3 = {3, 4.5};
    
    // 复制构造
    std::pair<int, std::string> p4 = p1;
    
    std::cout << p1.first << ", " << p1.second << std::endl;
    std::cout << p2.first << ", " << p2.second << std::endl;
    std::cout << p3.first << ", " << p3.second << std::endl;
    std::cout << p4.first << ", " << p4.second << std::endl;

    return 0;
}
```

### 2. 成员变量
`std::pair`有两个公开的成员变量：

- `first`：存储第一个数据
- `second`：存储第二个数据

使用示例：

```cpp
std::pair<int, std::string> p = {10, "hello"};
std::cout << p.first << std::endl;  // 输出 10
std::cout << p.second << std::endl; // 输出 hello
```

### 3. 使用`std::make_pair`
`std::make_pair` 可以自动推导类型，简化构造`std::pair`的过程：

```cpp
auto p = std::make_pair(42, "example");
std::cout << p.first << ", " << p.second << std::endl;
```

### 4. 比较操作
`std::pair` 支持字典序比较，即先比较 `first`，如果 `first` 相等，则再比较 `second`：

```cpp
std::pair<int, int> p1 = {1, 5};
std::pair<int, int> p2 = {1, 10};

if (p1 < p2) {
    std::cout << "p1 is less than p2" << std::endl;
}
```

上面的代码中，`p1 < p2` 是 `true`，因为 `1 == 1`，然后 `5 < 10`。

### 5. 作为容器的元素
`std::pair` 可以用于标准容器（如`std::vector`, `std::map`）中。例如，`std::map` 的键值对本质上就是 `std::pair`：

```cpp
#include <map>

std::map<int, std::string> m;
m.insert(std::make_pair(1, "one"));
m[2] = "two";

for (const auto& item : m) {
    std::cout << item.first << " -> " << item.second << std::endl;
}
```

### 6. 结构化绑定（C++17）
在C++17中，可以使用结构化绑定直接从 `std::pair` 中解构出两个值：

```cpp
auto [id, name] = std::make_pair(3, "C++");
std::cout << id << ", " << name << std::endl;
```

### 7. 应用场景
`std::pair` 主要用于以下场景：
- 返回多个值：如果函数需要返回多个值，可以使用 `std::pair`。
- 键值对：在 `std::map` 中使用。
- 组合相关的数据：如坐标 `(x, y)`、范围 `(start, end)`等。

### 示例：使用`std::pair`返回多个值

```cpp
std::pair<int, int> getMinMax(const std::vector<int>& nums) {
    int min = *std::min_element(nums.begin(), nums.end());
    int max = *std::max_element(nums.begin(), nums.end());
    return {min, max};
}

int main() {
    std::vector<int> numbers = {5, 7, 2, 9, 1};
    auto [minValue, maxValue] = getMinMax(numbers);
    std::cout << "Min: " << minValue << ", Max: " << maxValue << std::endl;
}
```

在上面的例子中，`getMinMax` 函数使用 `std::pair` 返回了最小值和最大值。

## 元组(tuple)
在C++中，`std::tuple` 是一个可以包含多个不同类型元素的容器。它类似于结构体，但更灵活，因为不需要预先定义类型和数量。`std::tuple` 是在 C++11 中引入的，它在 `<tuple>` 头文件中定义。

### 1. 创建和初始化 `std::tuple`

可以使用 `std::make_tuple` 或直接构造一个 `std::tuple` 来创建：

```cpp
#include <iostream>
#include <tuple>
#include <string>

int main() {
    // 使用std::make_tuple
    auto person = std::make_tuple("Alice", 25, 1.75);

    // 直接构造一个std::tuple
    std::tuple<std::string, int, double> person2("Bob", 30, 1.80);

    return 0;
}
```

### 2. 访问 `std::tuple` 元素

可以使用 `std::get<index>` 来访问 `tuple` 的元素。需要注意的是，索引是从 `0` 开始的：

```cpp
std::string name = std::get<0>(person);
int age = std::get<1>(person);
double height = std::get<2>(person);

std::cout << "Name: " << name << ", Age: " << age << ", Height: " << height << std::endl;
```

### 3. 修改 `std::tuple` 元素

`std::get` 也可以用于修改元素的值：

```cpp
std::get<1>(person) = 26; // 将age改为26
```

### 4. 获取 `std::tuple` 的元素数量

可以使用 `std::tuple_size` 来获取 `tuple` 的元素数量：

```cpp
std::cout << "Tuple size: " << std::tuple_size<decltype(person)>::value << std::endl;
```

### 5. 使用 `std::tie` 解构 `tuple`

`std::tie` 可以将 `tuple` 的内容分解为多个变量：

```cpp
std::string name;
int age;
double height;

std::tie(name, age, height) = person;
std::cout << "Name: " << name << ", Age: " << age << ", Height: " << height << std::endl;
```

还可以忽略不需要的元素，用 `std::ignore`：

```cpp
std::tie(name, std::ignore, height) = person;
```

### 6. 比较 `std::tuple`

`std::tuple` 支持比较运算符（`==`, `!=`, `<`, `<=`, `>`, `>=`），按照字典顺序进行比较：

```cpp
std::tuple<int, int, int> t1(1, 2, 3);
std::tuple<int, int, int> t2(1, 3, 2);

if (t1 < t2) {
    std::cout << "t1 is less than t2" << std::endl;
}
```

### 7. 合并 `std::tuple`

可以使用 `std::tuple_cat` 将多个 `tuple` 合并：

```cpp
auto t1 = std::make_tuple(1, 2);
auto t2 = std::make_tuple(3.5, "hello");
auto t3 = std::tuple_cat(t1, t2);

std::cout << std::get<0>(t3) << ", " << std::get<1>(t3) << ", " 
          << std::get<2>(t3) << ", " << std::get<3>(t3) << std::endl;
```

### 8. 使用结构化绑定 (C++17)

在 C++17 中，引入了结构化绑定，可以更加方便地解构 `tuple`：

```cpp
auto [name, age, height] = person;
std::cout << "Name: " << name << ", Age: " << age << ", Height: " << height << std::endl;
```

### 总结

`std::tuple` 非常适合在需要返回多个不同类型的值、或处理不同类型的数据集合时使用。它的灵活性和便捷的接口使得它成为 C++ 中一种非常实用的工具。

## 集合(set)
`std::set` 是 C++ 标准库中的一种关联容器，主要用于存储不重复的元素，并且会自动按照元素的顺序进行排序。常见的用法包括插入、删除、查找元素等。`std::set` 的底层实现通常是基于红黑树，因此它的操作（插入、删除、查找）时间复杂度都是 O(log n)。

下面是 `std::set` 的一些基本用法和示例。

### 1. 引入头文件
要使用 `std::set`，需要包含头文件：
```cpp
#include <set>
```

### 2. 定义 `std::set`
```cpp
std::set<int> s; // 定义一个存储 int 类型元素的集合
std::set<std::string> strSet; // 定义一个存储字符串的集合
```

### 3. 插入元素
使用 `insert` 函数来插入元素。如果元素已经存在，则不会插入。
```cpp
s.insert(5);
s.insert(10);
s.insert(5); // 重复插入无效，set 中仍然只有一个 5

for (int x : s) {
    std::cout << x << " "; // 输出: 5 10
}
```

### 4. 删除元素
- `erase(value)`: 删除指定值的元素。
- `erase(iterator)`: 删除指定位置的元素。
- `erase(begin, end)`: 删除指定范围内的元素。
```cpp
s.erase(5); // 删除元素 5

auto it = s.find(10);
if (it != s.end()) {
    s.erase(it); // 删除迭代器位置上的元素 10
}
```

### 5. 查找元素
- `find(value)`: 返回一个指向找到元素的迭代器，如果找不到则返回 `end()`。
- `count(value)`: 返回元素出现的次数，对于 `set` 来说，要么是 `0` 要么是 `1`。
```cpp
if (s.find(5) != s.end()) {
    std::cout << "5 is in the set" << std::endl;
}

if (s.count(10) > 0) {
    std::cout << "10 is in the set" << std::endl;
}
```

### 6. 大小与清空
- `size()`: 返回集合中元素的个数。
- `empty()`: 判断集合是否为空。
- `clear()`: 清空集合中的所有元素。
```cpp
std::cout << "Size: " << s.size() << std::endl; // 输出集合的大小

if (!s.empty()) {
    std::cout << "The set is not empty." << std::endl;
}

s.clear(); // 清空集合
```

### 7. 遍历 `std::set`
可以使用迭代器或者基于范围的 for 循环进行遍历。
```cpp
for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";
}

// 或者
for (const auto &x : s) {
    std::cout << x << " ";
}
```

### 8. 自定义排序规则
默认情况下，`std::set` 按照元素的 `<` 运算符排序。如果需要自定义排序规则，可以使用比较函数或仿函数。
```cpp
// 降序排序
std::set<int, std::greater<int>> s_desc;
s_desc.insert(3);
s_desc.insert(1);
s_desc.insert(2);

for (int x : s_desc) {
    std::cout << x << " "; // 输出: 3 2 1
}
```

### 9. 其它常用操作
- `lower_bound(value)`: 返回第一个大于或等于 `value` 的迭代器。
- `upper_bound(value)`: 返回第一个大于 `value` 的迭代器。
```cpp
s.insert(1);
s.insert(3);
s.insert(5);

auto lb = s.lower_bound(3); // 指向 3
auto ub = s.upper_bound(3); // 指向 5
```

### 示例代码
```cpp
#include <iostream>
#include <set>

int main() {
    std::set<int> s;

    // 插入元素
    s.insert(1);
    s.insert(5);
    s.insert(3);

    // 遍历集合
    for (int x : s) {
        std::cout << x << " "; // 输出: 1 3 5
    }
    std::cout << std::endl;

    // 查找元素
    if (s.find(3) != s.end()) {
        std::cout << "Found 3" << std::endl;
    }

    // 删除元素
    s.erase(3);

    // 检查大小
    std::cout << "Size: " << s.size() << std::endl;

    return 0;
}
```
## 多重集合(multiset)
`std::multiset` 是 C++ 标准库中的一个容器，用于存储可以重复的元素，且元素会自动按照特定的顺序排列。`std::multiset` 是一个关联容器，底层通常使用红黑树实现，因此支持高效的插入、删除和查找操作。

### 主要特性

1. **元素可以重复**：与 `std::set` 不同，`std::multiset` 允许插入重复元素。
2. **自动排序**：插入的元素会根据给定的比较函数（默认是 `operator<`）自动排序。
3. **性能**：查找、插入和删除操作的平均时间复杂度为 O(log n)。

### 常用操作

以下是一些 `std::multiset` 的常用操作：

1. **包含头文件**：
   ```cpp
   #include <set>
   ```

2. **定义和初始化**：
   ```cpp
   std::multiset<int> ms;  // 定义一个整型的multiset
   std::multiset<int> ms2 = {1, 2, 2, 3, 4};  // 初始化
   ```

3. **插入元素**：
   ```cpp
   ms.insert(5);
   ms.insert(3);
   ms.insert(3);  // 允许重复
   ```

4. **删除元素**：
   ```cpp
   ms.erase(3);  // 删除一个值为3的元素，若存在多个3，删除一个
   ```

5. **查找元素**：
   ```cpp
   auto it = ms.find(2);  // 查找值为2的元素
   if (it != ms.end()) {
       std::cout << "Found: " << *it << std::endl;
   }
   ```

6. **计数元素**：
   ```cpp
   size_t count = ms.count(2);  // 计数值为2的元素个数
   ```

7. **遍历元素**：
   ```cpp
   for (const auto& val : ms) {
       std::cout << val << " ";
   }
   ```

8. **大小和清空**：
   ```cpp
   std::cout << "Size: " << ms.size() << std::endl;  // 返回元素个数
   ms.clear();  // 清空multiset
   ```

### 示例代码

以下是一个使用 `std::multiset` 的简单示例：

```cpp
#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // 插入元素
    ms.insert(5);
    ms.insert(3);
    ms.insert(3);
    ms.insert(7);
    ms.insert(1);

    // 遍历元素
    std::cout << "Elements in multiset: ";
    for (const auto& val : ms) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = ms.find(3);
    if (it != ms.end()) {
        std::cout << "Found: " << *it << std::endl;
    }

    // 计数
    std::cout << "Count of 3: " << ms.count(3) << std::endl;

    // 删除元素
    ms.erase(3);  // 删除一个3
    std::cout << "After erasing one 3, elements: ";
    for (const auto& val : ms) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}
```
## 双端队列(deque)
`deque`（双端队列）是C++标准库中提供的一种序列容器，它支持从两端高效地插入和删除元素。与`vector`不同，`deque`允许在头部和尾部都进行高效的操作，适合需要频繁在两端插入和删除的场景。

### 1. 引入头文件
使用`deque`之前，需要包含头文件：
```cpp
#include <deque>
```

### 2. 创建`deque`
可以使用默认构造函数或指定初始值来创建一个`deque`：
```cpp
std::deque<int> dq; // 创建一个空的 deque
std::deque<int> dq2(5, 10); // 创建一个包含5个10的 deque
```

### 3. 常用操作
以下是一些常用的`deque`操作：

#### 3.1 插入元素
- 在头部插入元素：`push_front()`
- 在尾部插入元素：`push_back()`

```cpp
dq.push_front(1); // 在头部插入 1
dq.push_back(2);  // 在尾部插入 2
```

#### 3.2 删除元素
- 从头部删除元素：`pop_front()`
- 从尾部删除元素：`pop_back()`

```cpp
dq.pop_front(); // 删除头部元素
dq.pop_back();  // 删除尾部元素
```

#### 3.3 访问元素
- 使用下标访问元素：`operator[]`
- 使用 `at()` 方法安全访问元素
- 使用 `front()` 和 `back()` 访问头尾元素

```cpp
int first = dq.front(); // 获取头部元素
int last = dq.back();   // 获取尾部元素
int second = dq[1];     // 获取第二个元素
```

#### 3.4 大小和容量
- `size()` 获取元素个数
- `empty()` 判断是否为空

```cpp
size_t size = dq.size(); // 获取 deque 的大小
bool isEmpty = dq.empty(); // 判断 deque 是否为空
```

#### 3.5 清空容器
- 使用 `clear()` 清空所有元素

```cpp
dq.clear(); // 清空 deque
```

### 4. 示例代码
下面是一个完整的示例，演示如何使用`deque`：

```cpp
#include <iostream>
#include <deque>

int main() {
    // 创建一个双端队列并添加元素
    std::deque<int> dq;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(5);
    
    // 输出当前元素
    std::cout << "当前 deque 元素: ";
    for (const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 删除头部和尾部元素
    dq.pop_front(); // 删除 5
    dq.pop_back();  // 删除 20

    std::cout << "删除后 deque 元素: ";
    for (const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 访问头尾元素
    std::cout << "头部元素: " << dq.front() << std::endl;
    std::cout << "尾部元素: " << dq.back() << std::endl;

    return 0;
}
```

### 5. 注意事项
- `deque`的底层实现使其在插入和删除时比`vector`更高效，但在随机访问时可能比`vector`慢。
- `deque`适合用作队列和栈，支持高效的插入和删除操作。
## 优先队列(priority_queue)
在 C++ 中，`priority_queue` 是一个 STL（标准模板库）容器适配器，用于管理优先队列。优先队列是一种特殊类型的队列，其中每个元素都有一个优先级。优先级较高的元素会被优先处理，而不是按照它们被添加的顺序。

### 基本特性

1. **元素顺序**：在 `priority_queue` 中，元素会根据优先级进行排序。默认情况下，优先级最高的元素位于队列的顶部（即最前面），并且可以快速访问和移除。

2. **底层容器**：`priority_queue` 通常使用堆（heap）作为其底层数据结构，默认是最大堆（max heap）。这意味着最大元素总是位于队列的顶部。

3. **模板类**：`priority_queue` 是一个模板类，可以与任意类型的元素一起使用，但需要提供比较函数来确定优先级。

### 基本操作

以下是 `priority_queue` 的一些基本操作和用法：

- **定义优先队列**：
  
  ```cpp
  #include <queue>
  #include <vector>
  #include <iostream>

  std::priority_queue<int> pq; // 默认最大堆
  ```

- **添加元素**：
  
  ```cpp
  pq.push(10);
  pq.push(5);
  pq.push(20);
  ```

- **访问顶部元素**：

  ```cpp
  std::cout << "Top element: " << pq.top() << std::endl; // 输出 20
  ```

- **移除顶部元素**：

  ```cpp
  pq.pop(); // 移除 20
  ```

- **检查是否为空**：

  ```cpp
  if (!pq.empty()) {
      std::cout << "Queue is not empty" << std::endl;
  }
  ```

- **获取队列大小**：

  ```cpp
  std::cout << "Size of queue: " << pq.size() << std::endl;
  ```

### 自定义比较

如果你想创建一个最小堆（即优先级最低的元素在顶部），可以使用自定义比较函数。下面是一个示例：

```cpp
#include <queue>
#include <vector>
#include <iostream>

struct Compare {
    bool operator()(int a, int b) {
        return a > b; // 小的优先
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);

    std::cout << "Top element (min-heap): " << minHeap.top() << std::endl; // 输出 5

    return 0;
}
```
## 映射(map)
`std::map` 是 C++ 标准库中的一个关联容器，它提供了一种基于键-值对存储数据的方式。`std::map` 内部实现通常是平衡二叉树（例如红黑树），这使得它在插入、删除和查找操作上具有对数时间复杂度。下面是一些关于 `std::map` 的基本用法和特性：

### 1. 基本特性

- **键唯一性**：每个键在 `std::map` 中都是唯一的。如果插入一个已经存在的键，旧的值将被新值覆盖。
- **有序性**：`std::map` 中的元素是按照键的顺序排列的，默认情况下使用 `<` 运算符进行比较。
- **支持自定义比较**：可以通过提供自定义比较器来定义排序方式。

### 2. 常用操作

以下是一些常用的操作及示例代码：

#### 2.1 包含头文件

```cpp
#include <iostream>
#include <map>
```

#### 2.2 创建和初始化

```cpp
std::map<std::string, int> myMap;  // 键为字符串，值为整数

// 初始化
std::map<std::string, int> myMap = {
    {"apple", 2},
    {"banana", 3},
    {"orange", 5}
};
```

#### 2.3 插入元素

```cpp
myMap["grape"] = 4;  // 插入新元素
myMap.insert({"pear", 1});  // 使用 insert 方法插入
```

#### 2.4 查找元素

```cpp
auto it = myMap.find("banana");  // 查找键为 "banana" 的元素
if (it != myMap.end()) {
    std::cout << "Found banana: " << it->second << std::endl;  // 输出对应的值
} else {
    std::cout << "Banana not found!" << std::endl;
}
```

#### 2.5 删除元素

```cpp
myMap.erase("apple");  // 删除键为 "apple" 的元素
```

#### 2.6 遍历元素

```cpp
for (const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << std::endl;  // 输出每个键值对
}
```

#### 2.7 其他常用操作

- **获取大小**：`myMap.size()` 返回元素个数。
- **检查是否为空**：`myMap.empty()` 检查 `map` 是否为空。

### 3. 示例代码

以下是一个完整的示例代码，展示了 `std::map` 的基本用法：

```cpp
#include <iostream>
#include <map>

int main() {
    // 创建一个 map
    std::map<std::string, int> myMap;

    // 插入元素
    myMap["apple"] = 2;
    myMap["banana"] = 3;
    myMap["orange"] = 5;

    // 查找元素
    auto it = myMap.find("banana");
    if (it != myMap.end()) {
        std::cout << "Found banana: " << it->second << std::endl;
    }

    // 遍历元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 删除元素
    myMap.erase("apple");

    // 检查大小
    std::cout << "Size: " << myMap.size() << std::endl;

    return 0;
}
```
## 多重映射(multimap)
`std::multimap` 是 C++ STL（标准模板库）中的一个关联容器，用于存储键值对，其中一个键可以对应多个值。与 `std::map` 不同，`std::multimap` 允许相同的键多次出现，因此适合需要重复键的场景。

### 主要特点

1. **存储键值对**：`std::multimap` 存储的是 `std::pair<const Key, Value>` 类型的数据。
2. **自动排序**：插入的元素会根据键自动排序，默认是升序排列。
3. **键的重复性**：相同的键可以多次插入。
4. **性能**：插入、删除、查找操作的时间复杂度是 O(log n)。

### 常用操作

以下是 `std::multimap` 的一些常用操作：

- **定义和初始化**：
  ```cpp
  #include <iostream>
  #include <map>

  std::multimap<int, std::string> mmap;
  mmap.insert(std::make_pair(1, "apple"));
  mmap.insert(std::make_pair(1, "banana"));
  mmap.insert(std::make_pair(2, "cherry"));
  ```

- **遍历**：
  ```cpp
  for (const auto& pair : mmap) {
      std::cout << pair.first << ": " << pair.second << std::endl;
  }
  ```

- **查找元素**：
  ```cpp
  auto range = mmap.equal_range(1); // 获取所有键为1的元素
  for (auto it = range.first; it != range.second; ++it) {
      std::cout << it->second << std::endl; // 输出 apple 和 banana
  }
  ```

- **删除元素**：
  ```cpp
  mmap.erase(1); // 删除所有键为1的元素
  ```

### 示例代码

以下是一个完整的示例代码，展示 `std::multimap` 的基本用法：

```cpp
#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mmap;

    // 插入元素
    mmap.insert(std::make_pair(1, "apple"));
    mmap.insert(std::make_pair(1, "banana"));
    mmap.insert(std::make_pair(2, "cherry"));
    mmap.insert(std::make_pair(3, "date"));
    
    // 遍历并打印元素
    std::cout << "Multimap elements:" << std::endl;
    for (const auto& pair : mmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找特定键的所有值
    std::cout << "\nValues with key 1:" << std::endl;
    auto range = mmap.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl; // 输出 apple 和 banana
    }

    // 删除键为1的所有元素
    mmap.erase(1);

    // 打印删除后的元素
    std::cout << "\nAfter erasing key 1:" << std::endl;
    for (const auto& pair : mmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
```

### 注意事项

- **键的唯一性**：虽然同一个键可以有多个值，但键本身在容器中仍然是唯一的。
- **性能**：对于需要频繁插入和删除的场景，`std::multimap` 提供了相对较高的性能，但在需要大量查找时，`std::unordered_multimap`（基于哈希表实现）可能会提供更好的性能。
## 算法模板库中的常用函数
C++ STL（标准模板库）中提供了丰富的算法函数，这些算法函数可以极大地简化编程任务并提高代码的可读性和效率。以下是一些常用且实用的算法函数，按类别进行分类：

### 1. **排序和排列算法**
- **`std::sort`**: 对容器中的元素进行排序，支持自定义比较函数。
  ```cpp
  std::vector<int> vec = {5, 2, 9, 1};
  std::sort(vec.begin(), vec.end());
  ```
  
- **`std::stable_sort`**: 稳定排序，保持相等元素的相对顺序。
  
- **`std::partial_sort`**: 对部分元素进行排序，前n个元素会被排好序。

- **`std::next_permutation`**: 生成下一个字典序排列。

### 2. **查找算法**
- **`std::find`**: 在容器中查找特定值。
  ```cpp
  auto it = std::find(vec.begin(), vec.end(), 2);
  ```

- **`std::binary_search`**: 在已排序的容器中查找某个值，使用二分查找，时间复杂度为O(log n)。

- **`std::lower_bound`** 和 **`std::upper_bound`**: 在已排序容器中查找第一个不小于（或大于）给定值的元素位置。

### 3. **修改算法**
- **`std::copy`**: 将元素从一个容器复制到另一个容器。
  
- **`std::transform`**: 对容器中的每个元素应用给定的函数，并将结果存储到另一个容器。
  ```cpp
  std::vector<int> squares;
  std::transform(vec.begin(), vec.end(), std::back_inserter(squares), [](int x) { return x * x; });
  ```

- **`std::remove`**: 移除容器中的特定元素，实际上是标记，需结合 `erase` 使用。
  
- **`std::fill`**: 将指定值填充到容器的元素中。

### 4. **集合算法**
- **`std::set_union`**: 计算两个集合的并集。

- **`std::set_intersection`**: 计算两个集合的交集。

- **`std::set_difference`**: 计算两个集合的差集。

- **`std::set_symmetric_difference`**: 计算两个集合的对称差集。

### 5. **数值算法**
- **`std::accumulate`**: 对容器中的元素进行累加（或其他二元操作）。
  ```cpp
  int sum = std::accumulate(vec.begin(), vec.end(), 0);
  ```

- **`std::inner_product`**: 计算两个容器元素的内积。

- **`std::adjacent_difference`**: 计算相邻元素的差。

### 6. **其他常用算法**
- **`std::for_each`**: 对容器中的每个元素应用给定的操作。
  
- **`std::count`**: 统计容器中某个值的出现次数。
  
- **`std::all_of`, `std::any_of`, `std::none_of`**: 检查容器中是否所有、任意或没有元素满足特定条件。

### 7. **并行算法（C++17及以上）**
- **`std::for_each(std::execution::par, ...)`**: 在并行执行上下文中对元素进行操作。
  
- **`std::sort(std::execution::par, ...)`**: 并行排序容器中的元素。