# 算法基础导读（C++）


# 前言

{{< note info flat >}}
学习算法的前提是掌握至少一门编程语言，并对其语法和数据结构做到了如指掌，建议读者有 C 语言和基本的数据结构基础。
{{< /note >}}

# 数据结构与算法

- 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
- 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
- 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。

# C++语法概要

C 语言为 C++子集，因此 C 语言涉及的语法部分将不再说明

## C++标准格式

```C++
#include <iostream>  //标准输入输出流 头文件引入
using namespace std; //开辟命名空间
int main(){
						//程序内容
	return 0;			//程序顺利运行
}
```

## 常用头文件

容器、算法、迭代器等高级用法暂不引入

```C++
#include <bits/stdc++.h> //C++万能标准头文件
#include <cstdio> 	 //C风格输入输出
#include <iostream>  //标准输入输出流
#include <iomanip>   //输入输出流格式化
#include <sstream>   //字符串流
```

## 输入输出流

```C++
cout<<"字符串"<<'\n';		//endl等效'\n'
cout<<"字符串"<<endl;		//输出流
cin>>"";					//输入流
cerr<<""<<endl;				//错误流
clog<<""<<endl:				//日志流
```

## 存储类

存储类定义 C++ 程序中变量/函数的范围（可见性）和生命周期。这些说明符放置在它们所修饰的类型之前。下面列出 C++ 程序中可用的存储类：

1. auto：这是默认的存储类说明符，通常可以省略不写。auto 指定的变量具有自动存储期，即它们的生命周期仅限于定义它们的块（block）。auto 变量通常在栈上分配。
2. register：用于建议编译器将变量存储在 CPU 寄存器中以提高访问速度。在 C++11 及以后的版本中，register 已经是一个废弃的特性，不再具有实际作用。
3. static：用于定义具有静态存储期的变量或函数，它们的生命周期贯穿整个程序的运行期。在函数内部，static 变量的值在函数调用之间保持不变。在文件内部或全局作用域，static 变量具有内部链接，只能在定义它们的文件中访问。
4. extern：用于声明具有外部链接的变量或函数，它们可以在多个文件之间共享。默认情况下，全局变量和函数具有 extern 存储类。在一个文件中使用 extern 声明另一个文件中定义的全局变量或函数，可以实现跨文件共享。

```C++
#include <iostream>
// 全局变量，具有外部链接，默认存储类为extern
int globalVar;
void function() {
    // 局部变量，具有自动存储期，默认存储类为auto
    auto int localVar = 10;
    // 静态变量，具有静态存储期，生命周期贯穿整个程序
    static int staticVar = 20;
    const int constVar = 30; // const变量默认具有static存储期
    // 尝试修改const变量，编译错误
    // constVar = 40;
    // mutable成员变量，可以在const成员函数中修改
    class MyClass {
    public:
        mutable int mutableVar;
        void constMemberFunc() const {
            mutableVar = 50; // 允许修改mutable成员变量
        }
    };
    // 线程局部变量，每个线程有自己的独立副本
    thread_local int threadVar = 60;
}
int main() {
    extern int externalVar; // 声明具有外部链接的变量
    function();
    return 0;
}
```

## 引用与指针

### 区别

引用很容易与指针混淆，它们之间有三个主要的不同：

1. 不存在空引用。引用必须连接到一块合法的内存。
2. 一旦引用被初始化为一个对象，就不能被指向到另一个对象。指针可以在任何时候指向到另一个对象。
3. 引用必须在创建时被初始化。指针可以在任何时间被初始化。

```C++
int var = 26;    // 实际变量的声明
// 指针
int  *ip;        // 指针变量的声明
ip = &var;       // 在指针变量中存储 var 的地址
// 引用
int&  a = var;   // 引用变量 var
```

### 创建引用

变量名称是变量附属在内存位置中的标签，可以把引用当成是变量附属在内存位置中的第二个标签。因此，我们可以通过原始变量名称或引用来访问变量的内容。例如：

```C++
int i = 17;
// 我们可以为 i 声明引用变量，如下所示：
int&  r = i;
double& s = d;
```

