C++工程师面试模拟

STL的组成

容器、算法、迭代器、适配器
一共有六大部分：容器、算法、迭代器、仿函数、适配器、空间配置器
容器：用来存放数据的各种数据结构，比如vector、deque、list、set和map等，是一种类模板
算法：各种常用的算法，比如排序算法，拷贝算法、查找算法等，是一种函数模板
迭代器：容器与算法间的粘合剂，共有五种类型，重载了指针相关的各种操作，比如operator++、operator–等，是一种类模板
仿函数：行为类似函数，可以作为算法的某种策略，从实现角度来看，它是重载了operator()的一种类模板
适配器：用来修饰容器、仿函数和迭代器的接口
空间配置器：负责空间的配置与管理。配置器实现了动态空间分配、管理与释放的类模板。

它们间的交互关系：容器通过空间配置器取得数据存储空间；算法通过迭代器来存储容器中的内容；
仿函数可以协助算法实现不同的策略；适配器可以修饰仿函数。

啥是内存对齐，为啥内存对齐

硬件读的时候是整块整块的读取操作的
尽量不要让一个数据存到两块里，如果满了就找个新开始存储
现代计算机中内存空间都是按照 字节（byte）划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但是实际的计算机系统对基本类型数据在内存中存放的位置有限制，它们会要求这些数据的首地址的值是某个数 k（通常它为4或8）的倍数，这就是所谓的内存对齐。

内存对齐的原因
平台原因（移植原因）：不是所有的硬件平台都能访问任意地址上的任意数据的。某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
性能原因：数据结构（尤其是栈）应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问，而对齐的内存访问仅需要一次访问。

内存对齐的规则
每个特定平台上的编译器都有自己的默认“对齐系数”（也叫对齐模数）。可以通过预编译命令 #pragma pack(n)，n = 1,2,4,8,16 来改变这一系数。
有效对其值：是给定值 #pragma pack(n) 和结构体中最长数据类型长度中较小的那个，有效对齐值也叫对齐单位。
结构体第一个成员的偏移量（offset）为0，以后每个成员相对于结构体首地址的 offset 都是该成员大小与有效对齐值中较小那个的整数倍，如有需要编译器会在成员之间加上填充字节。
结构体的总大小为有效对齐值的整数倍，如有需要编译器会在最末一个成员之后加上填充字节

介绍几种IO模型

阻塞IO、非阻塞IO、信号驱动IO、IO多路转接、异步IO。其中，前四个被称为同步IO。
https://blog.csdn.net/ZWE7616175/article/details/80591587

翻转部分链表

https://leetcode.cn/problems/reverse-linked-list-ii/
主要是保存好左右的接口，尤其要清楚的知道当前遍历位置，取出正确的反转链表之后，用递归反转链表，再把反转完的拼接回去就ok了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *reversedlist = new ListNode(0);
    ListNode *revCur = reversedlist;
    void  reverseList(ListNode *revlist){
        if(revlist == nullptr){
            return;
        }
        reverseList(revlist->next);
        revCur->next = revlist;
        revCur = revCur->next;
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        int revLen = right-left+1;
        ListNode *dummynode = new ListNode(0);
        dummynode->next  = head;//带烧饼节点的
        ListNode *cur = dummynode;
        while(--left){
            cur = cur->next;
        }
        ListNode *leftInter = cur;
        ListNode *revlist = leftInter->next;
        while(revLen--){
            cur = cur->next;
        }

        ListNode *rightInter = cur->next;
        cur->next = nullptr;
        leftInter->next = nullptr;

        reverseList(revlist);
        revCur->next = rightInter;
        leftInter->next = reversedlist->next;
        return dummynode->next;
    }
};
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