程序基础：数据类型、变量、输入与输出、运算符与表达式、程序结构、数组、函数、字符串、结构体、指针、类和对象。 以上内容参见PPT图。

数据结构

• 1.容器 vector 、 pair 、 set 、 map

• 4.链表、list

• 5.栈、队列

算法

• 2.高精度计算

• 3.排序

• 6.分治

• 7.贪心

【1.数据结构——容器】

在C++标准库中，有多种容器（containers）可供使用，每种容器都有其特定的用途和特性。以下是一些主要的C++容器及其简要描述：

• std::vector ：动态数组，支持快速随机访问元素，但在元素插入或删除时（特别是在中间位置）可能需要移动大量元素。

• std::array ：固定大小的数组，与C风格的数组类似，但提供了更安全和方便的方法来访问和修改元素。

• std::deque （双端队列）：支持在序列的两端进行快速插入和删除操作的容器。

• std::list ：双向链表，支持在任何位置进行快速插入和删除操作，但不支持快速随机访问元素。

• std::forward_list ：单向链表，同样支持在任何位置进行快速插入和删除操作，但只能从头部进行迭代。

• std::set ：包含唯一元素的集合，元素自动按升序排序。

• std::multiset ：与std::set类似，但允许包含重复的元素。

• std::map ：关联容器，它包含可以重复的键值对（key-value pairs），其中键（key）是唯一的，并自动按升序排序。

• std::multimap ：与std::map类似，但允许包含具有相同键的多个元素。

• std::unordered_set ：与std::set类似，但它不保证元素的排序，而是通过哈希表来存储元素，从而提供了更快速的查找性能。

• std::unordered_multiset ：与std::unordered_set类似，但允许包含重复的元素。

• std::unordered_map ：与std::map类似，但它不保证键的排序，并通过哈希表来存储键值对，从而提供了更快速的查找性能。

• std::unordered_multimap ：与std::unordered_map类似，但允许包含具有相同键的多个元素。

• std::stack ：后进先出（LIFO）的容器适配器，它基于另一个底层容器（如std::deque或std::vector）实现。

• std::queue ：先进先出（FIFO）的容器适配器，它基于另一个底层容器（如std::deque或std::list）实现。

• std::priority_queue ：优先队列，它包含可以重复的元素，并且每个元素都有一个优先级。元素按优先级顺序出队，默认情况下，最高优先级的元素最先出队。它通常基于std::vector或std::deque实现，并使用std::less（或提供的比较函数）来比较优先级。

每种容器都有其特定的用途和性能特性，因此在选择容器时，你应该考虑你的具体需求，如元素的数量、是否需要排序、是否需要快速随机访问等。

【数据对： pair】

pair 是一个模板类，它表示一个包含两个元素的固定大小的异种容器。这两个元素可以是不同的类型，通常被称为 first 和 second。pair 可用于将两个可能不同类型的值组合成一个独立的单元。

1.包含头文件

1
#include <utility>

2.创建pair对象：

xxxxxxxxxx
4
1
pair<int , string>aPair //创建了一个数据对 aPair
2
pair<int , string>bPair = {2 , ”b”};        //创建并使用列表初始化一个数据对bPair
3
pair<int , string>cPair {3 , ”c”};      //不要“=”，在声明时就初始化
4
dPair=make_pair(4,"d"); //使用make_pair()函数创建

3.给数据对赋值

xxxxxxxxxx
2
1
aPair.first=1;
2
aPair.second=”a”;

想要更多的数据对，可以用数据或array来存储pair 以数组为例： 4.创建一个pair数组：

xxxxxxxxxx
1
1
pair<int , string>ar[10]    //10个pair元素的数组

5.初始化赋值

xxxxxxxxxx
3
1
ar[0].first = 3;
2
ar[0].second = "three";
3
ar[1] = pair<int , string>(2 , "two");

6.pair应用举例

NOI / 1.10编程基础之简单排序 01:谁考了第k名 描述 在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。 输入 第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。 其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。 输出 输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩） 样例输入 5 3 90788001 67.8 90788002 90.3 90788003 61 90788004 68.4 90788005 73.9 样例输出 90788004 68.4

解题思路： 1.每个学生有两个数据，可以选用 pair数据对 来存数据。 2.用 sort() 函数对数据对排序，sort()默认按第一个元素排，这里可以把数据对的first存为成绩，second存为学号。 3.输出第k个*/

参考代码：

xxxxxxxxxx
15
1
#include<iostream>
2
#include<algorithm>
3
using namespace std;
4
pair<float,int>stu[100];//第一个是成绩，第二个是学号 
5
int main() {
6
    int n,m;
7
    cin>>n>>m;
8
    for(int i=0;i<n;i++){
9
        //输入时，先输second学号 后输入first成绩
10
        cin>>stu[i].second>>stu[i].first; 
11
    }
12
    sort(stu,stu+n);//此时的sort()是默认升序排序
13
    //所以输出时是倒数第m个：stu[n-m]
14
    cout<<stu[n-m].second<<" "<<stu[n-m].first;
15
}

【动态数组： vector】

