1059 lines
29 KiB
Markdown
1059 lines
29 KiB
Markdown
# 类
|
||
|
||
## 类的概念及简单应用
|
||
|
||
1. [官方文档解释](https://zh.cppreference.com/w/cpp/language/classes)
|
||
|
||
1. > 比较复杂，有些东西用不到，想要深入了解时可以自行学习
|
||
> 
|
||
>
|
||
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)
|
||
|
||
|
||
## 迭代器(Iterator)
|
||
|
||
1. [官方解释](https://zh.cppreference.com/w/cpp/iterator)
|
||
|
||
2. 说白了，迭代器就是经过抽象化的指针
|
||
|
||
```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, ...)`**: 并行排序容器中的元素。
|