[面试]C/C++面试题补充（一）

总结了一些近几天遇到模糊的面试，随手记录一下。
时间：09-30

• 智能指针
• 智能指针的作用
• 说说你了解的auto_ptr
• 智能指针的循环引用如何解决
• 手写实现智能指针类需要实现哪些函数？
• 宏定义最小值和最大值
• 同步和异步
• 堆排序介绍及代码
• 三种基本状态
• 什么是自旋锁
• 用户态和内核态
• 超时重传的问题
• TCP快速重传为什么要三次
• epoll 水平（LT）和边沿触发（第二个回答好一点）
• 各种排序时间复杂度分析
• 为什么选择快排而非归并
• socket tcp http三者的区别

代码例子

• shared_ptr
• 实现原理： 采用引用计数器的方法，允许多个智能指针指向同一个对象，每当多一个指针指向该对象时，指向该对象的所有智能指针内部的引用计数加1，每当减少一个智能指针指向对象时，引用计数会减1，当计数为0的时候会自动的释放动态分配的资源。
  • 智能指针将一个计数器与类指向的对象相关联，引用计数器跟踪共有多少个类对象共享同一指针
  • 每次创建类的新对象时，初始化指针并将引用计数置为1
  • 当对象作为另一对象的副本而创建时，拷贝构造函数拷贝指针并增加与之相应的引用计数（链接有例子）
  • 对一个对象进行赋值时，赋值操作符减少左操作数所指对象的引用计数（如果引用计数为减至0，则删除对象），并增加右操作数所指对象的引用计数
  • 调用析构函数时，构造函数减少引用计数（如果引用计数减至0，则删除基础对象）
• unique_ptr
  • unique_ptr采用的是独享所有权语义，一个非空的unique_ptr总是拥有它所指向的资源。转移一个unique_ptr将会把所有权全部从源指针转移给目标指针，源指针被置空；所以unique_ptr不支持普通的拷贝和赋值操作，不能用在STL标准容器中；局部变量的返回值除外（因为编译器知道要返回的对象将要被销毁）；如果你拷贝一个unique_ptr，那么拷贝结束后，这两个unique_ptr都会指向相同的资源，造成在结束时对同一内存指针多次释放而导致程序崩溃。
• weak_ptr
  • weak_ptr：弱引用。 引用计数有一个问题就是互相引用形成环（环形引用），这样两个指针指向的内存都无法释放。需要使用weak_ptr打破环形引用。weak_ptr是一个弱引用，它是为了配合shared_ptr而引入的一种智能指针，它指向一个由shared_ptr管理的对象而不影响所指对象的生命周期，也就是说，它只引用，不计数。如果一块内存被shared_ptr和weak_ptr同时引用，当所有shared_ptr析构了之后，不管还有没有weak_ptr引用该内存，内存也会被释放。所以weak_ptr不保证它指向的内存一定是有效的，在使用之前使用函数lock()检查weak_ptr是否为空指针。
• auto_ptr
  • 主要是为了解决“有异常抛出时发生内存泄漏”的问题 。因为发生异常而无法正常释放内存。auto_ptr有拷贝语义，拷贝后源对象变得无效，这可能引发很严重的问题；而unique_ptr则无拷贝语义，但提供了移动语义，这样的错误不再可能发生，因为很明显必须使用std::move()进行转移。auto_ptr不支持拷贝和赋值操作，不能用在STL标准容器中。STL容器中的元素经常要支持拷贝、赋值操作，在这过程中auto_ptr会传递所有权，所以不能在STL中使用。

智能指针shared_ptr代码实现：
template
class SharedPtr
{
public:
    SharedPtr(T* ptr = NULL):_ptr(ptr), _pcount(new int(1))
    {}

    SharedPtr(const SharedPtr& s):_ptr(s._ptr), _pcount(s._pcount){
        (*_pcount)++;
    }

