2023届C/C++软件开发工程师校招面试常问知识点复盘Part 6

41、DHCP协议(动态主机配置协议)

DHCP协议是应用层协议,使用运输层协议UDP提供的服务

DHCP服务端的端口是UDP 67

DHCP客户端的端口是UDP 68

DHCP协议的工作过程以及一个没有IP地址的计算机如何通过网络中的DHCP服务器动态地配置IP

前提条件：局域网中存在DHCP服务器,或存在DHCP中继代理,计算机开机后自动运行DHCP客户端软件

---

①DHCP客户主动寻找DHCP服务器:DHCP DISCOVER

• DHCP客户通过广播的方式(目的地址:255.255.255.255源地址0.0.0.0目的端口:67)发送DHCP发现报文,用于寻找DHCP服务器;

• 因为端口为67,所以只有DHCP服务器会响应该发现报文,其他主机则丢弃该报文; DHCP服务器收到报文后会报文层层解析会得到客户端MAC,报文的事务ID等信息,然后跟根据客户端MAC查询本地是否有已经配置好的网络配置信息

• 如果存在,就在DHCP OFFER报文中回复,如果不存在就以默认的方式生成配置信息然后在DHCP OFFER报文中回复

---

②DHCP服务器发送配置信息提供报文:DHCP OFFER

• DHCP服务器通过广播的方式(目的地址:255.255.255.255源地址DHCP服务器自己的IP地址目的端口:68)发送DHCP OFFER报文.

• 因为端口为68,所以只有运行了DHCP客户的主机才会接收该报文,然后对报文进行解析可以获得事务ID,由此判断是否是发给自己的报文,如果不是则丢弃.

• 在DHCP OFFER报文中提供配置信息有IP地址 子网掩码 地址租期 默认网关 DNS服务器等

• 如果网络中存在多个DHCP服务器,客户端有可能获得多个DHCP OFFER报文,通常DHCP客户会选择先到的那个,然后给DHCP服务器发送DHCP请求报文

---

③DHCP客户发送DHCP请求报文:DHCP REQUEST

• DHCP客户通过广播的方式(目的地址:255.255.255.255源地址0.0.0.0目的端口:67)发送DHCP REQUEST报文.

• 广播发送是因为这样就不用为每一个DHCP服务器单播发送自己的选择情况,源地址为0.0.0.0是因为DHCP客户目前还没有设定自己的IP地址

• DHCP REQUEST报文中有事务ID DHCP客户的MAC地址 接收的租约中的IP地址 提供此租约的DHCP服务器的IP地址,DHCP服务器收到该报文后就可以知道自己的offer是否被选择了

• 然后DHCP服务器给DHCP客户发送确认报文

---

④被选择OFFER的DHCP服务器给DHCP客户发送确认报文:DHCP ACK

• DHCP服务器通过广播方式(目的地址:255.255.255.255源地址DHCP服务器自己的IP地址目的端口:68)发送确认报文.

• 之后在DHCP客户收到DHCP ACK报文后就可以使用租用的IP地址等网络配置信息,然后与网络中的其他主机进行通信了

• 然后就是正常的使用和通信了…

---

⑤DHCP客户的续约阶段(目的IP:DHCP服务器的IP地址 源IP地址:租用的IP地址 端口:67)

• a) 0.5倍租用期时：DHCP客户端主动续约,发送DHCP REQUEST报文,然后DHCP的响应有三种情况

  • 情况1: DHCP服务器同意续约,发送DHCP ACK报文,于是DHCP客户端有了新的租期

  • 情况2: DHCP服务器不同意续约,发送DHCP NACK否认报文,于是DHCP客户端立刻放弃当前的IP地址等配置信息,然后重新执行上述的第①步

  • 情况3: DHCP服务器未响应,则继续使用之前的IP地址配置信息,等待0.875倍租用期的到来

• b) 0.875倍租用期时：重复0.5倍租用期的动作,如果DHCP服务器还是未响应,那么等待租期用尽

• c) 租期用尽时：立即放弃当前的IP地址等配置信息,然后重新执行第①步

---

⑥DHCP客户在租期内可以随时终止DHCP服务器所提供的租用期:DHCP RELEASE

此时的是以广播方式(目的地址:255.255.255.255源地址0.0.0.0目的端口:67)发送DHCP RELEASE报文

42、STL中的allocate、deallocate

STL中的内存空间分配有两级：第一级配置器和第二级配置器

首先第一个问题：为什么需要两级空间配置器？

①频繁的在堆上申请释放内存，会造成大量的内存碎片；