在这些声明中，& 读作引用。因此，第一个声明可以读作 "r 是一个初始化为 i 的整型引用"，第二个声明可以读作 "s 是一个初始化为 d 的 double 型引用"。

# C++数据结构

## vector 容器

C++ 中的 vector 是一种序列容器，它允许你在运行时动态地插入和删除元素。
vector 是基于数组的数据结构，但它可以自动管理内存，这意味着你不需要手动分配和释放内存。
与 C++ 数组相比，vector 具有更多的灵活性和功能，使其成为 C++ 中常用的数据结构之一。
vector 是 C++ 标准模板库（STL）的一部分，提供了灵活的接口和高效的操作。

### 基本特性

1. 动态大小：vector 的大小可以根据需要自动增长和缩小。
2. 连续存储：vector 中的元素在内存中是连续存储的，这使得访问元素非常快速。
3. 可迭代：vector 可以被迭代，你可以使用循环（如 for 循环）来访问它的元素。
4. 元素类型：vector 可以存储`任何类型`的元素，包括内置类型、对象、指针等。

### 使用场景

1. 当你需要一个可以动态增长和缩小的数组时。
2. 当你需要频繁地在序列的末尾添加或移除元素时。
3. 当你需要一个可以高效随机访问元素的容器时。
4. 要使用 vector，首先需要包含 <vector> 头文件：

```C++
#include <vector>
```

### 创建 Vector

创建一个 vector 可以像创建其他变量一样简单：

```C++
std::vector<int> myVector; // 创建一个存储整数的空 vector
```

这将创建一个空的整数向量,也可以在创建时指定初始大小和初始值：

```C++
std::vector<int> myVector(5); // 创建一个包含 5 个整数的 vector，每个值都为默认值（0）
std::vector<int> myVector(5, 10); // 创建一个包含 5 个整数的 vector，每个值都为 10
// 或：
std::vector<int> vec; // 默认初始化一个空的 vector
std::vector<int> vec2 = {1, 2, 3, 4}; // 初始化一个包含元素的 vector
```

### 添加元素

可以使用 push_back 方法向 vector 中添加元素：

```C++
myVector.push_back(7); // 将整数 7 添加到 vector 的末尾
```

### 访问元素

可以使用下标操作符 [] 或 at() 方法访问 vector 中的元素：

```C++
int x = myVector[0]; // 获取第一个元素
int y = myVector.at(1); // 获取第二个元素
```

### 获取大小

可以使用 size() 方法获取 vector 中元素的数量：

```C++
int size = myVector.size(); // 获取 vector 中的元素数量
```

### 迭代访问

可以使用迭代器遍历 vector 中的元素：

```C++
for (auto it = myVector.begin(); it != myVector.end(); ++it) {
    std::cout << *it << " ";
}
```

或者使用范围循环：

```C++
for (int element : myVector) {
    std::cout << element << " ";
}
```

### 删除元素

可以使用 erase() 方法删除 vector 中的元素：

```C++
myVector.erase(myVector.begin() + 2); // 删除第三个元素
```

### 清空 Vector

可以使用 clear() 方法清空 vector 中的所有元素：

```C++
myVector.clear(); // 清空 vector
```

### 实例

```C++
#include <iostream>
#include <vector>
int main() {
    // 创建一个空的整数向量
    std::vector<int> myVector;
    // 添加元素到向量中
    myVector.push_back(3);
    myVector.push_back(7);
    myVector.push_back(11);
    myVector.push_back(5);
    // 访问向量中的元素并输出
    std::cout << "Elements in the vector: ";
    for (int element : myVector) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
    // 访问向量中的第一个元素并输出
    std::cout << "First element: " << myVector[0] << std::endl;
    // 访问向量中的第二个元素并输出
    std::cout << "Second element: " << myVector.at(1) << std::endl;
    // 获取向量的大小并输出
    std::cout << "Size of the vector: " << myVector.size() << std::endl;
    // 删除向量中的第三个元素
    myVector.erase(myVector.begin() + 2);
    // 输出删除元素后的向量
    std::cout << "Elements in the vector after erasing: ";
    for (int element : myVector) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
    // 清空向量并输出
    myVector.clear();
    std::cout << "Size of the vector after clearing: " << myVector.size() << std::endl;
    return 0;
}
```