概念：类模板中的一种顺序容器，是一种动态数组，它可以根据需要增长或缩小。 性质： 动态大小：vector的大小不是固定的，它可以在运行时增长或缩小。 连续存储：vector的元素在内存中连续存储，这意味着可以通过指针算术快速访问任意元素。 自动管理内存：vector自动管理其内部元素的内存分配和释放，从而减少了内存泄漏和重复释放的风险。 随机访问迭代器：vector提供随机访问迭代器，允许在常数时间内访问任何元素（通过索引）。 插入和删除：虽然vector在元素末尾插入和删除的效率非常高（通常为常数时间），但在中间插入或删除元素可能需要移动其他元素，因此效率较低（通常为线性时间）。 用途： 动态数组：vector最常用的用途是作为动态数组，用于存储可变数量的同类型元素。 算法和数据结构：vector可以与C++标准库中的算法结合使用，以实现各种数据结构和算法，如排序、搜索和图形算法。 与其他容器的交互：vector可以与其他容器（如set、map等）进行交互，例如将vector中的元素插入到另一个容器中，或从另一个容器中复制元素到vector中。

声明一个动态数组：

xxxxxxxxxx
2
1
vector<int> vi; //不指定个数，可以使用vi.push_back(1); 向vi中添加元素（数字1）
2
vector<int> vi(5);  //指定个数

使用说明： 1.要使用vector对象，必须包含头文件。 2.vector包含在名称空间std中，所以需要加 using namespace std; 或 vector。 3.模板使用不同的语法来指出它存储的数据类型。 如：vector<int> vi; //声明vi是一个vector对象，是一个存储整数的动态数组。 4.vector类使用不同的语法来指定元素个数。 如：vector<int> vi(5); //vi可以存5个int型元素。

vector的常用用法：

1.包含头文件

xxxxxxxxxx
1
1
#include <vector>

2.创建vector

xxxxxxxxxx
4
1
vector<int> vec; // 创建一个空的int类型的
2
vector<int> vec(10); // 创建一个包含10个元素的vector，所有元素初始化为0
3
vector<int> vec(10, 5); // 创建一个包含10个元素的vector，所有元素初始化为5
4
vector<int> vec1 = {1, 2, 3, 4, 5}; // 使用初始化列表创建ector

3.访问元素

使用下标操作符[]或at()成员函数访问元素。注意，at()成员函数会检查索引是否越界，如果越界会出错（抛出out_of_range异常）。

xxxxxxxxxx
4
1
cppint first = vec[0]; // 访问第一个元素
2
int last = vec.back(); // 访问最后一个元素
3
int second_to_last = vec[vec.size() - 2]; // 访问倒数第二个元素
4
int value_at_index = vec.at(index); // 使用at()成员函数访问元素

4.修改元素

使用下标操作符[]直接修改元素。

xxxxxxxxxx
1
1
vec[0] = 100; // 修改第一个元素为100

5.添加元素

使用push_back()成员函数在vector的末尾添加元素。

xxxxxxxxxx
1
1
vec.push_back(10); // 在vector末尾添加元素10

6.删除元素

• 使用pop_back()成员函数删除vector的最后一个元素。

xxxxxxxxxx
1
1
vec.pop_back(); // 删除vector的最后一个元素

• 使用erase()成员函数删除指定位置的元素或一段连续的元素。

xxxxxxxxxx
2
1
vec.erase(vec.begin()); // 删除第一个元素
2
vec.erase(vec.begin() + 2, vec.begin() + 5); // 删除从第三个元素开始的三个元素

7.遍历vector

可以使用范围for循环、迭代器或传统for循环遍历vector。

xxxxxxxxxx
12
1
// 使用范围for循环
2
for (int value : vec) {    
3
    // 循环体
4
}
5
// 使用迭代器，什么是迭代器：请参见后面迭代器部分内容
6
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
7
    // 循环体
8
}
9
// 使用传统for循环
10
for (size_t i = 0; i < vec.size(); ++i) { 
11
    // 循环体
12
}

8.获取vector的大小

使用size()成员函数获取vector中元素的数量。

xxxxxxxxxx
1
1
cppsize_t size = vec.size(); // 获取vector的大小

9.判断vector是否为空

使用empty()成员函数检查vector是否为空。