    SharedPtr& operator=(const SharedPtr& s){
        if (this != &s)
        {
            if (--(*(this->_pcount)) == 0)
            {
                delete this->_ptr;
                delete this->_pcount;
            }
            _ptr = s._ptr;
            _pcount = s._pcount;
            *(_pcount)++;
        }
        return *this;
    }
    T& operator*()
    {
        return *(this->_ptr);
    }
    T* operator->()
    {
        return this->_ptr;
    }
    ~SharedPtr()
    {
        --(*(this->_pcount));
        if (*(this->_pcount) == 0)
        {
            delete _ptr;
            _ptr = NULL;
            delete _pcount;
            _pcount = NULL;
        }
    }
private:
    T* _ptr;
    int* _pcount;//指向引用计数的指针
};

• C++11中引入了智能指针的概念，方便管理堆内存。使用普通指针，容易造成堆内存泄露（忘记释放），二次释放，程序发生异常时内存泄露等问题等，使用智能指针能更好的管理堆内存。

• 智能指针在C++11版本之后提供，包含在头文件中，shared_ptr、unique_ptr、weak_ptr。shared_ptr多个指针指向相同的对象。shared_ptr使用引用计数，每一个shared_ptr的拷贝都指向相同的内存。每使用他一次，内部的引用计数加1，每析构一次，内部的引用计数减1，减为0时，自动删除所指向的堆内存。shared_ptr内部的引用计数是线程安全的，但是对象的读取需要加锁。

• 初始化。智能指针是个模板类，可以指定类型，传入指针通过构造函数初始化。也可以使用make_shared函数初始化。不能将指针直接赋值给一个智能指针，一个是类，一个是指针。例如std::shared_ptr p4 = new int(1);的写法是错误的。

• unique_ptr“唯一”拥有其所指对象，同一时刻只能有一个unique_ptr指向给定对象（通过禁止拷贝语义、只有移动语义来实现 链接有例子）。相比与原始指针unique_ptr用于其RAII的特性，使得在出现异常的情况下，动态资源能得到释放。unique_ptr指针本身的生命周期：从unique_ptr指针创建时开始，直到离开作用域。离开作用域时，若其指向对象，则将其所指对象销毁(默认使用delete操作符，用户可指定其他操作)。unique_ptr指针与其所指对象的关系：在智能指针生命周期内，可以改变智能指针所指对象，如创建智能指针时通过构造函数指定、通过reset方法重新指定、通过release方法释放所有权、通过移动语义转移所有权。

• 智能指针类将一个计数器与类指向的对象相关联，引用计数跟踪该类有多少个对象共享同一指针。每次创建类的新对象时，初始化指针并将引用计数置为1；当对象作为另一对象的副本而创建时，拷贝构造函数拷贝指针并增加与之相应的引用计数；对一个对象进行赋值时，赋值操作符减少左操作数所指对象的引用计数（如果引用计数为减至0，则删除对象），并增加右操作数所指对象的引用计数；调用析构函数时，构造函数减少引用计数（如果引用计数减至0，则删除基础对象）。

• weak_ptr 是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象. 进行该对象的内存管理的是那个强引用的 shared_ptr. weak_ptr只是提供了对管理对象的一个访问手段。weak_ptr 设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少.

• auto_ptr的出现，主要是为了解决“有异常抛出时发生内存泄漏”的问题；抛出异常，将导致指针p所指向的空间得不到释放而导致内存泄漏；

• auto_ptr构造时取得某个对象的控制权，在析构时释放该对象。我们实际上是创建一个auto_ptr类型的局部对象，该局部对象析构时，会将自身所拥有的指针空间释放，所以不会有内存泄漏；

• auto_ptr的构造函数是explicit，阻止了一般指针隐式转换为 auto_ptr的构造，所以不能直接将一般类型的指针赋值给auto_ptr类型的对象，必须用auto_ptr的构造函数创建对象；

• 由于auto_ptr对象析构时会删除它所拥有的指针，所以使用时避免多个auto_ptr对象管理同一个指针；

• Auto_ptr内部实现，析构函数中删除对象用的是delete而不是delete[]，所以auto_ptr不能管理数组；

• auto_ptr支持所拥有的指针类型之间的隐式类型转换。

• 可以通过*和->运算符对auto_ptr所有用的指针进行提领操作；

• T* get(),获得auto_ptr所拥有的指针；T* release()，释放auto_ptr的所有权，并将所有用的指针返回。

• 换种说法

• 就是帮我们C++程序员管理动态分配的内存的，它会帮助我们自动释放new出来的内存，从而避免内存泄漏！