②调用malloc和free等申请释放内存会使得空间添加许多附加信息，降低了空间的利用率；

其次第二个问题：二级空间配置器与一级空间配置器之间的协调合作关系？

①二级空间配置器负责小块内存的申请，一般是小于等于128字节；STL默认选择二级空间配置器，如果申请的空间大于128字节再去使用一级配置器

②一级空间配置器负责较大内存的申请，一般是大于128字节；

第三个问题：二级空间配置

使用一个数组存放8~128共16个大小的区块链表，维护了16个free-list。

1、第一级配置器直接使用的是malloc、free、relloc函数

2、第二级配置器则是根据请求区块的大小，大于128字节，调用一级配置器；小于等于128字节，则不使用一级配置器；

3、allocate()是空间配置函数，先判断请求的区块大小，大于128字节就去调用一级配置器；小于等于128字节就去检查free-list是否有可用区块，有的话直接拿来用；没有的话就要为free-list申请内存空间

4、dellocate()是空间释放函数，先判断空间大小，大于128字节就去调用一级配置器；小于等于128自己就去寻找对应的free-list然后释放内存

43、虚函数表、虚函数表指针

• C++中的虚函数的作用主要是实现多态的作用；而所谓多态则是当父类指针指向子类的时候，使用该指针调用同一个函数会因为指向的子类不同而表现出多种形态

• 虚函数的实现机制：

  虚函数机制的实现主要依靠编译器：

  1. 如果一个类存在虚函数，那么该类就会存在一个对应的虚函数表（一般是放在常量区），这里简称为虚表，这个虚表中保存的是该类的虚函数的函数地址
     • 虚函数表的存在与类有关
  2. 由该类实例化的一个对象，在对象存储空间的头部是虚函数表指针，简称vptr；vptr指向了该类的虚函数表，虚函数表中存放的是该类的虚函数地址，然后有了虚函数地址就可以找到虚函数，进行执行了。(虚函数存放在代码区)
  3. 一般情况下在虚函数表中存放的虚函数会依照声明顺序存放

  如果子类Derive继承了父类Base：（假设父类、子类都有虚函数）

  1. 子类Dreive也会有属于自己的虚函数表，在虚函数表中父类虚函数在前，子类虚函数在后；注意这是虚函数表（一般存放在常量区）

  2. 子类对象内存空间的头部就是虚函数表指针，指向了他自己拥有的虚函数表

  3. 如果子类重写了父类的虚函数，那么被重写的虚函数的地址在子类的虚函数表中将被替换成子类新写的函数（这一条特性决定，假如父类指针指向了子类的对象，可以实现多态效果）

     

  4. 对于没有被重写的父类虚函数，在子类虚函数表和父类虚函数表中的函数指针一样，相当于复刻，但不是同一个

  如果子类Derive继承了多个父类Base1、Base2、Base3

  1. 子类拥有自己的虚函数表，如果继承了多个父类，将会拥有多个自己的虚函数表；

  2. 子类对象的头部是指向虚函数表的指针，如果有多个父类，将会有多个虚函数表指针，指向子类拥有的多个虚函数表

  3. 对于子类自己新定义的虚函数，这些虚函数地址会存放在第一个虚函数表中

  4. 如果子类重写了父类虚函数，重写的是哪一个父类的虚函数，就会在对应的虚函数表中修改相应的函数地址

     

  关于初始化时机：

  • 虚函数表在编译时，编译器就会建立好。虚函数表存在常量区，虚函数存在代码区；
  • 虚函数表指针是对象的一部分，在对象构造时进行初始化；虚函数和虚函数表属于类，因此在编译时就会建立好。
  • 我们经常说的编译器会去调用某个函数balabala（我觉得这个表述有点误导人）。我认为其想表达的意思是：编译器在将源文件编译成二进制文件过程中在遇到创建一个对象的代码时，会自动地生成调用构造函数的二进制代码，也即所谓的编译器调用…

• 子类和父类的虚函数表是独立的吗？

  答：

  1. 不管子类是否拥有自己新创建的虚函数以及是否重写父类的虚函数，子类都拥有自己的虚函数表；
  2. 因为假如子类重写虚函数或者新定义虚函数时，就会改变虚函数表的内容，如果和父类共享虚函数表，那么父类不就无法调用自己的虚函数了吗？

44、左值与右值的相关内容

左值与右值:

一般在等号的左边，可以进行取地址的就是左值；

一般在没有地址的临时值、将亡值、字面值就是右值；

左值引用与右值引用：