xxxxxxxxxx
1
1
cppif (vec.empty()) {    // vector为空}

10.清空vector

使用clear()成员函数删除vector中的所有元素。

xxxxxxxxxx
1
1
cppvec.clear(); // 清空vector

11.vector的容量和预留空间

• 使用capacity()成员函数获取vector的当前容量（即在不重新分配内存的情况下可以容纳的元素数量）。

• 使用reserve()成员函数预留额外的内存空间。这可以提高向vector中添加元素的性能，因为它减少了重新分配内存的次数。

xxxxxxxxxx
2
1
cppsize_t capacity = vec.capacity(); // 获取vector的容量
2
vec.reserve(100); // 预留100个元素的内存空间

12.vector的插入和赋值

• 使用insert()成员函数在指定位置插入一个或多个元素。

• 使用assign()成员函数替换vector中的元素。

xxxxxxxxxx
3
1
cppvec.insert(vec.begin() + 2, 100); // 在第三个位置插入元素100
2
vec.insert(vec.begin() + 2, 3, 200); // 在第三个位置插入三个元素200
3
vec.assign(10, 300); // 将vector替换为包含10个元素300的vector

例程序：vector

​x
1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
int main() {
5
// 声明一个空的int型向量
6
    vector<int> vi;
7
// 向向量中添加元素
8
    vi.push_back(1);
9
    vi.push_back(2);
10
    vi.push_back(3);
11
// 遍历向量并打印元素
12
    for (int i = 0; i < vi.size(); i++) {   //vi.size()返回vi的元素个数
13
        cout << vi[i] << ' ';
14
    }   //输出结果：1 2 3
15
    cout << endl;
16
// 使用范围（rang-based for loop)循环遍历向量（基于范围的for循环，vi必须是一个可迭代对象或容器，什么是可迭代对象请自行百度）
17
    for (int num : vi) {
18
        cout << num << ' ';
19
    }   //输出结果：1 2 3
20
    cout << endl;
21
// 访问特定元素
22
    cout << "第2个元素是: " << vi[1] << endl;
23
// 删除元素，删除后将后面的元素移前来
24
    vi.erase(vi.begin() + 1); // 删除第二个元素，vi.erase(迭代器)删除
25
// 再次遍历并打印元素
26
    for (int num : vi) {
27
        cout << num << ' '; //输出结果：1 3
28
    }
29
    cout << endl;
30

31
return 0;
32

33
}

输出结果： 1 2 3 1 2 3 第2个元素是: 2 1 3

在vector中存储pair: pair经常与vector一起使用，特别是vector中存储两种不同类型的数据对时。可以创建一个vector，其中每个元素都是一个pair。这样，就可以同时存储和访问两种类型的数据了。 例程序：vector与pair的结合(一)

xxxxxxxxxx
18
1
#include <iostream>
2
#include <vector>
3
int main() {
4
    std::vector<int> v = {1, 2, 3, 4, 5};
5
    for (int i : v) {
6
        std::cout << i << " ";
7
    }
8
    std::cout << std::endl;
9

10
// 在vector中存储std::pair
11
std::vector<std::pair<int, std::string>> vp;
12
vp.push_back(std::make_pair(1, "one"));
13
vp.push_back(std::make_pair(2, "two"));
14
for (const auto& p : vp) {
15
    std::cout << "First: " << p.first << ", Second: " << p.second << std::endl;
16
}
17
return 0;
18
}

例程序：vector与pair的结合(二)

xxxxxxxxxx
28
1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
int main() {
5
    int n,w;    //数量、架子宽度 
6
    int h=0,max_h=0,sum_w=0;//h-最终高度，max_h-每层的最大高度，sum_w-每层摆件宽度之和 
7
    cin>>n>>w;
8
    vector<pair<int,int>>wh(n); //数据对动态数组{{2,1},{1,2},{1,3},{2,3},{2,2}} 
9
    //上句中指定了wh(n)数据对个数 ，可以用cin多次输入。没指定个数时用push_back()添加元素。 
10
    for(int i=0;i<n;i++){   //录入每个摆件的宽度、高度 
11
        cin>>wh[i].first>>wh[i].second; //first-宽度，second-高度 
12
    }
13
    //处理数据：
14
    // 宽度之和要小于架子宽度，每层高度取各摆件最大值 
15
    for(const auto &p:wh){  //范围循环，每次取一个数据对临时存入p 
16
        if(sum_w<=w){
17
            sum_w+=p.first;
18
            max_h=max(max_h,p.second);
19
        } 
20
        else{
21
            h+=max_h;
22
            sum_w=0;
23
        }
24
    }
25
    h+=max_h;   //加上最上层的最大高度 
26
    cout<<h;
27
    return 0;
28
}

【关联容器 set】

在C++中，set是一种关联容器，它包含唯一元素的集合。这些元素在插入时按照某种排序规则（默认为升序）自动排序。C++标准库提供了两种主要的集合类型：std::set和std::unordered_set1。

std::set：它的元素按照排序规则自动排序，并且不允许重复元素。插入、删除、查找操作的时间复杂度都是O(log n)，其中n是集合中元素的数量。std::set的元素是不可变的，一旦插入到集合中就不能修改1。

std::unordered_set：基于哈希表实现的无序集合。它的元素没有特定的顺序，并且不允许重复元素。插入、删除、查找操作的平均时间复杂度是O(1)，但在最坏情况下可能会是O(n)，其中n是集合中元素的数量。同样，std::unordered_set的元素也是不可变的1。 C++ set的应用

set容器在C++编程中有广泛的应用场景，其特性和有序性使其成为管理有序唯一数据集合的首选。使用set不仅可以提高数据处理的效率，还能在底层自动维护数据的完整性和顺序2。

以下是一些set的应用场景：处理唯一元素的有序集合

• 去重：由于set中的元素是唯一的，因此它可以用来去除数据中的重复项。例如，你可以将一组数据插入到set中，然后将set中的数据复制回原始数据结构中，从而达到去重的效果。

• 快速查找：由于set中的元素是自动排序的，因此可以使用二分查找等算法在set中快速查找元素。这使得set在处理需要频繁查找的数据集时非常有效。

• 有序存储：如果你需要存储一组需要保持有序的数据，那么set是一个很好的选择。与vector或list等顺序容器相比，set可以在插入和删除元素时自动维护数据的顺序。

需要注意的是，虽然set提供了许多便利的功能，但由于其内部实现需要额外的空间来维护元素的顺序和唯一性，因此在使用时可能会消耗更多的内存和计算资源。因此，在选择是否使用set时需要根据具体的应用场景进行权衡。

去重例程序：

xxxxxxxxxx
14
1
#include <iostream>
2
#include <set>
3
#include <vector>
4

5
int main() {
6
    std::vector<int> nums = {1, 2, 3, 2, 4, 4, 5, 1};
7
    std::set<int> unique_nums(nums.begin(), nums.end()); // 构造set时传入vector的迭代器，实现去重
8

9
for (const auto& num : unique_nums) {
10
    std::cout << num << " ";
11
}
12
std::cout << std::endl;
13
return 0;
14
}

查找例程序：

xxxxxxxxxx
15
1
#include <iostream>
2
#include <set>
3

4
int main() {
5
    std::set<int> mySet = {1, 2, 3, 4, 5};
6

7
    int toFind = 3;
8
    if (mySet.find(toFind) != mySet.end()) {
9
       std::cout << "Found " << toFind << " in the set." << std::endl;
10
    } 
11
    else {
12
       std::cout << toFind << " not found in the set." << std::endl;
13
    }    
14
    return 0;
15
}

插入与删除例程序：

xxxxxxxxxx
21
1
#include <iostream>
2
#include <set>
3

4
int main() {
5
    std::set<int> mySet = {1, 2, 3, 4, 5};
6

7
    // 插入新元素
8
    mySet.insert(6);
9
    
10
    // 删除元素
11
    mySet.erase(3);
12
    
13
    // 遍历 set 中的元素
14
    for (const auto& elem : mySet) {
15
        std::cout << elem << " ";
16
    }
17
    std::cout << std::endl;
18
    
19
    return 0;
20

21
}

应用举例：

NOI / 1.10编程基础之简单排序 09:明明的随机数描述 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。 输入 有2行，第1行为1个正整数，表示所生成的随机数的个数：N； 第2行有N个用空格隔开的正整数，为所产生的随机数。 输出 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。 样例输入 10 20 40 32 67 40 20 89 300 400 15 样例输出 8 15 20 32 40 67 89 300 400

参考代码：

xxxxxxxxxx
13
1
#include <iostream>
2
using namespace std;
3
int main(){
4
    int n,r;
5
    set<int>mm;
6
    cin>>n;
7
    for (int i = 0; i < n; ++i){
8
        cin>>r;
9
        mm.insert(r);   //插入元素 
10
    }
11
    cout<<mm.size()<<endl;  //输出大小 
12
    for(int val:mm) cout<<val<<" "; //遍历输出 
13
}

【关联容器 map】

一、map简介 map是STL（标准模板库）的一个关联容器。 可以将任何基本类型映射到任何基本类型。如int array[100]事实上就是定义了一个int型到int型的映射。 map提供一对一的数据处理，key-value键值对，其类型可以自己定义，第一个称为关键字，第二个为关键字的值。

每个键在map中都是唯一的，而与之关联的值可以是任何类型。

map内部是自动排序的 二、map的用法 必须引入包

xxxxxxxxxx
1
1
#include<map>

2.map的定义

xxxxxxxxxx
2
1
map<type1name,type2name> maps;//第一个是键的类型，第二个是值的类型
2
map<string,int> maps;

3.map容器内元素的访问 通过下标进行访问 如：maps['c']=5; 通过迭代器进行访问 map可以使用it->first来访问键，使用it->second访问值

xxxxxxxxxx
17
1
#include<map>
2
#include<iostream>
3
using namespace std;int main(){
4
   map<char,int>maps;
5
   maps['d']=10;
6
   maps['e']=20;
7
   maps['a']=30;
8
   maps['b']=40;
9
   maps['c']=50;
10
   maps['r']=60;
11
   for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
12
   {
13
       cout<<it->first<<" "<<it->second<<endl;
14
   }
15
   return 0;
16

17
}

4.map的常用用法

xxxxxxxxxx
41
1
//插入
2
maps.insert() 
3
// 定义一个map对象
4
map<int, string> m;
5
 //用insert函数插入pair
6
m.insert(pair<int, string>(111, "kk"));
7
 // 用insert函数插入value_type数据
8
m.insert(map<int, string>::value_type(222, "pp"));
9
 // 用数组方式插入
10
m[123] = "dd";
11
m[456] = "ff";
12
maps.find() 查找一个元素
13
find(key): 返回键是key的映射的迭代器
14
map<string,int>::iterator it;
15
it=maps.find("123");
16
maps.clear()清空
17
maps.erase()删除一个元素
18
//迭代器刪除
19
it = maps.find("123");
20
maps.erase(it);
21
//关键字删除
22
int n = maps.erase("123"); //如果刪除了返回1，否则返回0
23
//用迭代器范围刪除 : 把整个map清空
24
maps.erase(maps.begin(), maps.end());
25
//等同于mapStudent.clear()
26
maps.szie()长度
27
int len=maps.size();获取到map中映射的次数
28
maps.begin()返回指向map头部的迭代器
29
maps.end()返回指向map末尾的迭代器
30
//迭代
31
map< string,int>::iterator it;
32
for(it = maps.begin(); it != maps.end(); it++)
33
    cout<<it->first<<" "<<itr->second<<endl;//输出key 和value值
34
maps.rbegin()返回指向map尾部的逆向迭代器
35
maps.rend()返回指向map头部的逆向迭代器
36
//反向迭代
37
map<string,int>::reverse_iterator it;
38
for(it = maps.rbegin(); it != maps.rend(); it++)
39
    cout<<it->first<<' '<<it->second<<endl;
40
maps.empty()判断其是否为空
41
maps.swap()交换两个map

C++：迭代器

• 什么是迭代器

• 迭代器分类

• 获取迭代器

• 什么是迭代器

C++的迭代器是一种用于遍历容器元素的对象。迭代器提供了一种通用的访问容器元素的方式，无论容器的类型和数据结构如何。通过迭代器，我们可以依次访问容器中的每个元素，对其进行读取、修改或删除操作。

使用迭代器可以极大地简化对容器元素的访问和操作，同时提高程序的灵活性和可扩展性。迭代器的使用方式类似于指针，我们可以通过迭代器来遍历容器中的每个元素，并通过迭代器进行读写操作，而不需要关心容器内部的具体实现细节。

迭代器分类 在C++中，迭代器是一种用于访问容器中的元素的对象。C++标准库中提供了多种类型的迭代器，每种迭代器都有不同的功能和特性。以下是C++中常用的迭代器类型：

输入迭代器（Input Iterator）：只能读取容器中的元素，而不能修改或重复读取。输入迭代器支持++、*、==、!=等操作符。适用于遍历容器中的元素，如std::istream_iterator。 *

xxxxxxxxxx
18
1
#include <iostream>
2
#include <iterator>
3

4
int main() {
5
    int arr[] = {1, 2, 3, 4, 5};
6
    std::istream_iterator<int> input_iter(std::cin);
7

8
    for (auto it = std::begin(arr); it != std::end(arr); ++it) {
9
        *it = *input_iter;
10
        ++input_iter;
11
    }
12

13
    for (int num : arr) {
14
        std::cout << num << " ";
15
    }
16

17
    return 0;
18
}

输出迭代器（Output Iterator）：只能写入容器中的元素，而不能读取或重复写入。输出迭代器支持++、*等操作符。适用于向容器中写入数据，如std::ostream_iterator。

xxxxxxxxxx
18
1
#include <iostream>
2
#include <iterator>
3
#include <vector>
4

5
int main() {
6
    std::vector<int> vec;
7
    std::ostream_iterator<int> output_iter(std::cout, " ");
8
    
9

10
    for (int i = 1; i <= 5; ++i) {
11
        *output_iter = i;
12
        ++output_iter;
13
        vec.push_back(i);
14
    }
15
    
16
    return 0;
17

18
}

前向迭代器（Forward Iterator）：支持读写操作，可以向前遍历容器中的元素。前向迭代器支持++、*、==、!=等操作符。适用于需要多次遍历容器中的元素，如std::forward_list。 *

xxxxxxxxxx
16
1
#include <iostream>
2
#include <forward_list>
3

4
int main() {
5
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
6
    
7

8
    auto it = flist.begin();
9
    while (it != flist.end()) {
10
        std::cout << *it << " ";
11
        ++it;
12
    }
13
    
14
    return 0;
15

16
}

双向迭代器（Bidirectional Iterator）：支持读写操作，可以向前和向后遍历容器中的元素。双向迭代器支持++、–、*、==、!=等操作符。适用于需要反向遍历容器中的元素，如std::list。

xxxxxxxxxx
16
1
#include <iostream>
2
#include <list>
3

4
int main() {
5
    std::list<int> list = {1, 2, 3, 4, 5};
6
    
7

8
    auto it = list.begin();
9
    while (it != list.end()) {
10
        std::cout << *it << " ";
11
        ++it;
12
    }
13
    
14
    return 0;
15

16
}

随机访问迭代器（Random Access Iterator）：支持读写操作，可以在常数时间内进行随机访问。随机访问迭代器支持++、–、*、[]、+、-、<、<=、>、>=等操作符。适用于需要通过下标访问容器中的元素，如std::vector和std::array。

xxxxxxxxxx
19
1
#include <iostream>
2
#include <vector>
3

4
int main() {
5
    std::vector<int> vec = {1, 2, 3, 4, 5};
6
    
7

8
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
9
        std::cout << *it << " ";
10
    }
11
    
12
    std::cout << std::endl;
13
    
14
    std::cout << "Element at index 2: " << vec[2] << std::endl;
15
    std::cout << "Element at index 4: " << *(vec.begin() + 4) << std::endl;
16
    
17
    return 0;
18

19
}