• 存在以下几个问题

  • 复制和赋值会改变资源的所有权，不符合人的直觉。
  • 在 STL 容器中使用auto_ptr存在重大风险，因为容器内的元素必需支持可复制（copy constructable）和可赋值（assignable）。
  • 不支持对象数组的操作 因为 delete 非 delete[]

• 常用三个操作

  • get() 获取智能指针托管的指针地址

  • release() 取消智能指针对动态内存的托管

    • reset() 重置智能指针托管的内存地址，如果地址不一致，原来的会被析构掉

• 几个建议

  • 尽可能不要将auto_ptr 变量定义为全局变量或指针；
  • 除非自己知道后果，不要把auto_ptr 智能指针赋值给同类型的另外一个 智能指针；（改变所有权）
  • C++11用更严谨的unique_ptr 取代了auto_ptr！

• 循环引用是指使用多个智能指针share_ptr时，出现了指针之间相互指向，从而形成环的情况，有点类似于死锁的情况，这种情况下，智能指针往往不能正常调用对象的析构函数，从而造成内存泄漏。例子上面的链接有
• 弱指针用于专门解决shared_ptr循环引用的问题，weak_ptr不会修改引用计数，即其存在与否并不影响对象的引用计数器。循环引用就是：两个对象互相使用一个shared_ptr成员变量指向对方。弱引用并不对对象的内存进行管理，在功能上类似于普通指针，然而一个比较大的区别是，弱引用能检测到所管理的对象是否已经被释放，从而避免访问非法内存。

• 智能指针是一个数据类型，一般用模板实现，模拟指针行为的同时还提供自动垃圾回收机制。它会自动记录SmartPointer对象的引用计数，一旦T类型对象的引用计数为0，就释放该对象。

• 除了指针对象外，我们还需要一个引用计数的指针设定对象的值，并将引用计数计为1，需要一个构造函数。新增对象还需要一个构造函数，析构函数负责引用计数减少和释放内存。

• 通过覆写赋值运算符，才能将一个旧的智能指针赋值给另一个指针

• 一个构造函数、拷贝构造函数、复制构造函数、析构函数、移动函数；

• #define MAX(A,B) ( (A) > (B) ? (A) : (B))
• #define MIN(A,B) ( (A) > (B) ? (B) : (A))

需要注意的是：
1 宏定义的变量在引用的时候，用（）括起来，防止预编译器展开的错误
2 （a > b ? action1 : action2 ） 这样的方式和 if —else 结果一样，但他会使得编译器产生更优化的代码，这在嵌入式编程中比较重要。

• 当然也有第二种实现方式：参考链接

• 同步：是所有的操作都做完了，写入服务器数据库当中才会通知用户执行成功，这样的话会造成服务器压力过大，而且用户的体验效果也不是很好。

• 异步：不用等待服务器数据库是否写入，而是先通知用户执行成功，随后在慢慢的写入服务器数据库，这样会减轻服务器的压力，同时对用户的体验效果很好。

• 第二种回答（更合适）

• 添加链接描述

• 阻塞和非阻塞 同步和异步（这个讲的非常好）

• 二三结合一起看，内核把数据拷到进程空间 然后再通过其他方式通知我 （回调函数 状态）

• 大堆顶 根结点是最大值 的堆，用于维护和查询 max、
• 第 i 个结点的 父结点 下标 为 （i-1）/2 ;
• 第 i 个结点的 左子结点 下标 为 2i+1 ;
• 第 i 个结点的 右子结点 下标 为 2i+2 ;
• 最后一个非叶子结点 下标为：n/2 -1（也可以理解成 最后一个节点坐标是 n-1 带入第一个公式 就是 （n-2）/2）
• 思想就是： 将一个长为n的序列构造成一个大顶堆，则整个序列的最大值就是堆顶的根结点。 将最大值结点与末尾结点的值互换，此时末尾结点的值就是最大值。(即数组的最后一个元素为最大值) 。然后将剩余的 n-1个序列重新构造成一个大顶堆，再将n-1序列的最大值与末尾结点的值互换，就会得到 次最大值。 如此重复执行，就可以得到一个有序序列了。
• 局部调整向下，从后向前建立（右下）

