问题总结

数学类

Nim游戏

为什么用异或可以判断先手与后手的输赢，即最后一个拿走石子的人会赢

问题1：为什么会分有先手必赢和后手必赢

image-20251028145355489

问题2：如何确定每一次拿走的个数

image-20251028145411094

292. Nim 游戏 - 力扣（LeetCode）

image-20251028155201989

欧几里得欧拉原理

507. 完美数 - 力扣（LeetCode）

加减乘除与模运算

分享丨模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理/组合数） - 讨论 - 力扣（LeetCode）

程序类

其他小问题

1.使用include的时候，<>与””的区别，<>会优先使用搜索系统目录，””会优先当前文件夹

2.换行符\n与end的区别，endl一般用于需要立即显示的信息的上面，但是\n可用于大量的数据换行，可以不着急输出，最后加一个cout<<endl刷新缓冲即可

image-20251029150550847

3.c++可以连续给变量复制a=b=c=10;成立

4.在LST之中，contains的效率比count高，contains一般找到相应的元素，即可就会返回，但是count需要找完整个数组

5.get与getline 的区别，getline可清理掉最后的结束换行符，但是get会保存下来，如果紧接着继续使用get们会发生错误，也就是说最后剩余的‘\n’还会被当作下一次的输入，进而导致错误

image-20251101152022465

6.struct与union的区别主要在与union里面的元素只有一个有意义，但是struct里面的元素可以同时有意义、image-20251102104849503

7.static_cast与(int)的区别

image-20251102111700831

8.下面的代码，在初始化的，分配给p指向的空间可能是无效的，此时无正确的输出正确的值，是野指针

image-20251103140159388

9.一个指针在被delete之后，变成了野指针，而非空指针， 此时需要重新使用的话，需要重新new一个然后指向，而野指针的定义就是为连自己指向什么类型的元素都不知道，此时赋值可能会发生上面的情况，同时注意在c++之中，允许delete空指针，但是不允许delete野指针

image-20251103142114830

10，对于int *p=new int[10];执行p+1的操作之后，此时的p[0]实际指向了原来的p[1]，请仔细看下面的输出，&a此时代表的整个数组，所以+16，换算为16进制，为+10

image-20251103155629907

11.比较位置的类型

image-20251105145248266

12.switch之中不能比较浮点类型的数据，其比较大值必须是一个单独的值

13.传指针与传引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
void fun1(int *a,int &b) {
    //首先指针可以为空的，在操作之前，必须检查，但是引用不需要
    if (!a) return;
    a=new int(100);
    cout<<*a<<endl;
    cout<<b<<endl;
}
void fun2(int &a) {
    //其次在这里更改的时候，变更a的值只能是原存储空间的变更，但是指针可以指向另外的地方

}
int main() {
    int a=0,b=10;
    fun1(&a,a);
    //可以发现在fun1之中变更了值，但是还是无法生效，因为指针指向了别的值
    cout<<a<<endl;

}

