一、基础问题

1.1 迭代器失效

删除操作引起vector内元素移动，导致被移动部分的迭代器失效
另：push_back、insert、erase都会导致迭代器失效。

1.2 没有说到的C++ 11-20 新特性

我看的是一本手册：《现代C++教程：高速上手C++11/14/17/20》

1.3 容器的实现原理

1.3.1.vector

原理：连续的内存空间、数组、支持下标访问、随机访问的速度很快、头部插入很慢，尾部插入很快
性能：查找删除与数组性能一样，增加元素引发扩容时会有性能压力，一般为当前大小的两倍，然后把原数组的内容拷贝过去，接着释放原来的空间。

1.3.2.list

原理：双向链表、不支持下标访问、随机访问速度慢、插入快
性能：常量性能的增删，不支持随机访问

1.3.3.map, multimap：

原理：以Key建立的红黑树、插入删除效率贼高
区别：multimap不存在at操作
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

1.3.4.set，multiset:

原理：红黑树
区别：Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在于Set只含有Key，而Map有一个Key和Key所对应的Value两个元素。

1.3.5.unordered_map：

所有无序容器的底层实现都是Hash Map
原理：序容器存储键值对时，会先申请一整块连续的存储空间，但此空间并不用来直接存储键值对，而是存储各个链表的头指针，我们称其为桶，各键值对真正的存储位置是各个链表的节点。

1.4 虚函数的实现原理

虚函数的实现原理是虚表，这个虚表里面存储着最终需要调用的虚函数地址，这个虚表也叫虚函数表

指向虚表的指针在x86平台下占4个字节，所以sizeof(cat)占12个字节，比平时多出来4个。

只要父类里面有virtual声明，子类重写后依然是虚函数，只不过省略未写virtual

1.5 sizeof(string) 的大小

gcc12.1 ： 32
clang14.0.0 ：32
msvc19.32：24

二、shell之awk

打印日志 1.log的信息

adfadfasdf site:12343 dkdkdkkck
adfkadfadasfdadf site:3423 adlfadalda
dfadfa site:14444 dddddddd

awk -F "[: ]" '{sum+=$3}{print "Average = ", sum/NR}' 1.log | tail -n1
1

-F "[: ]"：指定两种分隔符
{sum+=$3}：求和
| tail -n1：打印最后一行

三、SQL

select department, avg(xx_score) 
from bd_table_name 
where sex='男' and xx_xx = 'x_x'
group by department
1
2
3
4

四、Git

4.1 git revert 撤销中间某次commit

git revert commit_id
1

4.2 rebase与 merge 都是作为合并分支；

merge 优点
简单又熟悉
保留完整的历史记录和时间顺序
维护分支的上下文
merge 缺点
提交历史可能会被很多merge提交污染
使用调试git bisect可能会变得更加困难

rebase优点
简单化复杂历史
容易操作单个提交（例如revert它）
避免在庞大仓库忙碌的分支中存在很多乱七八糟的‘merge’ commit
通过清理使多个提交成为单个提交，这对于DevOps团队可能会有所帮助
rebase缺点
将功能压缩到少量提交可能隐藏一些信息
团队合作时重新建立公共存储库可能很危险
要通过远程分支进行rebase，需要强行推送。

五、编程题

5.1 缺失的数字

问题描述

input [1,1,1,1,1,1]
output [2]
input [1,1,1,5,1,1]
output [2，3，4]

#include 
#include 
#include 
#include 

using namespace std;

//思路一：数组
void nums1(int v[], int &size) {
    int max = 0, x = 0;
    int dic[1000] = {0};  //设置一个全为0的数组
    // 找到最大值
    for (int i = 0; i < size; i++)
        if (v[i] > max)
            max = v[i];
    // [1,最大值] 和 size 两层遍历
    for (int i = 1; i < max + 1; i++)
        for (int j = 0; j < size; j++)
            if (i == v[j])
                dic[i] = 1;  // 将v中存在的值 置1
    // 找出未置1的数 存入数组v
    for (int i = 1; i < max + 1; i++)
        if (dic[i] == 0) {
            v[x] = i;
            x++;
        }
    // 更新数组的大小
    size = x;
    // 如果数组为0，填入最大值+1
    if (size == 0) {
        size = 1;
        v[0] = max + 1;
    }
}

//思路二：set、vector
vector<int> nums2(vector<int> v) {
    vector<int> re;
    set<int> temp;
    int max = 0;
    // 取出最大值；把元素放入集合
    for (int i = 0; i < v.size(); i++) {
        if (v[i] > max)
            max = v[i];
        temp.insert(v[i]);
    }
    // 利用set的查找方法，把找不到的放入vector
    for (int i = 1; i < max + 1; i++)
        if (temp.find(i) == temp.end())
            re.push_back(i);
    // 如果vector为0，加入最大值+1
    if (1 > re.size())
        re.push_back(max + 1);
    return re;
}

//思路三：我女朋友的思路
vector<int> nums3(vector<int> v) {
    vector<int> re;
    vector<int>::iterator iter;
    sort(v.begin(), v.end());
    iter = unique(v.begin(), v.end());
    v.erase(iter, v.end());

    for (int i = 0; i < v.size(); i++)
        if (v[i] != (i + 1)) {
            v.insert(v.begin() + i, i + 1);
            re.push_back(i+1);
        }
    
    if (0 == re.size())
        re.push_back(v.back() + 1);
    return re;
}

int main() {
    vector<int> v = {1, 2, 3, 4, 6};
    vector<int> v1 = {1, 3, 4, 7, 8, 7, 4, 3};
    vector<int> v2 = {1, 1, 1, 1, 1, 1, 1, 1, 1};
    int v3[8] = {1, 3, 4, 7, 8, 7, 4, 3};
    int v4[9] = {1, 1, 1, 1, 1, 1, 1, 1,1};
    int sizeV3 = sizeof(v3) / sizeof(int);
    int sizeV4 = sizeof(v4) / sizeof(int);

    //思路1
    nums1(v3, sizeV3);
    for (int i = 0; i < sizeV3; i++) {
        cout << v3[i] << " ";
    }
    cout << endl;
    nums1(v4, sizeV4);
    for (int i = 0; i < sizeV4; i++) {
        cout << v4[i] << " ";
    }
    cout << endl;

    //思路2
    for (auto it: nums2(v1))
        cout << it << " ";
    cout << endl;
    for (auto it: nums2(v2))
        cout << it << " ";
    cout << endl;
    
    //思路3
    for (auto it: nums3(v1))
        cout << it << " ";
    cout << endl;
    for (auto it: nums3(v2))
        cout << it << " ";
    cout << endl;
    
    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
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
105
106
107
108
109
110
111
112
113
114

5.2 忘记题目了

大概是链表的问题