以上是C++中常见的迭代器类型及其示例。通过使用适当的迭代器类型，可以方便地对容器中的元素进行访问和操作。

以上就是迭代器常见的功能，接下来我用一张表格为大家展示迭代器的功能关系：

在C++中，可以使用不同的方法来获取迭代器，具体取决于数据结构类型。以下是获取迭代器的几种常见方式：

使用begin()和end()方法： 这是最常用的获取迭代器的方式。通过调用容器的begin()方法，可以返回指向第一个元素的迭代器；而调用end()方法则返回指向容器末尾的迭代器。例如：

xxxxxxxxxx
19
1
#include <iostream>
2
#include <vector>
3

4
int main() {
5
    std::vector<int> vec{1, 2, 3, 4, 5};
6
    
7

8
    // 使用begin()和end()方法获取迭代器
9
    auto it = vec.begin();
10
    auto end = vec.end();
11
    
12
    // 遍历容器
13
    for (; it != end; ++it) {
14
        std::cout << *it << " ";
15
    }
16
    
17
    return 0;
18

19
}

输出结果为：1 2 3 4 5

使用rbegin()和rend()方法： rbegin()方法返回指向容器最后一个元素的逆向迭代器，而rend()方法则返回指向容器开始的逆向迭代器。逆向迭代器可以从容器的末尾开始向前遍历容器。例如：