14,传输指针与传输引用对于数组的不同点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <iostream>
using namespace std;
int main() {
    int arr[4] = {100, 200, 300,400};

    // 验证第一行：访问值
    printf("Accessing values:\n");
    printf("arr[1] = %d\n", arr[1]);        // 输出 200
    printf("*(arr + 1) = %d\n", *(arr + 1)); // 输出 200

    // 验证第二行：获取地址
    printf("\nAccessing addresses:\n");
    printf("&arr[1] = %p\n", (void*)&arr[1]); // 输出一个地址，如 0x...
    printf("arr + 1 = %p\n", (void*)(arr + 1)); // 输出完全相同的地址

    // 演示它们可以互换使用
    printf("\nUsing interchangeably:\n");
    // 可以用指针形式给数组赋值
    *(arr + 2) = 999; // 这等价于 arr[2] = 999;
    printf("arr[2] is now: %d\n", arr[2]); // 输出 999
    cout<<&arr<<endl;
    cout<<&arr+1<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <vector>
#include <iostream>
using namespace std;

int main() {
    int arr[12]={0};
    vector<int> arr1(4,0);
    cout<<&arr<<endl;
    cout<<&arr+1<<endl;
    cout<<&arr1<<endl;
    cout<<sizeof(&arr1)<<endl;//注意看这里&arr+1之后+了3个，因为在vector定义的时候，包含3-4个指针，包括size等信息，此时会跳过对应的数量
    cout<<&arr1+1<<endl;
}

什么是差分数组

主要用于区间更新,差分数组用于存储当前值与前一个值之间的差值,同时也可以很方便的恢复原数组

如何构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void createDifVec(vector<int> &arr)
{
    int pre=arr[0];
    for (int i=1;i<arr.size();++i)
    {
        int temp=arr[i];
        arr[i]-=pre;
        pre=temp;
    }
}
void reDifVec(vector<int> &arr)
{
    for (int i=1;i<arr.size();++i)
    {
        arr[i]+=arr[i-1];
    }
}
int main()
{
    vector<int> arr={5,8,6,8,9,4,2,3,3};
    createDifVec(arr);
    cout<<"现在是差分数组的结构"<<endl;
    for_each(arr.begin(),arr.end(),[](int i){cout<<i;});cout<<endl;
    reDifVec(arr);
    cout<<"现在是恢复结构"<<endl;
    for_each(arr.begin(),arr.end(),[](int i){cout<<i;});cout<<endl;
}

有什么作用

主要用于区间的更新

假设在上述的操作之上，使得下标[1-5]的值+1，但是其他值不会更改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void createDifVec(vector<int> &arr)
{
    int pre=arr[0];
    for (int i=1;i<arr.size();++i)
    {
        int temp=arr[i];
        arr[i]-=pre;
        pre=temp;
    }
}
void reDifVec(vector<int> &arr)
{
    for (int i=1;i<arr.size();++i)
    {
        arr[i]+=arr[i-1];
    }
}
void intervalUpdate(vector<int> &arr,int begin,int end,int num)
{
    //那么从begin开始到end的元素+1，而end之后的元素-1
    arr[begin]+=num;
    arr[end+1]-=num;
}
int main()
{
    vector<int> arr={5,8,6,8,9,4,2,3,3};
    createDifVec(arr);
    cout<<"现在是差分数组的结构"<<endl;
    for_each(arr.begin(),arr.end(),[](int i){cout<<i;});cout<<endl;
    //reDifVec(arr);
    //cout<<"现在是恢复结构"<<endl;
    intervalUpdate(arr,1,5,1);
    for_each(arr.begin(),arr.end(),[](int i){cout<<i;});cout<<endl;
    //现在尝试复原原数组
    reDifVec(arr);
    for_each(arr.begin(),arr.end(),[](int i){cout<<i;});
}

进阶：二维差分

什么是单调栈

在栈之中保持其单增或者单减，找到元素左边或者右边第一个比他大或者比他小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
//寻找下一个比此数大的数
vector<int> getNextBigValue(vector<int> nums) {
    stack<int> indexStack;
    vector<int> result(nums.size(),-1);
    for (int i = 0; i < nums.size(); ++i) {
        if (indexStack.empty()) {
            indexStack.push(i);
        }else {
            //如果不为空
            while (!indexStack.empty()&&nums[i]>nums[indexStack.top()]) {
                result[indexStack.top()] = nums[i];
                indexStack.pop();
            }
            indexStack.push(i);
        }
    }
    return result;
}
//现在的任务是找到左边第一个比他小的值
vector<int> getPreSmallValue(vector<int> nums) {
    vector<int> result(nums.size(),-1);
    stack<int> indexStack;
    for (int i=nums.size()-1; i>=0; --i) {
        if (indexStack.empty()) {
            indexStack.push(i);
        }else {
            while (!indexStack.empty()&&nums[i]<nums[indexStack.top()]) {
                result[indexStack.top()] = nums[i];
                indexStack.pop();
            }
            indexStack.push(i);
        }
    }
    return result;
}
int main() {
    vector<int> nums={2,1,2,4,3};
    vector<int> nums2 = getNextBigValue(nums);
    vector<int> nums3 = getPreSmallValue(nums);
    for_each(nums2.begin(),nums2.end(),[](int c){cout<<c;});
    cout<<endl;
    for_each(nums3.begin(),nums3.end(),[](int c){cout<<c;});

}

优先队列

基本特性

插入元素与删除元素均为O(logn),但是默认底层使用vector进行实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Student {
public:
    int score;
    explicit Student(int score) {
        this->score = score;
    }
};
int main() {

    vector<int> v{1,2,3,4,5};
    priority_queue<int> pq1(v.begin(),v.end());//默认最大堆
    priority_queue<int,vector<int>,greater<>> pq2(v.begin(),v.end());//形成最小堆
    cout<<"最小堆顶的元素为"<<pq2.top()<<endl;
    //插入与删除操作
    pq2.push(0);
    pq2.pop();
    //如何自定义比较规则
    auto cmp=[](int a,int b){return a<b;};
    priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);//现在也是最小堆
    //如果存在自定义的函数规则
    auto studentCmp=[](Student &s1,Student &s2){return s1.score>s2.score;};
    Student student1(1);
    Student student2(77);
    Student student3(99);
    priority_queue<Student,vector<Student>,decltype(studentCmp)> studentPriorityQueue(studentCmp);
    studentPriorityQueue.push(student1);
    studentPriorityQueue.push(student2);
    studentPriorityQueue.push(student3);
    cout<<studentPriorityQueue.top().score<<endl;
}
注意在vector里面排序的时候，a>b是按照从大到小进行排序，但是在由于优先队列的定义是优先的关系，那么如果按照a>b进行排序的时候，此时会构成最小堆，即b堆优先度比较小，优先出去