左值引用：可以指向左值，但是不能指向右值的是左值引用

• 原因：因为左值引用相当于是变量的别名，因此左值引用应该有修改变量的能力，但是右值没有地址，因此无法被修改，所以左值引用也就无法指向右值

• 但是const 左值引用不对右值进行修改， 所以const 左值引用可以指向右值，例如 const int& ref_left_a = 5;,

• 在vector的push_back(const int& val)—vec.push_back(5)就用到了左值引用指向右值

---

右值引用：&&，可以指向右值，但是不能指向左值，有了右值引用之后，就可以通过右值引用去修改右值

• 为什么右值引用指向了一个右值，就可以修改其值了呢？

• 因为右值引用指向右值的过程本质上是将一个右值提升为一个左值，然后定义一个右值引用通过move函数，指向一个左值。

• 右值引用通过move函数指向一个左值后，就可以修改这个左值。

  

右值引用如何指向左值？

答：使用move()函数可以将一个左值转换成右值，可以让右值引用指向一个左值；这也是为什么右值引用可以修改右值。

左值引用和右值引用本身是左值！

只要是声明出来的左值引用和右值引用本身也是左值！

但是作为函数返回值的右值引用是右值

因此右值引用既可能是左值（直接声明：int && ref b = 5;）也可能是右值（函数返回右值：std::move(a)的返回值）

总之

1、左值引用只能指向左值，但是加了const的左值引用可以指向右值

2、右值引用可以直接指向右值，也可以借助move()函数指向左值

3、作为函数参数的右值引用，更加灵活：根据上述的第二条，就可以接收左右值，同时也能修改传进来参数 ，按照第一条，虽然可以使用const接收右值，但是不能修改。

右值引用和move的应用场景

主要是在STL和自定义类中实现移动语义，避免拷贝

注意：是不是可以提供一个移动构造函数，把被拷贝者的数据移动过来，被拷贝者后边就不要了，这样就可以避免深拷贝了

场景1：用于实现移动构造函数，将被拷贝者的数据直接移动过来

①在没有右值引用时的拷贝构造时，用的是const的左值引用 const type& val：这样既可以接收左值也可以接收右值。

• 使用左值引用，在参数传递进函数时因为使用了引用，所以避免了一次传参时的值拷贝。但是在对象内部进行深拷贝时，还不可避免的要进行拷贝操作。

• 那如果某一个值已经是不再需要的，在上述的拷贝操作就是一件重复的操作，如果可以将被拷贝的数据直接转移给新的对象拥有。那么这个仅剩的一次拷贝操作也可以避免了，由此也就提高了效率。但是若还是使用const的左值引用就无法实现了，因为有const的，所以就无法对该左值引用进行修改，也就无法实现安全的将被拷贝的数据直接转移给新的对象。

---

②此时右值引用就排上用场了：因为移动构造函数的参数是右值引用 type&& val，所以该函数可以接收右值和左值（接收左值时使用move()函数将左值转变成右值）

• 如此以来，就可以在函数内部修改这个左值了。因为当右值引用指向左值时，右值引用可以修改左值的内容。

• 如果参数是一个右值，右值引用指向该右值，对一个将亡值进行移动语义也是符合逻辑和语法的，并且使用右值引用引用了一个将亡值后该右值引用也是可以修改的

场景2：在类似vector中的push_back()与empalce_back()函数中，会有右值引用参数的重载，在使用时主动使用move()函数会触发移动语义

这种情况可以减少拷贝，直接将将亡对象的内容移动至容器中：

vector<string> vec;
string a = "hello";
// 直接push_back()左值
vec.push_back(a);  // a不变
vec.push_back(move(a)); // 触发了移动语义，将a中的内容“移动”到了容器内部，a将变成一个空字符串

// 也可以直接填右值
vec.push_back("hello");
1
2
3
4
5
6
7
8

此外智能指针unique_ptr仅有移动构造函数，只能移动对象内部的所有权，不能拷贝

场景3：就是forward()函数中，但是这个不常用，所以也不太了解

45、二叉堆的实现

1、二叉堆

• 二叉堆本质是完全二叉树，并且存放在数组之中

• 因此存储在数组中的二叉堆有如下性质：

  如果在数组中idx = 0的位置存放root，那么父节点的索引与左右子节点的关系如下：

  • 父节点为i，左子节点2i + 1 右子节点2i+2

  如果在数组中idx = 1的位置存放root，那么父节点的索引与左右子节点的关系如下：

  • 父节点为i，左子节点2i 右子节点2i+1

  