#include
#include 
using namespace std;
//调整的函数
//需要传入的参数
// 1数组 
// 2数组的调整的长度（最大下标+1）
// 3调整的起始点（下标）
 
void heapify(int* tree, int n, int i)
{
	if (i >= n) return;
	//左子结点
	int c1 = i * 2 + 1;
	//右子结点
	int c2 = i * 2 + 2;
	//假设最大值坐标是根结点，获取左右子结点的最大值
	int max = i;
	if (c1tree[max])
	{
		max = c1;
	}
	if (c2tree[max])
	{
		max = c2;
	}
	if (max != i)
	{
		//将左右子树的最大值赋给父结点
		swap(tree[max],tree[i]);
		//较小的值，被赋给左子树或右子树，则左子树或右子树 需要重新建堆 
		heapify(tree,n,max);
	}
 
}
 
void build_heap(int *tree, int n)
{
	int last_node = n - 1;
	//最后一个结点的父节点 下标，即最后一个非叶子结点
	int parent = (last_node - 1) / 2;
	
	//针对最后一个父节点的 及其前面的父节点进行建堆
	for (int i =parent; i>=0; i--)
	{
		heapify(tree,n,i);
	}
}
 

// 实现整体排序
void heap_sort(int *tree, int n)
{
	//建立一个堆 从后向前建立
	build_heap(tree,n);
	
	//循环不断把最大值放在最后 并且对第一个值进行局部调整
	for (int i = n-1; i>=0; i--)
	{
		//堆顶与末尾结点值交换
		swap(tree[i], tree[0]);
		//每次把第一个移到最后 最后一个移上来 然后进行局部调整
		heapify(tree,i,0);//注意这边的i 放入i的下标 剩余i个元素
	}
}
 