与set的区别

image-20251105212654936

请注意在删除和插入的过程之中set与priority_queue的区别

并查集

如何实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
using namespace std;
class Union {
    //在这里的实现的时候主要是使用数组进行压缩，简洁实现树的结构
    vector<int> parents;
    //rank表示当前的对应节点的树的高度，在合并的时候，防止退化成为链表
    vector<int> rank;
    //表示其中连通分量的数量，每一次成功合并之后，连通分量都会--
    int count;
public:
    explicit Union(const int size):count(size) {
        parents.resize(size);
        rank.resize(size,0);
        for (int i = 0; i < size; i++) {
            //初始定义每一个元素的节点均为自己的父节点
            parents[i] = i;
        }
    }
    //查找根节点，一边查找，一边优化
    int findRoot(int i) {
        if (parents[i] != i) {
            parents[i]=findRoot(parents[i]);
        }
        return parents[i];
    }
    //合并两个元素所在的集合
    void unionArray(int x,int y){
        const int rootX = findRoot(x);
        const int rootY = findRoot(y);
        if (rootX != rootY) {
            //按照秩进行合并，保持树的平衡，此时的y的树比较高
            if (rank[rootX] < rank[rootY]) {
                //小树向大树上面靠近
                parents[rootX]=rootY;
            }else if(rank[rootY] < rank[rootX]) {
                parents[rootY]=rootX; 
            }else {
                parents[rootX]=rootY;
                rank[rootY]++;
            }
        }
    }
    //判断是否属于同一个集合
    bool connectUnion(int x,int y) {
        //为什么不能使用parents[x]==parents[y]，因为可能两个刚刚合并，但是此时并没有完成其下面每个元素根的归并
        return findRoot(x) == findRoot(y);
    }
};
int main() {

}

move函数

快速移动现在的元素，防止拷贝

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include <string>

int main() {
    std::string str = "Hello, World!";
    // 使用 move 将左值转换为右值引用
    std::string new_str = std::move(str);
    std::cout << "str after move: \"" << str << "\"" << std::endl;     // 可能为空
    std::cout << "new_str: \"" << new_str << "\"" << std::endl;        // "Hello, World!"
    return 0;
}

快速转移

快速转移对应的元素，容器的高速插入，容器之间的元素快速转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string str="hello world";
    string str2=move(str);
    cout<<str<<"-----"<<str2<<endl;
    str="hi";
    //快速插入，插入之后，原来的变为空
    vector<string> v;
    v.push_back(move(str));
    //在vector之间移动
    vector<string> v2={"apple","ban","good","hi"};
    vector<string> v3;
    move(v2.begin(),v2.begin()+2,back_inserter(v3));
    for_each(v2.begin(),v2.end(),[](string str){cout<<str;});
    for_each(v3.begin(),v3.end(),[](string &s){cout<<s;});
}

bitset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;

int main() {
    bitset<32> bits1(-3);
    bitset<32> bits2(3);
    //将其按照转换为string并且输出
    cout << bits1.to_string() << endl;
    //转换为10进制进行输出，但是注意对负数不会产生作用
    cout << bits1.to_ulong()<< endl;
    //统计1的个数
    cout << bits1.count() << endl;
    //可用于位运算
    cout << (bits1^bits2).to_string() << endl;
}

双端队列deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <deque>
#include <iostream>
using namespace std;