• 最大堆（大顶堆）：每个节点都大于他的两个子节点

• 最小堆（小顶堆）：每个节点都小于他的两个子节点

2、利用二叉堆实现优先级队列

• 其实所谓的优先级队列，就是一个二叉堆。

• 既然是队列自然是要实现一些基本的函数：

  1、构造

  2、入队列 push()

  3、出队列（获取队首元素，并弹出该元素）get_pop_front()

  4、size()

  5、是否为空empty()

• 其实想要实现上述的功能有两个函数非常重要，也即节点的上浮swim()和下沉sink()，这两个函数是二叉堆的精髓所在！

Show Me Code！

class PriorityQueue {
private:
	int* m_pArray;
    int m_length;
    int m_cap;
    
    // 节点上浮--大顶堆
    void swim_max(int idx){
        while(idx > 1 && m_pArray[idx] > m_pArray[idx / 2]) { // 当前节点大于父节点
            int temp = m_pArray[idx];						  // 交换
            m_pArray[idx] = m_pArray[idx / 2];
            m_pArray[idx / 2] = temp;
            
            idx = idx / 2;	 								  // 节点更新
        }
    }
    
    // 节点上浮--小顶堆
    void swim_small(int idx){
    	while(idx > 1 && m_pArray[idx] < m_pArray[idx / 2]) {
            int temp = m_pArray[idx];
            m_pArray[idx] = m_pArray[idx / 2];
            m_pArray[idx / 2] = temp;
            
            idx = idx / 2;
        }
    }
    
    // 节点下沉--大顶堆
    void sink_max(int idx){
        while(2 * idx <= m_length) {
            int l = 2 * idx;// 左节点
            if(l < m_length && m_pArray[l] < m_pArray[l + 1]) // 求左右节点的最大值(大顶堆)/最小值(小顶堆)
                l++;
            if(m_pArray[l] < m_pArray[idx])		// 如果已经满足的条件--那么break; 下沉结束
                break;
            
            int temp = m_pArray[idx];			// 交换
            m_pArray[idx] = m_pArray[l];
            m_pArray[l] = temp;
            
            idx = l;							// idx = l; 更新idx
        }
    }
    
    // 节点下沉--小顶堆
    void sink_max(int idx){
        while(2 * idx <= m_length) {
            int l = 2 * idx;
            if(l < m_length && m_pArray[l] > m_pArray[l + 1])
                l++;
            if(m_pArray[l] > m_pArray[idx])
                break;
            
            int temp = m_pArray[idx];
            m_pArray[idx] = m_pArray[l];
            m_pArray[l] = temp;
            
            idx = l;
        }
    }
public:
    // 构造,参数N表示队列或二叉堆的最大容量
    PriorityQueue(int N) {
        m_pArray = new int[N + 1]; // 因为从数组的下标1开始存节点的
        m_length = 0;
        m_cap = N;
    }
    
    // 析构
    ~PriorityQueue() {
        delete []m_pArray;
        m_pArray = nullptr;
        m_length = 0;
        m_cap = 0;
    }
    
    int size() {
        return m_length;
    }
    
    bool empty() {
        return m_length == 0;
    }
    
    // 入队--大顶堆
    void push(int ele) {
        if(m_length >= m_cap) return;
        m_pArray[++m_length] = ele;
        swim_max(m_length);
        // 或者小顶堆时用 swim_min(m_length); 
    }
    
    // 出队--大顶堆
    int get_pop_front() {
        int ret = m_pArray[1];
        m_pArray[1] = m_pArray[m_length--];// 将最后的值交换到root节点
        m_pArray[m_length + 1] = 0;			// 尾部置空
        sink_max(1);
        // 或者小顶堆时用 sink_min(1);
        
        return ret;
    }
};
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

3、利用二叉堆实现堆排序

• 对于使用二叉堆进行堆排序，完全可以使用上述的优先级队列
• 在排序算法函数内，创建一个优先级队列也即二叉堆，然后将所有的数组元素添加到堆（队列）中
• 然后再从优先级队列依次取出每一个元素，放到原始数组中
• 返回原始数组即可

对于大顶堆，就做降序排序； 对于小顶堆，就做升序排序；

void headSort(vector<int> &nums){
    PriorityQueue PQ(nums.size() + 1);  // PQ是一个局部变量
    //PriorityQueue* pPQ = new PQ(nums.size() + 1);
    for(auto it : nums) PQ.push(it);
    for(auto & it : nums)  it = PQ.get_pop_front();
    
    // delete pPQ;
}
1
2
3
4
5
6
7
8