? 博客主页：?@披星戴月的贾维斯
? 欢迎关注：?点赞?收藏?留言
?系列专栏：? C/C++专栏
?请不要相信胜利就像山坡上的蒲公英一样唾手可得，但是请相信，世界上总有一些美好值得我们全力以赴，哪怕粉身碎骨！?
?一起加油，去追寻、去成为更好的自己！
文章目录
前言?1、为什么C++没有实现垃圾回收？?2、浅析STL源码中hash表?解决哈希冲突的方式（常考常问）拓展：STL vector迭代器失效的问题（常考常问） ?3、网络：TCP/IP五层(或四层)模型?4、三次握手的过程?5、四次挥手的过程?6、 TCP和UDP的区别（常问常考）?7、洛谷P2390地标访问（二分算法）?总结
提示：以下是本篇文章正文内容，下面案例可供参考
前言
这次我们将把之前没有聊到C++面经的几个点继续和朋友们分享，以及我最近在写一些题目，对于二分算法的理解更深刻了，和大家一起分享一下！希望要参加面试和参加蓝桥杯的同学都有所收获！
?1、为什么C++没有实现垃圾回收？
实现垃圾回收器会带来额外的时间和空间开销，因为需要一定的空间用来保存指针的引用计数和对他们进行标记，并且要单独开一个线程在空闲的时候进行free操作。不符合C++高效的特性，不适合做底层的工作。
C++是要兼容C语言的，这使得可以将一个类型转化为另一个类型，因此对于一个指针无法知道它真正指向的类型。这也就导致所有的指针没有共同的基类，并不知道要如何释放指针所指向的对象。
C++有析构、智能指针等方式来进行内存管理，对垃圾回收的需求不是很着急。
?2、浅析STL源码中hash表
STL中的hash就是unordered_map，使用哈希桶进行实现，其对传入的key值进行hash操作得到哈希值，从而得到存储的位置，实现O（1）的插入和访问操作。由于使用哈希桶来进行实现，当一个桶对应的拉链超过8个时，则会将链表转化为红黑树，从而提高查找的效率。
map则是使用红黑树来实现，红黑树相比于哈希表的一个优势在于红黑树能够实现自动排序，但其插入和查找的效率则取决于树的高度也就是log（n）。
?解决哈希冲突的方式（常考常问）
线性探测：当要插入的数据的哈希值对应的桶不能存放元素时，就继续往后面查找，直到找到了空桶。
二次探测：与线性探测类似，但每次并不是线性查找，而按照1,4,9的顺序进行探测。
双散列函数法：当第一个哈希函数得到的哈希值发生冲突时，就换另一个哈希函数。
拉链法：每一个哈希桶维护一个链表，哈希值找到对应的桶，并将元素头插到对应的链表中。如果链表过长，就将链表转化成红黑树。
建立公共溢出区：当发生冲突时，就将所有冲突的元素放到公共溢出区。
拓展：STL vector迭代器失效的问题（常考常问）
vector插入时，空间不够，重新申请空间并将原来的元素都移动到新的空间，此时指向原来内存的迭代器就都失效了。
插入时，end迭代器肯定失效。
vector删除时，被删除的元素以及后面元素的迭代器都会失效。
?3、网络：TCP/IP五层(或四层)模型
TCP/IP是一组协议的代名词，它还包括许多协议，组成了TCP/IP协议簇.
TCP/IP通讯协议采用了5层的层级结构，每一层都呼叫它的下一层所提供的网络来完成自己的需求。
?4、三次握手的过程
服务端调用socket（指定协议、套接字类型）创建套接字、分配文件描述符，bind（绑定套接字也就是文件信息和网络信息）绑定服务器的端口和ip地址，listen监听文件描述符，进入LISTEN状态，等待客户端的连接。
客户端调用connect（填写套接字、服务器的ip和端口号）向服务器发送连接请求（这个请求是一个带有SYN标志的报文），并且阻塞等待服务器的响应，客户端此时的状态为SYN_SENT。
服务器通过listen收到客户端发来的SYN报文并确认Seq字段，由LISTEN状态转变为SYN_RECVD状态，并向客户端发送SYN+ACK的报文，并且将连接放到半连接队列里。
客户端收到ACK+SYN报文后，发送ACK报文，并且变成ESTABLISHED状态，服务器收到客户端发送的ACK报文，进入ESTABLISHED状态，并且把连接从半连接队列取出放到全连接队列，等待accept取出。
后续客户端和服务器分别调用send和recv两个函数，进行通讯。
在三次握手的过程中，客户端和服务器还会将自己的序列号seq和窗口大小wind一起放到报文中进行沟通。
?5、四次挥手的过程
客户端调用close函数后，向服务器发送FIN数据包，此时客户端进入FIN_WAIT_1状态。
服务器收到FIN数据包，向客户端发送ACK报文，进入CLOSE_WAIT状态。
客户端收到ACK报文，进入FIN_WAIT_2状态，等待接收服务器的FIN报文。
服务器处理完数据以后，调用close函数，向客户端发送FIN报文，并进入LAST_ACK状态。
客户端收到FIN报文，最后向服务器发送ACK报文，并进入TIME_WAIT状态，2MSL后，进入CLOSED状态。
服务器收到ACK，断开连接关闭套接字，进入CLOSED状态。
?6、 TCP和UDP的区别（常问常考）
TCP是面向连接的协议，从而提供可靠的传输，在收发数据之前需要先通过三次握手建立连接，期间沟通seq序列号和窗口大小。而UDP是无连接的，不管对方有没有收到或者收到的数据是否正确。TCP提供流量控制、拥塞控制和超时重传等一系列方式来保证可靠性。TCP对系统资源的要求高于UDP，速度比UDP慢。TCP是面向字节流，而UDP是数据报。TCP的数据包没有边界，会出现粘包问题，UDP的包是独立的，不会出现粘包问题，但UDP的包要么不读要么就要一次性全读完。通常要解决TCP粘包问题，可以采用包和包之间增加分隔符、指定包的长度、每次发送定长的包来解决。在应用方面，如果强调数据的完整性和正确性，可以采用TCP，如果对性能要求比较高比如直播等允许一定丢包的情况，可以采用UDP。?7、洛谷P2390地标访问（二分算法）
?题目链接 ：地标访问
?题目背景
改编自 USACO2007Nov 铜组 Exploration
题目描述
贝西在一条道路上旅行，道路上有许多地标，贝西想要在日落之前访问尽可能多的路标。将道路视为一条数轴，贝西从原点出发，道路上有n(1≤n≤5×10）个地标，每个地标有一个坐标xi(|xi| <= 10^5), 且地标的坐标各不相同,(1≤T≤10^9) 分钟之后将会日落。
输入格式
第一行：两个整数 t,n
第二行至第 n+1 行：地标的坐标
输出格式
一个整数，贝西能访问的最多的地标数.
输入输出样例
输入 #1
25 14168-7310-15-176-1214-1329-5输出 #1
8?对样例分析
我们要在日落之前访问尽量多的坐标，样例给的T是25，就是我们要在25分钟内，总共有14块路标，每一个路标都有对应的位置，我们比如说是有3块路标，分别在1，2，3这些位置，那我们在访问 1 - 3时可以顺便把 2这块路标访问到，这样的时间也算3，对负数的处理在时间上也是要转为正数来算的，我们先sort每块路标的位置，得到
-17 -15 -13 -12 -7 -5 2 3 6 8 9 10 14 16答案8 就是左端点是-7开始到右端点是10，加起来8个数，而且贝西是先去最短的地方-7再去最远的10，这样子加起来的时间就是7 + 7 + 10 = 24 < 25成立。
?二分的再次理解：二分算法使用于具有二段性的题目，比如求最大值，最小值，最大值中的最小值等等，二分中的L 和 R的取值一定要在合理的区间内，R的值也最好是区间右端点，如果是求最小值，mid = (l + r) / 2， 不用 + 1.
while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid;}求最大值（枚举区间右端点）
while(l < r){int mid = l + r + 1;if(check(mid)) l = mid;else r = mid - 1;}?本题题解
#include<bits/stdc++.h>using namespace std;const int N = 5e4 + 10;int a[N];int n, t;bool cheak(int x)//能访问到x个坐标{ for(int r=x;r<=n;r++){//枚举右端点int l=r-x+1;if(a[r]<=0)//如果右端点在原点左边，就要一直向左走 if(-a[l]<=t)return true;//根据题意判断即可，可以就直接返回trueif(a[l]>=0)//如果左端点在原点右边，就要一直向右走 if(a[r]<=t)return true;//同上if(a[l]<=0&&a[r]>=0)//如果这段区间横跨了原点 if(min(a[r],-a[l])+a[r]-a[l]<=t)return 1;//那么我一定是先去距离原点短的那一边，再走到另一边}return 0;//如果整个循环执行完，没有找到可行解，那就返回false}int main (){ cin >> t >> n; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int l = -1, r = n + 1;//因为可能一个点也访问不了 //我们想找尽量大一点的值 while(l + 1 < r) { int mid = l + r >> 1; if(cheak(mid)) l = mid; else r = mid; } cout << l << endl; return 0;}?总结
本文向大家介绍了几个C/C++面试中可能会被问到的问题，还和大家一起继续深入理解二分算法，解决了地标访问这一题，希望对读者能有所帮助！