xxxxxxxxxx
19
1
#include <iostream>
2
#include <vector>
3

4
int main() {
5
    std::vector<int> vec{1, 2, 3, 4, 5};
6
    
7

8
    // 使用rbegin()和rend()方法获取逆向迭代器
9
    auto it = vec.rbegin();
10
    auto end = vec.rend();
11
    
12
    // 遍历容器
13
    for (; it != end; ++it) {
14
        std::cout << *it << " ";
15
    }
16
    
17
    return 0;
18

19
}

输出结果为：5 4 3 2 1

使用advance()方法： advance()方法允许我们在迭代器上进行偏移，以便访问容器中的其他元素。它需要两个参数，第一个是迭代器，第二个是偏移量。使用advance()方法可以在容器中跳过指定数量的元素，然后获取新位置上的迭代器。例如：

xxxxxxxxxx
20
1
#include <iostream>
2
#include <list>
3
#include <iterator>
4

5
int main() {
6
    std::list<int> lst{1, 2, 3, 4, 5};
7
    
8

9
    // 获取迭代器，并在容器中移动到第三个元素之后
10
    auto it = lst.begin();
11
    std::advance(it, 2);
12
    
13
    // 输出第三个元素之后的元素
14
    for (; it != lst.end(); ++it) {
15
        std::cout << *it << " ";
16
    }
17
    
18
    return 0;
19

20
}