int main()
{
    deque<int> deque={1,2,3,4,5,6};//定义双端队列
    //查看操作
    cout<<"头节点为"<<deque.front()<<endl;
    cout<<"尾节点为"<<deque.back()<<endl;
    cout<<"通过下标进行访问"<<deque.at(1)<<endl;
    cout<<"不检查下标进行访问"<<deque[0]<<endl;
    //插入操作
    deque.push_back(7);
    deque.push_front(0);
    //删除操作
    deque.pop_back();
    deque.pop_front();
}

emplace函数

与insert的区别在于emplace是直接在参数构造对象，但是insert是首先构建参数，然后再拷贝到stl容器之中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3};
    //直接传入4，比push_back更加好
    v.emplace_back(4);
    //再指定的位置传入指定的值
    v.emplace(v.begin()+1,100);
    std::cout<<v[1]<<std::endl;
    //再map结构的区别
    std::unordered_map<int,int> hashmap={{1,1}};
    auto it=hashmap.emplace(2,2);//返回的结果是迭代器+是否插入程序
    std::cout<<it.second<<std::endl;
    //再指定位置插入对应的元素，但是注意仅仅对map有效，对于hashmap没有效果，第一个位置可以直接指定插入的位置
    hashmap.emplace_hint(hashmap.end(),3,2);
    //也就是说再有序的时候，并且直到对应的位置，才会速度更快
    return 0;
 }

无符号数与有符号运算

首先会考虑优先级

int比short高，会转换为unsigned int进行计算

image-20251101114341491

类型会首先考虑转换为无符号数

image-20251101113427643

其他

当有符号数可以包括无符号数的所有范围，则按照有符号数进行运算

image-20251101113345037

vector与array的比较

初始化的比较

首先array在初始化的时候，必须指定大小，并且之后不可变更，在其他用法方面与vector基本相同

1
2
3
4
5
6
7
8
9
10
#include <cstring>
#include <iostream>
#include <vector>
#include <array>
using namespace std;

int main() {
    array<int,5> arr{};//此时指定大小，元素分配在栈上，不需要堆分配的开销
    vector<int> vec{};//此时可以不指定大小，但是其中的元素分配在堆上，但是可以随时调整大小
}

image-20251104104501042

位置比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <array>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main()
{
    string name="zss";
    vector<string> words={"zss"};
    cout<<&name<<endl;
    cout<<&words[0]<<endl;
    cout<<&words<<endl;
    vector<int> arr={1};
    cout<<&arr[0]<<endl;
    cout<<&arr<<endl;
    array<int,1> temparr={1};
    cout<<&temparr<<endl;
    cout<<&temparr[0]<<endl;
}

image-20251105144933937

小数组

为什么推荐小数组

小数组数据量小的时候，可以存储在cpu缓存之中，此时的读取效率完全可以避免算法结构带来的差异，是对缓存友好的，在大规模的排序系统之中，子数组小到一定的长度之后，就会切换到插入排序

多长的数组可以定义为小数组

小数组应该能够舒适的放到cpu 的高速缓存（三级缓存）

枚举类

基础用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
enum Weekday {
   MONDAY = 1,
   TUESDAY,    // 自动为 2
   WEDNESDAY,  // 自动为 3
   THURSDAY = 10,
   FRIDAY      // 自动为 11
};
int main() {
   Weekday day = MONDAY;
   cout << "Weekday: " << day << endl;    // 输出: 1
   return 0;
}

枚举类的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