## 顺序表 🥖list

<list> 是 C++ 标准模板库（STL）中的一个序列容器，它允许在容器的任意位置快速插入和删除元素。与数组或向量（<vector>）不同，<list> 不需要在创建时指定大小，并且可以在任何位置添加或删除元素，而不需要重新分配内存。

### 语法

```C++
//引用头文件
#include <list>
//声明列表，其中 T 是存储在列表中的元素类型。
std::list<T> mylist;
//插入元素
mylist.push_back(value);
//删除元素
mylist.pop_back(); 或 mylist.erase(iterator);
//访问元素
mylist.front(); 和 mylist.back();
//遍历遍历列表：使用迭代器
for (auto it = mylist.begin(); it != mylist.end(); ++it)
```

### 特点

双向迭代：<list> 提供了双向迭代器，可以向前和向后遍历元素。
动态大小：与数组不同，<list> 的大小可以动态变化，不需要预先分配固定大小的内存。
快速插入和删除：可以在列表的任何位置快速插入或删除元素，而不需要像向量那样移动大量元素。

### 注意事项

<list> 的元素是按插入顺序存储的，而不是按元素值排序。
由于 <list> 的元素存储在不同的内存位置，所以它不适合需要随机访问的场景。
与向量相比，<list> 的内存使用效率较低，因为每个元素都需要额外的空间来存储指向前后元素的指针。

## 链表 🥨forward_list

与双向链表（std::list）不同，std::forward_list 只支持单向遍历。它适用于需要频繁进行前向遍历和插入、删除操作的场景。以下是对 std::forward_list 的详细说明：

- 单向链表：
  std::forward_list 是单向链表，只能从前往后遍历，不能反向遍历。
  由于其单向链表的结构，插入和删除操作在已知位置的情况下非常高效（O(1) 复杂度）。
- 低内存开销：
  与 std::list 相比，std::forward_list 只需要一个指向下一个节点的指针，节省了内存。
- 不支持随机访问：
  不支持通过索引访问元素，不能使用 operator[] 或 at 方法，只能通过迭代器进行访问。

### 构造函数

std::forward_list 提供了多种构造函数，包括：
默认构造函数：创建一个空的 forward_list。
带初始值的构造函数：创建一个包含给定初始值的 forward_list。
带范围的构造函数：创建一个包含指定范围内元素的 forward_list。

### 常用成员函数

```C++
void push_front(const T& value)  //在列表的前端插入一个元素。
void pop_front()                 //移除列表前端的元素。
iterator before_begin()          //返回指向列表前端之前的迭代器。
iterator begin()                 //返回指向列表前端的迭代器。
iterator end()                   //返回指向列表末尾的迭代器。
```

## 队列 🍣queue

C++ 标准库中的 <queue> 头文件提供了队列（Queue）数据结构的实现。队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。

### 基本操作

```C++
empty()     //检查队列是否为空。
size()      //返回队列中的元素数量。
front()     //返回队首元素的引用。
back()      //返回队尾元素的引用。
push()      //在队尾添加一个元素。
pop()       //移除队首元素。
```

### 语法

在 C++ 中，队列的语法如下：

```C++
#include <queue>
// 声明队列
std::queue<Type> q;
//这里 Type 是队列中存储元素的数据类型。
```

## 栈 🍡stack

<stack> 是 C++ 标准模板库（STL）的一部分，它实现了一个后进先出（LIFO，Last In First Out）的数据结构。这种数据结构非常适合于需要"最后添加的元素最先被移除"的场景。
<stack> 容器适配器提供了一个栈的接口，它基于其他容器（如 deque 或 vector）来实现。栈的元素是线性排列的，但只允许在一端（栈顶）进行添加和移除操作。

### 基本操作

```C++
push()      //在栈顶添加一个元素。
pop()       //移除栈顶元素。
top()       //返回栈顶元素的引用，但不移除它。
empty()     //检查栈是否为空。
size()      //返回栈中元素的数量。
```

### 语法

