算法基础导读（C++）
前言
数据结构与算法
- 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
- 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
- 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。
C++语法概要
C 语言为 C++子集，因此 C 语言涉及的语法部分将不再说明
C++标准格式
#include <iostream> //标准输入输出流 头文件引入
using namespace std; //开辟命名空间
int main(){
//程序内容
return 0; //程序顺利运行
}常用头文件
容器、算法、迭代器等高级用法暂不引入
#include <bits/stdc++.h> //C++万能标准头文件
#include <cstdio> //C风格输入输出
#include <iostream> //标准输入输出流
#include <iomanip> //输入输出流格式化
#include <sstream> //字符串流
输入输出流
cout<<"字符串"<<'\n'; //endl等效'\n'
cout<<"字符串"<<endl; //输出流
cin>>""; //输入流
cerr<<""<<endl; //错误流
clog<<""<<endl: //日志流
存储类
存储类定义 C++ 程序中变量/函数的范围（可见性）和生命周期。这些说明符放置在它们所修饰的类型之前。下面列出 C++ 程序中可用的存储类：
- auto：这是默认的存储类说明符，通常可以省略不写。auto 指定的变量具有自动存储期，即它们的生命周期仅限于定义它们的块（block）。auto 变量通常在栈上分配。
- register：用于建议编译器将变量存储在 CPU 寄存器中以提高访问速度。在 C++11 及以后的版本中，register 已经是一个废弃的特性，不再具有实际作用。
- static：用于定义具有静态存储期的变量或函数，它们的生命周期贯穿整个程序的运行期。在函数内部，static 变量的值在函数调用之间保持不变。在文件内部或全局作用域，static 变量具有内部链接，只能在定义它们的文件中访问。
- extern：用于声明具有外部链接的变量或函数，它们可以在多个文件之间共享。默认情况下，全局变量和函数具有 extern 存储类。在一个文件中使用 extern 声明另一个文件中定义的全局变量或函数，可以实现跨文件共享。
#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;
}引用与指针
区别
引用很容易与指针混淆，它们之间有三个主要的不同：
- 不存在空引用。引用必须连接到一块合法的内存。
- 一旦引用被初始化为一个对象，就不能被指向到另一个对象。指针可以在任何时候指向到另一个对象。
- 引用必须在创建时被初始化。指针可以在任何时间被初始化。
int var = 26; // 实际变量的声明
// 指针
int *ip; // 指针变量的声明
ip = &var; // 在指针变量中存储 var 的地址
// 引用
int& a = var; // 引用变量 var
创建引用
变量名称是变量附属在内存位置中的标签，可以把引用当成是变量附属在内存位置中的第二个标签。因此，我们可以通过原始变量名称或引用来访问变量的内容。例如：
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）的一部分，提供了灵活的接口和高效的操作。
基本特性
- 动态大小：vector 的大小可以根据需要自动增长和缩小。
- 连续存储：vector 中的元素在内存中是连续存储的，这使得访问元素非常快速。
- 可迭代：vector 可以被迭代，你可以使用循环（如 for 循环）来访问它的元素。
- 元素类型：vector 可以存储
任何类型的元素，包括内置类型、对象、指针等。
使用场景
- 当你需要一个可以动态增长和缩小的数组时。
- 当你需要频繁地在序列的末尾添加或移除元素时。
- 当你需要一个可以高效随机访问元素的容器时。
- 要使用 vector，首先需要包含
头文件：
#include <vector>创建 Vector
创建一个 vector 可以像创建其他变量一样简单：
std::vector<int> myVector; // 创建一个存储整数的空 vector
这将创建一个空的整数向量,也可以在创建时指定初始大小和初始值：
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 中添加元素：
myVector.push_back(7); // 将整数 7 添加到 vector 的末尾
访问元素
可以使用下标操作符 [] 或 at() 方法访问 vector 中的元素：
int x = myVector[0]; // 获取第一个元素
int y = myVector.at(1); // 获取第二个元素
获取大小
可以使用 size() 方法获取 vector 中元素的数量：
int size = myVector.size(); // 获取 vector 中的元素数量
迭代访问
可以使用迭代器遍历 vector 中的元素：
for (auto it = myVector.begin(); it != myVector.end(); ++it) {
std::cout << *it << " ";
}或者使用范围循环：
for (int element : myVector) {
std::cout << element << " ";
}删除元素
可以使用 erase() 方法删除 vector 中的元素：
myVector.erase(myVector.begin() + 2); // 删除第三个元素
清空 Vector
可以使用 clear() 方法清空 vector 中的所有元素：
myVector.clear(); // 清空 vector
实例
#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
是 C++ 标准模板库（STL）中的一个序列容器，它允许在容器的任意位置快速插入和删除元素。与数组或向量（
不需要在创建时指定大小，并且可以在任何位置添加或删除元素，而不需要重新分配内存。
语法
//引用头文件
#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)特点
双向迭代： 提供了双向迭代器，可以向前和向后遍历元素。
动态大小：与数组不同，
的大小可以动态变化，不需要预先分配固定大小的内存。
快速插入和删除：可以在列表的任何位置快速插入或删除元素，而不需要像向量那样移动大量元素。
注意事项
的元素是按插入顺序存储的，而不是按元素值排序。
由于
的元素存储在不同的内存位置，所以它不适合需要随机访问的场景。
与向量相比，
的内存使用效率较低，因为每个元素都需要额外的空间来存储指向前后元素的指针。
链表 🥨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。
常用成员函数
void push_front(const T& value) //在列表的前端插入一个元素。
void pop_front() //移除列表前端的元素。
iterator before_begin() //返回指向列表前端之前的迭代器。
iterator begin() //返回指向列表前端的迭代器。
iterator end() //返回指向列表末尾的迭代器。
队列 🍣queue
C++ 标准库中的
基本操作
empty() //检查队列是否为空。
size() //返回队列中的元素数量。
front() //返回队首元素的引用。
back() //返回队尾元素的引用。
push() //在队尾添加一个元素。
pop() //移除队首元素。
语法
在 C++ 中，队列的语法如下：
#include <queue>
// 声明队列
std::queue<Type> q;
//这里 Type 是队列中存储元素的数据类型。
栈 🍡stack
基本操作
push() //在栈顶添加一个元素。
pop() //移除栈顶元素。
top() //返回栈顶元素的引用，但不移除它。
empty() //检查栈是否为空。
size() //返回栈中元素的数量。
语法
#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 容器中的元素是按照键的顺序自动排序的，这使得它非常适合需要快速查找和有序数据的场景。
定义和特性
键值对：map 存储的是键值对，其中每个键都是唯一的。 排序：map 中的元素按照键的顺序自动排序，通常是升序。 唯一性：每个键在 map 中只能出现一次。 双向迭代器：map 提供了双向迭代器，可以向前和向后遍历元素。
基本语法
//包含头文件:
#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 使用哈希表来存储元素，这使得它在查找、插入和删除操作中具有平均常数时间复杂度。
语法
#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技术，该技术解决了传统语法中的逐行打印输出的不便，更方便用于控制台命令窗口程序的设计，对于部分赛题略有帮助。
#include<iostream>
int main()
{
std::cout<<R"(//由此开始
//批量级字符串输出
//由此结束)";
}存储类
- auto 关键字在 C++11 中用于两种情况：声明变量时根据初始化表达式自动推断该变量的类型、声明函数时函数返回值的占位符。
- mutable：用于修饰类中的成员变量，允许在 const 成员函数中修改这些变量的值。通常用于缓存或计数器等需要在 const 上下文中修改的数据。
- thread_local：用于定义具有线程局部存储期的变量，每个线程都有自己的独立副本。线程局部变量的生命周期与线程的生命周期相同。