int main()
{
	int tree[] = { 7,10,15,30,35,23,40 };
	int n = 7;
	heap_sort(tree,n);
 
	for (int i=0;i 
参考链接
 
三种基本状态 
 
就绪态—>执行态：进程获得CPU（被调度程序选中）；
执行态—>阻塞态：向OS请求共享资源（互斥、同步）失败、等待某种操作完成、新数据尚未到达（I/O操作）、等待新任务的到达；
阻塞态—>阻塞态：上述的四类等待事件发生；
 执行态—>就绪态：分配给进程的时间片执行完成（轮转调度算法）、高优先级的进程到达（抢占式调度）。
 
什么是自旋锁 

 
 
参考链接
 
用户态和内核态 
参考链接
 
超时重传的问题 
当一个报文段丢失时，会等待一定的超时周期然后才重传分组，增加了端到端的时延。
当一个报文段丢失时，在其等待超时的过程中，可能会出现这种情况：其后的报文段已经被接收端接收但却迟迟得不到确认，发送端会认为也丢失了，从而引起不必要的重传，既浪费资源也浪费时间。
 
TCP快速重传为什么要三次 
冗余ACK的概念 
  
即当接收端收到比期望序号大的报文段时，便会重复发送最近一次确认的报文段的确认信号，我们称之为冗余ACK（duplicate ACK）。
 
什么是快速重传 
  
如果在超时重传定时器溢出之前，接收到连续的三个重复冗余ACK（其实是收到4个同样的ACK，第一个是正常的，后三个才是冗余的），发送端便知晓哪个报文段在传输过程中丢失了，于是重发该报文段，不需要等待超时重传定时器溢出，大大提高了效率。这便是快速重传机制。
 
为啥是三次 
  
 
即使发送端是按序发送，由于TCP包是封装在IP包内，IP包在传输时乱序，意味着TCP包到达接收端也是乱序的，乱序的话也会造成接收端发送冗余ACK。那发送冗余ACK是由于乱序造成的还是包丢失造成的，这里便需要好好权衡一番，因为把3次冗余ACK作为判定丢失的准则其本身就是估计值。
 
 
在没丢失的情况下，有40%的可能出现3次冗余ACK
 
 
在乱序的情况下必定是2次冗余ACK
 
 
在丢失的情况下，必定出现3次冗余ACK
 
 
基于这样的概率，选定3次冗余ACK作为阈值也算是合理的。在实际抓包中，大多数的快速重传都会在大于3次冗余ACK后发生。
 
 
 
epoll 水平（LT）和边沿触发（第二个回答好一点） 
参考1 有代码
 
epoll水平触发: 只要监听的文件描述符中有数据，就会触发epoll_wait有返回值，这是默认的epoll_wait的方式;
 
epoll边沿触发 : 只有监听的文件描述符的读/写事件发生，才会触发epoll_wait有返回值;
 
通过epoll_ctl函数，设置该文件描述符的触发状态即可
 
//水平触发
evt.events = EPOLLIN;    // LT 水平触发 (默认) EPOLLLT
evt.data.fd = pfd[0];

//边沿触发
evt.events = EPOLLIN | EPOLLET;    // ET 边沿触发
evt.data.fd = pfd[0];
 
 
管道+epoll的例子
 
 
 
 
换一种说法：参考2
 
 
Level_triggered(水平触发)：当被监控的文件描述符上有可读写事件发生时，epoll_wait()会通知处理程序去读写。如果这次没有把数据一次性全部读写完(如读写缓冲区太小)，那么下次调用 epoll_wait()时，它还会通知你在上没读写完的文件描述符上继续读写，当然如果你一直不去读写，它会一直通知你！！！如果系统中有大量你不需要读写的就绪文件描述符，而它们每次都会返回，这样会大大降低处理程序检索自己关心的就绪文件描述符的效率！！！
 
 
Edge_triggered(边缘触发)：当被监控的文件描述符上有可读写事件发生时，epoll_wait()会通知处理程序去读写。如果这次没有把数据全部读写完(如读写缓冲区太小)，那么下次调用epoll_wait()时，它不会通知你，也就是它只会通知你一次，直到该文件描述符上出现第二次可读写事件才会通知你（根据上一个说法 数据应该还是在的）！！！这种模式比水平触发效率高，系统不会充斥大量你不关心的就绪文件描述符！！！
 
 
 
各种排序时间复杂度分析 
1
 
 
为什么选择快排而非归并 

 2.《算法图解》说过另一个方面：虽然平均时间复杂度都是 O(logN), 但归并排序的常数部分比快排大，因而速度慢
 
socket tcp http三者的区别 
 
 
1、TCP/IP连接 ：手机能够使用联网功能是因为手机底层实现了TCP/IP协议，可以使手机终端通过无线网络建立TCP连接。TCP协议可以对上层网络提供接口，使上层网络数据的传输建立在“无差别”的网络之上。
 
 
2、HTTP连接：HTTP协议即超文本传送协议(Hypertext Transfer Protocol )，是Web联网的基础，也是手机联网常用的协议之一，HTTP协议是建立在TCP协议之上的一种应用。HTTP连接最显著的特点是客户端发送的每次请求都需要服务器回送响应，在请求结束后，会主动释放连接。从建立连接到关闭连接的过程称为“一次连接”。（1.1 就另说了）
 
 
3、SOCKET原理：套接字（socket）是通信的基石，是支持TCP/IP协议的网络通信的基本操作单元。它是网络通信过程中端点的抽象表示，包含进行网络通信必须的五种信息：连接使用的协议，本地主机的IP地址，本地进程的协议端口，远地主机的IP地址，远地进程的协议端口。
 
 
socket则是对TCP/IP协议的封装和应用（程序员层面上）。也可以说，TPC/IP协议是传输层协议，主要解决数据 如何在网络中传输，而HTTP是应用层协议，主要解决如何包装数据。
 
 
“我们在传输数据时，可以只使用（传输层）TCP/IP协议，但是那样的话，如 果没有应用层，便无法识别数据内容，如果想要使传输的数据有意义，则必须使用到应用层协议，应用层协议有很多，比如HTTP、FTP、TELNET等，也 可以自己定义应用层协议。WEB使用HTTP协议作应用层协议，以封装HTTP文本信息，然后使用TCP/IP做传输层协议将它发到网络上。”
 
 
TCP/IP只是一个协议栈，就像操作系统的运行机制一样，必须要具体实现，同时还要提供对外的操作接口。这个就像操作系统会提供标准的编程接口，比如win32编程接口一样，TCP/IP也要提供可供程序员做网络开发所用的接口，这就是Socket编程接口。
 
 
-参