enum class Color
{
    RED,
    BLUE,
    GREEN
};
enum class Status:int{//在这里指定类型
    OK,
    BAD,
    GREAT
};
int main()
{
    auto col=Color::RED;
    cout<<static_cast<int>(col)<<endl;//不能直接输出，必须进行显示转换
    auto status=Status::OK;
    if (status==Status::OK)
    {
        cout<<"Ok"<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;

enum class Color
{
    RED,
    BLUE,
    GREEN
};
enum class Status:int{//在这里指定类型
    OK,
    BAD,
    GREAT
};
//字符串转换为string
string to_string(Color color)
{
    switch(color)
    {
        case Color::RED:
        return "RED";break;
        case Color::BLUE:
        return "BLUE";break;
        case Color::GREEN:
        return "GREEN";break;
        default:
        return "UNKNOWN";break;
    }
}
//使用运算符进行遍历
Color &operator++(Color &C)
{
    C=static_cast<Color>(static_cast<int>(C) + 1);
    return C;
}
int main()
{
    auto C = Color::RED;
    switch (C)
    {
        case Color::RED:
            cout<<"RED"<<endl;break;
        case Color::BLUE:
            cout<<"BLUE"<<endl;break;
        case Color::GREEN:
            cout<<"GREEN"<<endl;break;
    }
    const string s = to_string(C);
    cout<<s<<endl;
    while (true)
    {
        cout<<to_string(C)<<endl;
        if (C==Color::GREEN) break;
        ++C;
    }
}

++i与i++

++i与i++之间的区别

image-20251104111236231

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
class Counter
{
public:
    int value;
    Counter(int value) : value(value) {};
    Counter& operator++()
    {
        ++value;
        return *this;
    }
    Counter& operator++(int)
    {
        Counter tmp = *this;
        ++value;
        return tmp;
    }
};
int main()
{
    Counter c(0);
    ++c;
    c++;
    cout<<c.value<<endl;
}

i++为什么不能复制自身

下面的运算之中应该old的值为5，不应该为6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Counter {
private:
    int value;
public:
    Counter(int v = 0) : value(v) {}

    // 如果错误实现后缀运算符（返回自身引用）
    Counter& operator++(int) {  // 错误实现！
        Counter temp = *this;   // 保存原值
        ++value;                // 自身递增
        return *this;           // 错误！应该返回temp而不是*this
    }
};

int main() {
    Counter c(5);

    Counter old = c++;  // 期望：old=5, c=6
    
    // 但如果返回*this，实际结果：
    // old=6, c=6  ← 这违反了后缀运算符的语义！

    return 0;
}

运算符的重载

sizeof在函数之中失效的原因

总结一下

对于参数的使用arr[]的形式，此时传递的是指针，但是vector是将自己重新复制了一份，这样自己能够sizeof得到大小，但是指针却不可以，而下面的&arr则是指针的地址，也就是地址的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

void sum_arr(long long arr[], int size) {
    cout << "函数内 arr 地址: " << arr << endl;
    //注意这里取得的是自己的指针的地址，相当于地址的地址
    cout << "函数内 &arr: " << &arr << endl;  // 注意这里！
    cout << "sizeof(arr): " << sizeof(arr) << endl;
}

int main() {
    long long cookies[7] = {1,2,3,4,5,6,7};
    cout << "cookies 数组大小: " << sizeof(cookies) << endl;
    cout << "cookies 地址: " << cookies << endl;
    cout << "&cookies: " << &cookies << endl;
    sum_arr(cookies, 7);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
using namespace std;
void change(int arr[],int size) {
    arr[0]=12;
}
void change1(vector<int> arr) {
    arr[0]=12;
    //但是在这里arr可以得到自己的长度，这也就是因为在函数之中复制了vector的值
    //所以可以得到值，但是int arr[]并不会，因为次数传递的是指针
}
int main() {
    int arr[12]={0};
    vector<int> arr1(12,0);
    change(arr,12);
    change(arr1.data(),12);
    //但是注意传递vector并不会改变

}

7、函数

函数与数组

指针与const

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstring>
#include <iostream>
using namespace std;

int main()
{
    //const指向了指针a，此时名称为指针常量，此时指针的指向不能更改，但是其中的内容可以变更
    int* const a=new int(1);
    //错误，不能更改
    //a=new int(2);
    cout<<"a未更改之前"<<*a<<endl;
    *a=3;
    cout<<"a更改之后"<<*a<<endl;
    //现在是常量指针
    const int *b=new int(2);
    //在这里表示其中的2无法进行更改，因为const限制了*b，即其中的值
    //*b=3;但是可以更改其中的指向
    cout<<"b指向的地址为"<<b<<endl;
    b=a;
    cout<<"b指向的地址为"<<b<<endl;
    //现在有指向常量的常量指针，均不能更改
    const int * const c=new int(2);
}

image-20251110154202831

int arr[]自身特性

注意int arr[]之中的arr本身就是一个指针常量，即自身指向无法被更改

1
2
3
4
5
6
7
8
9
int main()
{
    int arr[]={1,2,3,4,5,6,7,8,9,10};
    int* arr2 = new int[10];
    //下面的不成立，无法进行进行更改
    //arr=arr2;
    //这里就是常量指针常量，任何值都无法进行更该
    const int arr3[]={5,8,9,58};
}

函数指针

如何设计与指定函数指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstring>
#include <iostream>
#include <array>
using namespace std;
void fun(int a)
{
    cout << a << endl;
}
void fun2(int a)
{
    cout << a << endl;
}
//将函数作为参数进行传递
void fun3(void (*pfun)(int))
{
    cout<<"开始使用指针调用函数"<<endl;
    pfun(5);
}
int main()
{
    void (*pfun)(int) = fun;
    //这种方式可以输出地址
    cout<<(void *)pfun<<endl;
    void (*pfun2)(int) = fun2;
    //为什么输出1，是因为隐形的转换为bool类型
    cout << pfun2 << endl;
    //如何使用指针来调用函数
    fun3(pfun);
    //将函数指针作为数组进行使用
    void (*parr[2])(int)={fun,fun2};
}

8、函数探幽

内联函数

用处

常规的函数在内存之中仅仅存在一份，调用的时候，直接返回地址即可，但是需要开辟栈空间，存储其他的信息等等，但是内敛函数会将函数直接复制到对应的位置，不需要通过地址调用，但是这也会导致调用多次，会在内存之中出现多份

1
2
3
4
5
6
7
8
9
10
11
#include <vector>
#include <iostream>
using namespace std;
inline int getS(int x) {//并不一定使用了inline就会时内联函数，抉择权在编译器，如果占用内存大，编译器不会同意
    return x*x;
}
int main() {
    //此时gets的函数代码会在内存之中存在多份，而非一份
    getS(2);
    getS(4);
}

image-20251116195323785

引用变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <iostream>
using namespace std;
int main() {
    int a=123;
    int &b=a;
    //此时的ab地址一模一样
    cout<<&b<<endl;
    cout<<&a<<endl;
    int c=99;
    b=c;
    cout<<a<<" "<<b<<" "<<&a<<" "<<&b<<endl;
    cout<<&c<<endl;
    //注意看下面的不同
    int *d=&a;
    cout<<d<<&a<<endl;
    //此时的d指针可以指向别的位置，但是此时b作为a的别名，一旦定义，怎么也不会改变，和指针还是不同
}

为什么尽可能使用const

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>

// 函数期望一个 "const double 引用",如果这里不添加const，此时函数会进行报错,因为这里是用了引用，如果不使用引用是不会报错的
void refcube(const double& rd) {
    std::cout << rd << std::endl;
    std::cout << "Address inside function: " << &rd << std::endl;
}

int main() {
    int x = 3; // 实参是 int 类型

    std::cout << "Original x: " << x << std::endl;
    std::cout << "Address of x: " << &x << std::endl;

    refcube(x); // 传递一个 int 给需要 const double& 的函数

    return 0;
}

image-20251116203920105

为什么在使用&的形参之中，使用const允许类型转化，但是不使用却不允许类型转换

对于非const的引用参数，我们可能会去修改他的值，如果允许自动转换的话，那么会创建临时变量，但是原来的值并不会改变，这也就是为什么使用&的时候推荐const的原因

重载

const重载的影响

注意这里是进行了值的传递，也就是复制了一份，故而是否使用const都无所谓，对原数产生不了影响，编译器认为他们是相同的 
1
2
3
4
5
6
7
8
void say(const int n)
{
    std::cout << n << std::endl;
}
void say(int  n)
{
    std::cout << n << std::endl;
}

但是const如果类修饰指针或者引用，这时可以进行操作，因为是否添加指针确实会影响到原函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <filesystem>
#include <iostream>
void say(const int *n)
{
    std::cout <<1 <<n << std::endl;
}
void say(int  *n)
{
    std::cout <<2 <<n << std::endl;
}
void say(int &n)
{
    std::cout <<3 <<n << std::endl;
}
void say(const int &n)
{
    std::cout <<4 <<n << std::endl;
}
int main() {
    //未规定const 的时候优先调用非const的数据
    int n=10;
    say(n);
    //这里其实对四个函数都是符合的，但是为什么会优先解释为指针
    int a=10;
    say(&a);
}

为什么优先解释为指针

因为再这个过程之中，&a总是被优先解释为指针，而如果再只使用int &n的函数，则需要再次解引用，多了一个步骤

函数模板

基础用法

此时传入double等什么类型均可，此时如果有一个具体的swap(int,int)函数，此时会优先调用

1
2
3
4
5
6
7
8
template <typename AnyType>//指出要建立一个函数的模板
void Swap(AnyType &a,AnyType &b)
{
    AnyType temp;
    temp=a;
    a=b;
    b=temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <filesystem>
#include <iostream>
#include <random> // 现代随机数库
template <typename AnyType>
void Swap(AnyType &a,AnyType &b)
{
    std::cout<<"隐式实例化"<<std::endl;
    AnyType temp=a;
    a=b;
    b=temp;
}
//在此直接创建int类型的，调用int类型的swap的时候，会直接来这里调用，直接链接，不会重新创建
template void Swap<int>(int&,int&);
//但是当我们想要交换的是数组的时候,可以理解为重载某个函数
template <>
void Swap<int *>(int *&a,int *&b)
{
    std::cout<<"显式显式具体化"<<std::endl;
    for (int i=0;i<6;++i)
    {
        int temp=a[i];
        a[i]=b[i];
        b[i]=temp;
    }
}
int main() {
    float a=101.1,b=56.2;
    Swap(a,b);
    std::cout<<"a="<<a<<" b="<<b<<std::endl;
    int c=1,d=2;
    Swap(c,d);
    std::cout<<"c="<<c<<" d="<<d<<std::endl;
    int e[]={1,2,3,4,5,6};
    int f[]={1,2,39,4,5,6};
    std::cout<<e<<std::endl;
    int *pe=e;
    int *pf=f;
    std::cout<<pe<<std::endl;
    Swap(pe,pf);
    std::cout<<e[2]<<std::endl;
}

1.显式实例化有什么用

显式实例化可以提前生成对应的代码模板，这样再不同的代码文件之中，比如调用int类型的时候，不会重新创建一份，而是去寻找

2.如何理解显式具体化

显式具体化可以理解为对于模板类的重写，比如这里交换数组的值，可以进行具体话，进行具体方法具体分析

3.为什么再上述的代码之中，直接传入ef不可吗

c语言形式的int a[]本身就是const 类型的指针，也就是指针的指向的位置不能改变，但是其中的数值可以改变，而这里是非const，即不能进行传入目标函数之中

自己指定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
template <typename T>
T getLesser(T a,T b)
{
    cout<<"使用了模板"<<endl;
    return a < b ? a : b;
}
template <>
int getLesser(int a,int b)
{
    cout<<"使用了具体的int类型"<<endl;
    return a < b ? a : b;
}
int main()
{
    int a=10,b=20;
    double c=10.2,d=5.2;
    cout<<getLesser(a,b)<<endl;
    cout<<getLesser(c,d)<<endl;
    //自己指定类型
    cout<<getLesser<>(a,b)<<endl;
    cout<<getLesser<int>(c,d)<<endl;

}

关键字decltype

基础用法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
//返回函数类型推导
template<typename  T,typename U>
auto add(T t,U u)->decltype(t)//会将结果推导成为t
{
    return t+u;
}
int main()
{
    int x=10;
    double y=3.14;
    decltype(x) a=3.25;//将a推导为x类型
    cout<<a<<endl;
    auto z=add(x,y);//将其推导为传入的t的类型
    cout<<z<<endl;
}
注意点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
//返回函数类型推导
int main()
{
    int x=9;
    decltype(x) a=x;
    cout << a << endl;
    a=10;
    //这里a仅仅是int类型，改变a不会改变x
    cout << x << endl;
    decltype((x)) b=x;
    cout << b << endl;
    b=100;
    //但是这里的b却是引用类型，即是&b，改变之后a也会改变
    cout << x << endl;
}

注意delctype对对于左值或者右值的作用改变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int x = 5;

// 变量名 - 得到声明类型
decltype(x) a;        // int

// 带括号的变量名 - 得到引用类型（因为是左值）
decltype((x)) b = x;  // int&

// 字面量 - 得到类型本身（因为是纯右值）
decltype(42) c;       // int

// 带括号的字面量 - 还是类型本身（仍然是纯右值）
decltype((42)) d;     // int

// 函数调用 - 取决于返回值类型
int func();
decltype(func()) e;   // int
decltype((func())) f; // int（函数返回临时对象，是右值）
与模板函数的结合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
/*template<typename T>
//这里使用auto会丢失掉引用，导致此时返回的值为t，但是不能够作为左值，程序也会报错
auto add(T &t)
{
    t+=10;
    return t;
}*/
template<typename T>
//但是在这里类型推导之后，可以得到返回的引用值，从而改变其中的结果
auto add(T &t)->decltype((t))
{
    t+=10;
    return t;
}
int main()
{
    int a = 10;
    cout << add<int>(a)<<endl;
    add<int>(a)=15;
    cout<<a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;
template<typename Container>
auto get_element(Container& c, int index) -> decltype(c[index]) {
    return c[index];  // 返回引用，可以修改原容器
}

template<typename Container>
auto get_element_const(const Container& c, int index) -> decltype(c[index]) {
    return c[index];  // 返回 const 引用
}

int main() {
    std::vector<int> vec{1,2,3};
    get_element(vec, 0) = 100;  // 正确！vec[0] 现在为 100
    
    const std::vector<int> cvec{1,2,3};
    // get_element(cvec, 0) = 200;  // 错误！返回 const 引用
}

内存模型与名称空间

头文件的保护

1
2
3
4
#ifndef 标识符
#define 标识符
//头文件的内容
#endif

  1. 第一次包含：EXAMPLE_H 未定义 → 执行 #ifndef 到 #endif 之间的代码

  2. 第二次包含：EXAMPLE_H 已定义 → 跳过整个内容

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // coordin.h
    #ifndef COORDIN_H          // 第1步：检查COORDIN_H是否被定义过
    #define COORDIN_H          // 第2步：如果没有，现在定义它

    // 这里是头文件的真实内容（声明等）
    struct Polar {
        double distance;
        double angle;
    };

    struct Rect {
        double x;
        double y;
    };

    // 函数声明
    Polar rect_to_polar(Rect xypos);
    void show_polar(Polar dapos);

    #endif                    // 第3步：条件编译结束
    1
    2
    3
    4
    5
    6
    #include "coordin.h"  // 第一次包含
    #include "another.h"  // 假设another.h内部也包含了coordin.h，现在在编译阶段第二次会直接跳过

    int main() {
        // ...
    }

强枚举类型

访问必须通过类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
enum Language {
  ENGLISH,
  CHINESE,
  MAX,
};

// 可以直接访问，容易命名冲突
int value = ENGLISH;  // OK
int max = MAX;        // 可能与其他的MAX冲突

enum class Language : uint32_t {
  ENGLISH,
  CHINESE,
  MAX,
};

// 必须通过枚举名访问
Language lang = Language::ENGLISH;  // 正确
// int value = ENGLISH;             // 错误！未声明的标识符

不会隐式转换

必须经过强制类型转换来获得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
enum Language { ENGLISH, CHINESE };
enum Color { RED, BLUE };

Language lang = ENGLISH;
Color color = RED;

if (lang == color) {  // 编译通过！逻辑错误但语法正确
    // 这不应该发生，但编译器不会报错
}
enum class Language { ENGLISH, CHINESE };
enum class Color { RED, BLUE };

Language lang = Language::ENGLISH;
Color color = Color::RED;

// if (lang == color) {  // 编译错误！类型不匹配
// }

可以指定底层类型

1
2
3
4
5
6
7
8
enum class Language : uint32_t {  // 明确指定32位无符号整数
  ENGLISH,
  CHINESE,
  MAX,
};

// 确保在不同平台和编译器上大小一致
static_assert(sizeof(Language) == sizeof(uint32_t));

tuple的用处

基础用法

tuple 的作用在于可以返回不同类型的多个值，同时也可实现在stl的排序，即按照不同的类型的规则进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
int main() {

    std::tuple<int, std::string,double> t1={789,"zss",15.69};
    std::tuple<int, std::string,double> t2={56,"haha",52.63};
    std::vector<std::tuple<int, std::string,double>> vec={t1,t2};
    sort(vec.begin(), vec.end(),[](std::tuple<int, std::string,double> t1,std::tuple<int, std::string,double> t2)
        {return std::get<1>(t1)<std::get<1>(t2);});
    std::cout<<"hi"<<std::endl;
    return 0;
 }

其他

1
2
3
4
5
6
7
#include <tuple>

auto t1 = std::make_tuple(1, "hello");
auto t2 = std::make_tuple(3.14, 'a');

// 连接两个tuple
auto merged = std::tuple_cat(t1, t2);  // (1, "hello", 3.14, 'a')

kmp算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void getNext(const string &s, vector<int> &next) {
    int j=0;//表示当前计算的位置
    int k=-1;//上一个的next的值，同时也被表示当前最长匹配前缀的长度
    while (j<s.length())
    {
        //在k=-1的时候，表示上一次的匹配是完全失效的，即不能使用
        //而在s[j]==s[k]的时候，此时匹配成功，此时应该匹配下一个
        if (k==-1||s[j]==s[k])
        {
            //当前的匹配成功j++，或者
            j++;
            //
            k++;
            next[j]=k;
        }else
        {
            k=next[k];
        }
    }
}

未完待续

题目1590