输出结果为：3 4 5

使用next()和prev()方法： next()方法返回当前迭代器的下一个迭代器，prev()方法返回当前迭代器的前一个迭代器。这些方法也需要两个参数，第一个是迭代器，第二个是偏移量。它们在使用时可以更加方便，无需像advance()方法一样显式指定迭代器的类型。例如：

xxxxxxxxxx
18
1
#include <iostream>
2
#include <array>
3
#include <iterator>
4

5
int main() {
6
    std::array<int, 5> arr{1, 2, 3, 4, 5};
7
    
8

9
    // 获取第三个元素的下一个迭代器和前一个迭代器
10
    auto nextIt = std::next(arr.begin(), 2);
11
    auto prevIt = std::prev(arr.begin(), 2);
12
    
13
    // 输出第三个元素和其周围的元素
14
    std::cout << *prevIt << " " << *nextIt << std::endl;
15
    
16
    return 0;
17

18
}

输出结果为：2 4

这些是获取C++中迭代器的几种常见方式，可以根据具体的需求选择合适的方法来获取迭代器

【2.算法：高精度计算】

高精度计算通常用于处理大数的加减乘除等运算。在C++中，可以通过字符串或数组来模拟大整数的处理。

高精度加法

对于位数较大的整数的加法，使用数组来存储整数，数组的长度等于整数的位数，按照字符串的形式输入，先统计长度，然后倒置过来利用数组进位来模拟加法，最终将数组最大位置的前导0判断去除，倒序输出即为最终的结果。

大整数 输入

我们用一个数组来保存整个高精度整数，并记录高精度整数的长度len。 因为我们在模拟一个计算竖式的过程，需要从右往左读入以解决进位的问题。

xxxxxxxxxx
7
1
string num;
2
cin >> num;
3
int a[105], len = num.size(); //num.size() 取 num 字符串的长度 num.length() 也可以
4
for (int i = 0; i < len; i++) {
5
    a[i] = num[len - 1 - i] - '0';// 减去'0'是为了把字符数字变成整数数字
6
}
7
//这里的 num[len - 1 - i] 是把字符串从右向左的读取，i=0时为最右边的数。

大整数 输出

输出一个高精度的数就非常容易了，直接把数组中的元素倒序输出就可以了。

xxxxxxxxxx
3
1
for (int i = len - 1; i >= 0; i--) {
2
    cout << a[i];
3
}

高精度加高精度参考代码（多位加多位）

xxxxxxxxxx
44
1
#include <bits/stdc++.h>
2
using namespace std;
3
string num1, num2;
4
int a1[105], a2[105], len1, len2;
5
int main() {
6
    
7
    //1.输入数字字符串
8
    cin >> num1 >> num2;
9
    len1 = num1.size(); //取 num1 的长度
10
    
11
    //2.把字符串转存到数组中，存入类型为整数
12
    for (int i = 0; i < len1; i++) {
13
        a1[i] = num1[len1 - 1 - i] - '0';
14
    }
15
    len2 = num2.size();//取 num2 的长度
16
    for (int i = 0; i < len2; i++) {
17
        a2[i] = num2[len2 - 1 - i] - '0';
18
    }
19
    len1 = max(len1, len2);//取位数多的那个值做为后序处理长度
20
    
21
    //3.按位依次相加，此时不管进位问题
22
    for (int i = 0; i < len1; i++) {
23
        a1[i] += a2[i];
24
    }
25
    
26
    //4.处理进位，不包括最后一位的进位，最后一位的值可能大于10，下一步单独处理
27
    for (int i = 0; i < len1; i++) {
28
        a1[i + 1] += a1[i] / 10;
29
        a1[i] %= 10;
30
    }
31
    
32
    //5.处理最后一位的进位
33
    while (a1[len1]) {
34
        a1[len1 + 1] += a1[len1] / 10;
35
        a1[len1] %= 10;
36
        len1++;
37
    }
38
    
39
    //6.输出
40
    for (int i = len1 - 1; i >= 0; i--) {
41
        cout << a1[i];
42
    }
43
    return 0;
44
}

高精度减法

高精度减高精度参考代码（多位减多位）

xxxxxxxxxx
63
1
#include <bits/stedc++.h>
2
using namespace std;
3
string num1, num2;
4
int a1[105], a2[105], len1, len2;
5
bool sgn;   //设一个标志，判断正负
6

7
//比较两个字符串的长度，a 大返回假，b 大返回真
8
bool cmp(string a, string b) {
9
    if (a.size() != b.size()) {
10
        return a.size() < b.size();
11
    }
12
    return a < b;
13
}
14