```C++
#include <iostream>
#include <stack>
int main() {
    std::stack<int> s;
    // 向栈中添加元素
    s.push(1);
    s.push(2);
    s.push(3);
    // 访问栈顶元素
    std::cout << "Top element is: " << s.top() << std::endl;
    // 移除栈顶元素
    s.pop();
    std::cout << "After popping, top element is: " << s.top() << std::endl;
    // 检查栈是否为空
    if (!s.empty()) {
        std::cout << "Stack is not empty." << std::endl;
    }
    // 打印栈的大小
    std::cout << "Size of stack: " << s.size() << std::endl;
    return 0;
}
```

## 红黑树 🍬map

在 C++ 中，<map> 是标准模板库（STL）的一部分，它提供了一种关联容器，用于存储键值对（key-value pairs）。

map 容器中的元素是按照键的顺序自动排序的，这使得它非常适合需要快速查找和有序数据的场景。

### 定义和特性

键值对：map 存储的是键值对，其中每个键都是唯一的。
排序：map 中的元素按照键的顺序自动排序，通常是升序。
唯一性：每个键在 map 中只能出现一次。
双向迭代器：map 提供了双向迭代器，可以向前和向后遍历元素。

### 基本语法

```C++
//包含头文件:
#include <map>
//声明 map 容器:
std::map<key_type, value_type> myMap;
key_type //是键的类型。
value_type //是值的类型。
//插入元素:
myMap[key] = value;
//访问元素:
value = myMap[key];
//遍历 map:
for (std::map<key_type, value_type>::iterator it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << it->first << " => " << it->second << std::endl;
}
```

## 哈希表 🍨unordered_map

在 C++ 中，<unordered_map> 是标准模板库（STL）的一部分，提供了一种基于哈希表的键值对容器。

### 定义和特性

与 std::map 不同，unordered_map 不保证元素的排序，但通常提供更快的查找速度。
unordered_map 是一个关联容器，它存储了键值对（key-value pairs），其中每个键（key）都是唯一的。unordered_map 使用哈希表来存储元素，这使得它在查找、插入和删除操作中具有平均常数时间复杂度。

### 语法

```C++
#include <unordered_map>
std::unordered_map<key_type, value_type> map_name;
key_type //是键的类型。
value_type //是值的类型。
//构造函数
unordered_map //可以以多种方式构造：
// 默认构造
std::unordered_map<int, std::string> myMap;
// 构造并初始化
std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}};
// 构造并指定初始容量
std::unordered_map<int, std::string> myMap(10);
// 构造并复制另一个 unordered_map
std::unordered_map<int, std::string> anotherMap = myMap;
基本操作
//插入元素:
myMap.insert({3, "three"});
//访问元素:
std::string value = myMap[1]; // 获取键为1的值
//删除元素:
myMap.erase(1); // 删除键为1的元素
//查找元素:
auto it = myMap.find(2); // 查找键为2的元素
if (it != myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
}
```

# C++11 和 C++17 特性

## raw string literal 技术

在第三代 C++标准中，引入了`raw string literal`技术，该技术解决了传统语法中的逐行打印输出的不便，更方便用于控制台命令窗口程序的设计，对于部分赛题略有帮助。

```C++
#include<iostream>
int main()
{
    std::cout<<R"(//由此开始
		//批量级字符串输出
	//由此结束)";
}
```

## 存储类

1. auto 关键字在 C++11 中用于两种情况：声明变量时根据初始化表达式自动推断该变量的类型、声明函数时函数返回值的占位符。
2. mutable：用于修饰类中的成员变量，允许在 const 成员函数中修改这些变量的值。通常用于缓存或计数器等需要在 const 上下文中修改的数据。
3. thread_local：用于定义具有线程局部存储期的变量，每个线程都有自己的独立副本。线程局部变量的生命周期与线程的生命周期相同。

# 致谢

{{< note default flat >}}
本文参考于：[头歌实践：C&C++程序设计（国防科大）](https://www.educoder.net/paths/co8zyp75) [哔哩哔哩：王道计算机考研 数据结构](https://www.bilibili.com/video/BV1b7411N798)
{{< /note >}}