15
int main() {
16
    cin >> num1 >> num2;
17
    
18
    //1.比较两串数字的长度，把长的放num1,短的放num2
19
    if (cmp(num1, num2)) {
20
        sgn = true;
21
        swap(num1, num2);
22
    }
23
    
24
    len1 = num1.size();     //取较长字符串的位数做为计算位数
25
    
26
    //2.转存字符串到整数数组
27
    for (int i = 0; i < len1; i++) {
28
        a1[i] = num1[len1 - 1 - i] - '0';
29
    }
30
    len2 = num2.size();
31
    for (int i = 0; i < len2; i++) {
32
        a2[i] = num2[len2 - 1 - i] - '0';
33
    }
34
    
35
    //3.按位相减，此时不管借位
36
    for (int i = 0; i < len1; i++) {
37
        a1[i] -= a2[i];
38
    }
39
    
40
    //4.处理借位
41
    for (int i = 0; i < len1; i++) {
42
        while (a1[i] < 0) {
43
            a1[i + 1]--;
44
            a1[i] += 10;
45
        }
46
    }
47
    
48
    //5.当最高位借完为0时，位数要减 1
49
    while (len1 > 1 && a1[len1 - 1] == 0) {
50
        len1--;
51
    }
52
    
53
    //按标志判断正负（本程序没处理位数相同时，相减为负的情况）
54
    if (sgn) {
55
        cout << "-";
56
    }
57
    
58
    //6.输出
59
    for (int i = len1 - 1; i >= 0; i--) {
60
        cout << a1[i];
61
    }
62
    return 0;
63
}

高精度乘法

高精度乘高精度参考代码（多位乘多位）

xxxxxxxxxx
41
1
#include <bits/stdc++.h>
2
using namespace std;
3
string num1, num2;
4
int a1[105], a2[105], len1, len2, a[205], len;
5
int main() {
6
    //1.输入并转存到数组
7
    cin >> num1 >> num2;
8
    len1 = num1.size();
9
    for (int i = 0; i < len1; i++) {
10
        a1[i] = num1[len1 - 1 - i] - '0';
11
    }
12
    len2 = num2.size();
13
    for (int i = 0; i < len2; i++) {
14
        a2[i] = num2[len2 - 1 - i] - '0';
15
    }
16
    
17
    //2.按乘法竖式依次相乘，把结果放到相应数组单元
18
    for (int i = 0; i < len1; i++) {
19
        for (int j = 0; j < len2; j++) {
20
            a[i + j] += a1[i] * a2[j];
21
        }
22
    }
23
    len = len1 + len2 - 1;//得数的基础长度为两个相乘数长度之和-1
24
    
25
    //3.处理进位
26
    for (int i = 0; i < len; i++) {
27
        a[i + 1] += a[i] / 10;
28
        a[i] %= 10;
29
    }
30
    while (a[len]) {
31
        a[len + 1] += a[len] / 10;
32
        a[len] %= 10;
33
        len++;
34
    }
35
    
36
    //4.输出
37
    for (int i = len - 1; i >= 0; i--) {
38
        cout << a[i];
39
    }
40
    return 0;
41
}

【3.算法：排序】

冒泡排序、选择排序、插入排序、桶排序、快速排序、归并排序……、

• 冒泡排序(Bubble Sort)：基础直观的排序方法，通过反复交换相邻元素将最大值逐渐“冒”到数组尾部。

• 插入排序(Insertion Sort)：逐个将元素插入已排序部分的适当位置，适合小规模数据或部分有序的数据。

• 选择排序(Selection Sort)：每次从未排序的部分找到最小（或最大）元素并放到已排序部分的末尾。

• 快速排序(Qualk Sort)：分治策略的经典应用，通常采用递归的方式，选取一个基准元素划分数组，然后对两部分分别排序。

• 归并排序(Merge Sort)：也属于分治法，将数组分成两半，独立排序后再合并。

• 堆排序(Heap Sort)：利用堆这种数据结构的特性，构建最大堆或最小堆来进行排序。

• 希尔排序(Sort)：改进版的插入排序，通过一系列间隔序列实现更高效的排序。

• 计数排序(Counting Sort)：适用于整数排序，通过统计每个元素出现的次数直接得到结果。

• 桶排序(Bucket Sort)：将元素分配到有限数量的桶里，再分别对每个桶内的元素排序。

• 基数排序(Radix Sort)：按位数从低位到高位排序，先处理最低位，再处理次低位，直到所有位都处理完毕。

各种排序方法的优缺点与应用范围：

• 冒泡排序（Bubble Sort）

  • 优点：实现简单，代码量少。

  • 缺点：性能较差，对于大规模数据排序效率低下。

  • 应用范围：适用于小规模或几乎已排序的数据。

  • 时间复杂度：最好情况下为O(n)，最坏情况下为O(n^2)。

• 插入排序（Insertion Sort）

  • 优点：对于小规模数据或基本有序的数据，性能较好。

  • 缺点：对于大规模数据排序效率低下。

  • 应用范围：适用于小规模数据。

  • 时间复杂度：最好情况下为O(n)，最坏情况下为O(n^2)。

• 选择排序（Selection Sort）

  • 优点：实现简单，不占用额外的内存空间。

  • 缺点：性能较差，对于大规模数据排序效率低下。

  • 应用范围：适用于小规模数据。

  • 时间复杂度：无论数据的初始状态如何，都需要进行n-1次比较，时间复杂度为O(n^2)。

• 快速排序（Quick Sort）

  • 优点：在平均情况下，时间复杂度为O(n log n)，效率较高。

  • 缺点：在最坏情况下，时间复杂度为O(n^2)，且空间复杂度可能较高。

  • 应用范围：适用于大规模数据排序。C++的sort函数就使用了快速排序算法。

• 归并排序（Merge Sort）

  • 优点：稳定，且时间复杂度始终为O(n log n)，无论数据的初始状态如何。

  • 缺点：空间复杂度较高，需要额外空间O(n)。

  • 应用范围：适用于需要稳定排序的场合。

• 堆排序（Heap Sort）

  • 优点：时间复杂度为O(n log n)，且空间复杂度较低。

  • 缺点：不稳定，且实现相对复杂。

  • 应用范围：适用于需要较高性能且对数据稳定性要求不高的场合。

• 其他排序算法：

  • 希尔排序（Shell Sort）：是插入排序的一种改进版本，通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

  • 计数排序（Counting Sort）、桶排序（Bucket Sort）、基数排序（Radix Sort）：这些排序算法通常用于特定类型的数据，如非负整数或具有特定分布的数据，它们的时间复杂度可以低于O(n^2)，但通常需要额外的空间。

在选择排序算法时，需要考虑数据的规模、稳定性要求、内存使用情况等因素。对于小规模或基本有序的数据，简单排序算法（如冒泡排序、插入排序、选择排序）可能足够高效。对于大规模数据，通常选择时间复杂度较低的排序算法（如快速排序、归并排序、堆排序）。如果数据具有特定分布或类型，可以考虑使用计数排序、桶排序或基数排序等算法。

1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

• 针对所有的元素重复以上的步骤，除了最后一个；

• 重复步骤1~3，直到排序完成。

1.2 动图演示

1.3 代码实现

xxxxxxxxxx
23
1
template<class T>
2
void swap(T& a, T& b) {
3
    T temp = a;
4
    a = b;
5
    b = temp;
6
}
7

8
void BubbleSort(std::vector<int>& nums, int n) {
9
    if (n <= 1) return;
10
    bool is_swap;
11
    for (int i = 1; i < n; ++i) {
12
        is_swap = false;
13
        //设定⼀个标记，若为false，则表示此次循环没有进⾏交换，也就是待排序列已经有序，排序已经完成。
14
        for (int j = 1; j < n - i + 1; ++j) {
15
            if (nums[j] < nums[j - 1]) {
16
                std::swap(nums[j], nums[j - 1]);
17
                is_swap = true;//表示有数据交换
18
            }
19
        }
20
        if (!is_swap) break;//没有数据交集，提前退出
21
    }
22
}
23

2、选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；

• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

• n-1趟结束，数组有序化了。

2.2 动图演示

2.3 代码实现

xxxxxxxxxx
21
1
template<class T>
2
void swap(T& a, T& b) {
3
    T temp = a;
4
    a = b;
5
    b = temp;
6
}
7

8
void SelectSort(std::vector<int>& nums, int n) {
9
    if (n <= 1) return;
10
    int mid;
11
    for (int i = 0; i < n - 1; ++i) {
12
        mid = i;
13
        for (int j = i + 1; j < n; ++j) {
14
            if (nums[j] < nums[mid]) {
15
                mid = j;
16
            }
17
        }
18
        std::swap(nums[mid], nums[i]);
19
    }
20
}
21

2.4 算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；

• 取出下一个元素，在已经排序的元素序列中从后向前扫描；

• 如果该元素（已排序）大于新元素，将该元素移到下一位置；

• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

• 将新元素插入到该位置后；

• 重复步骤2~5。

3.2 动图演示

3.2 代码实现

xxxxxxxxxx
16
1
template<class T>
2
void swap(T& a, T& b) {
3
    T temp = a;
4
    a = b;
5
    b = temp;
6
}
7

8
void InsertSort(std::vector<int>& nums, int n) {
9
    if (n <= 1) return;
10
    for (int i = 0; i < n; ++i) {
11
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j) {
12
            std::swap(nums[j], nums[j - 1]);
13
        }
14
    }
15
}
16

3.4 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

4、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

• 按增量序列个数k，对序列进行k 趟排序；

• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动图演示

4.3 代码实现

xxxxxxxxxx
11
1
// 希尔排序
2
void shellSort(vector<int>& nums) {
3
    for (int gap = nums.size() / 2; gap > 0; gap /= 2) {
4
        for (int i = gap; i < nums.size(); ++i) {
5
            for (int j = i; j - gap >= 0 && nums[j - gap] > nums[j]; j -= gap) {
6
                std::swap(nums[j - gap], nums[j]);
7
            }
8
        }
9
    }
10
}
11

4.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

5、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；

• 对这两个子序列分别采用归并排序；

• 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

xxxxxxxxxx
31
1
void mergeCount(int a[], int L, int mid, int R) {
2
    int* tmp = new int[L + mid + R];
3
    int i = L;
4
    int j = mid + 1;
5
    int k = 0;
6
    while (i <= mid && j <= R) {
7
        if (a[i] < a[j])
8
            tmp[k++] = a[i++];
9
        else
10
            tmp[k++] = a[j++];
11
    }
12
    ///判断哪个⼦数组中有剩余的数据
13
    while (i <= mid)
14
        tmp[k++] = a[i++];
15
    while (j <= R)
16
        tmp[k++] = a[j++];
17
    /// 将 tmp 中的数组拷⻉回 A[p...r]
18
    for (int p = 0; p < k; ++p)
19
        a[L + p] = tmp[p];
20
    delete tmp;
21
}
22
void mergeSort(int a[], int L, int R) {
23
    ///递归终⽌条件 分治递归
24
    /// 将 A[L...m] 和 A[m+1...R] 合并为 A[L...R]
25
    if (L >= R) { return; }
26
    int mid = L + (R - L) / 2;
27
    mergeSort(a, L, mid);
28
    mergeSort(a, mid + 1, R);
29
    mergeCount(a, L, mid, R);
30
}
31