今天分享一位百度春招面经,读者的技术栈是C++。
这次的面经,主要都是问操作系统、网络编程、C++ 这三大方向。
能明显感觉到,C++面试和Java或者Go面试重点,Java/Go主要是问MySQL、Redis。
一、介绍一下webserver项目
- 服务器开始运行,创建(初始化)线程池(IO密集型,线程数n+1);
- 创建 epoll 对连接进行监听
- 监听到连接事件,调用线程池线程处理 http 请求
- 读取 http 请求并对其进行解析 (空格,\r\n字段提取)
- 返回解析结果
二、select、poll、epoll的选择
select缺点:
- select() 检测数量有限制,最大值通常为 1024(bit),每一个比特位对应一个监听的文件描述符
- fd_set被内核修改后,不可以重用,每次都需要重置
- 每次调用select,都需要把fd集合从用户态拷贝到内核态,这个开销在fd很多时会很大
- 每次调用select都需要在内核遍历传递进来的所有fd,这个开销在fd很多时也很大(((时间复杂度是O(n))))
poll缺点:select第三四条缺点没有解决
- 每次调用select,都需要把**fd集合从用户态拷贝到内核态,这个开销在fd很多时会很大
- 每次调用select都需要在内核遍历传递进来的所有fd,这个开销在fd很多时也很大(((时间复杂度是O(n))))
epoll优点:epoll底层数据结构
- 红黑树增删改综合效率高
- 就绪的描述符的链表。当有的连接就绪的时候,内核会把就绪的连接放到 rdllist 链表里。这样应用进程只需要判断链表就能找出就绪进程,而不用去遍历整棵树。
三、线程和进程的区别?使用线程的心得?
- 进程是资源(包括内存、打开的文件等)分配的单位,线程是 CPU 调度的单位;
- (关键词:进程独立空间、线程之前共享空间资源)进程拥有一个独立完整的资源平台,不和其他进程共享;而线程只独享必不可少的资源,如寄存器和栈,而一个进程里可以有多个线程,彼此共享同一个地址空间。
- 线程同样具有就绪、阻塞、执行三种基本状态,同样具有状态之间的转换关系;
- 线程能减少并发执行的时间和空间开销
对于,线程相比进程能减少开销,体现在:
- (1. 创建时间少)线程的创建时间比进程快,因为进程在创建的过程中,还需要资源管理信息,比如内存、文件管理信息切换虚拟地址空间,切换内核栈和硬件上下文,页表切换开销很大,而线程在创建的过程中,不会涉及这些信息,而是共享它们,只需保存和设置少量寄存器内容,因此开销很小;
- (2. 终止时间少)线程的终止时间比进程快,因为线程释放的资源相比进程少很多;
- (3. 不需要切换页表,切换时间块)同一个进程内的线程切换比进程切换快,因为线程具有相同的地址空间(虚拟内存共享),这意味着同一个进程的线程都具有同一个页表,那么在切换的时候不需要切换页表。而对于进程之间的切换,切换的时候要把页表给切换掉,而页表的切换过程开销是比较大的;
- (4. 共享、线程之间数据传递效率高)由于同一进程的各线程间共享内存和文件资源,那么在线程之间数据传递的时候,就不需要经过内核了,这就使得线程之间的数据交互效率更高了;
所以,不管是时间效率,还是空间效率线程比进程都要高
心得:线程使用有一定难度,需要处理数据一致性问题,比如要使用互斥锁和条件变量等同步机制保证线程安全(原子性操作)
四、C++ 空类的大小?一个只包含int 变量的空class和只包含int变量的空struct的内存各占多大?
关键词:空类和空结构体都大小为1,这样可以确保两个不同的对象,拥有不同的地址。
1.空类
- C++空类的大小不为0,不同编译器设置不一样,vs和lg++都是设置为1;
- C++标准指出,不允许一个对象(当然包括类对象)的大小为0,不同的对象不能具有相同的地址;
- 带有虚函数的C++类大小不为1,因为每一个对象会有一个vptr指向虚函数表,具体大小根据指针大小确定;
- C++中要求对于类的每个实例都必须有独一无二的地址,那么编译器自动为空类分配一个字节大小,这样便保证了每个实例均有独一无二的内存地址。
在C++中空类会占一个字节,这是为了让对象的实例能够相互区别。具体来说,空类同样可以被实例化,并且每个实例在内存中都有独一无二的地址,因此,编译器会给空类隐含加上一个字节,这样空类实例化之后就会拥有独一无二的内存地址。当该空白类作为基类时,该类的大小就优化为0了,子类的大小就是子类本身的大小。这就是所谓的空白基类最优化。
空类的实例大小就是类的大小,所以sizeof(a)=1字节**,如果a是指针,则sizeof(a)就是指针的大小,即4字节。**
2.含有虚函数的类的大小
因为有虚函数的类对象中都有一个虚函数表指针 __vptr,其大小是4字节
3.只含有一个int成员变量的类的大小(4)
只是一个int变量的大小——4字节
4.只含有一个静态成员变量的类的大小(1)
静态成员存放在静态存储区,不占用类的大小, 普通函数也不占用类大小
静态成员a不占用类的大小,所以类的大小就是b变量的大小 即4个字节
五、为什么一般构造函数定义为虚函数?析构函数不定义为虚函数?
为什么析构函数一般写为虚函数?
如果析构函数不被声明成虚函数,则编译器实施静态绑定,在删除基类指针时,只会调用基类的析构函数而不调用派生类析构函数,这样就会造成派生类对象析构不完全,造成内存泄漏。
所以在实现多态时,当用基类操作派生类,在析构时防止只析构基类而不析构派生类的状况发生,要将基类的析构函数声明为虚函数。
为什么构造函数不写为虚函数?
从存储空间角度:虚函数对应一个vtable,可是这个vtable其实是存储在对象的内存空间的。问题出来了,如果构造函数是虚的,就需要通过 vtable来调用,可是对象还没有实例化,也就是内存空间还没有,无法找到vtable,所以构造函数不能是虚函数。
从使用角度:虚函数的作用在于通过父类的指针或者引用来调用它的时候能够变成调用子类的那个成员函数。而构造函数是在创建对象时自动调用的,不可能通过父类的指针或者引用去调用,因此也就规定构造函数不能是虚函数。
六、static的作用(作用域限制)
static
- 不考虑类的情况
有时候希望某些全局变量或者函数只在本文件中被使用,而不能被其他外部文件引用,这个时候可以在全局变量前加一个static说明,这样不同的人编写不同的变量或者函数时不用担心重名的问题,即使重名了也互不干扰
默认初始化为0,包括未初始化的全局静态变量与局部静态变量,都存在全局未初始化区
静态变量在函数内定义,始终存在,且只进行一次初始化,具有记忆性,其作用范围与局部变量相同,函数退出后仍然存在,但不能使用
- 考虑类的情况
static成员变量:只与类关联,不与类的对象关联。定义时要分配空间,不能在类声明中初始化,必须在类定义体外部初始化,初始化时不需要标示为static;可以被非static成员函数任意访问。
static成员函数:不具有this指针,无法访问类对象的非static成员变量和非static成员函数;不能被声明为const、虚函数和volatile;可以被非static成员函数任意访问
静态局部变量:
- 静态局部变量属于静态存储类别,在静态存储区内分配存储单元,在整个程序运行期间始终存在。
- 静态局部变量只初始化一次,并且之后再次调用函数时不再重新分配空间和赋初值,而保留上次函数调用结束时的值(而普通局部变量每调用一次就会重新分配空间并赋一次初值)
- 静态局部变量默认初始化为0
- 函数调用结束之后静态局部变量依然存在,但是只能在该函数内进行使用该静态局部变量,
extern的作用(作用域扩展)
- 将全局变量的作用域扩展到其定义之前:如果全局变量不在文件的开头定义,其作用范围只限定于从定义处到文件结尾,如果在定义点之前的函数想引用该变量,就应该在引用之前使用extern关键字对该变量进行声明,之后该全局变量的作用域就从声明处一直到文件结尾了
- 将某一个源文件中全局变量的作用域扩展到其他源文件中:一个C++项目很多情况是由多个源文件构成,如果在一个文件中想引用另一个文件中已定义的全局变量,比如现在两个文件都要使用到同一个全局变量int a,正确的做法应该是:在一个文件中定义变量a,而在另一个文件中使用extern int a;对该变量进行声明,这样就可以两个文件同时使用同一个变量了
const
- 不考虑类的情况
- const常量在定义时必须初始化,之后无法更改
- const形参可以接收const和非const类型的实参,例如// i 可以是 int 型或者 const int 型void fun(const int& i){ //...}
- 考虑类的情况
const成员变量:不能在类定义外部初始化,只能通过构造函数初始化列表进行初始化,并且必须有构造函数;不同类对其const数据成员的值可以不同,所以不能在类中声明时初始化。
const成员函数:const对象不可以调用非const成员函数;非const对象都可以调用;不可以改变非mutable(用该关键字声明的变量可以在const成员函数中被修改)数据的值。
七、C++ sort()函数实现
sort()源码中采用的是一种叫做IntroSort内省式排序的混合式排序算法,
1.首先进行判断排序的元素个数是否大于stl_threshold,stl_threshold是一个常量值是16,意思就是说我传入的元素规模小于我们的16的时候直接采用插入排序。(为什么用插入排序?因为插入排序在面对“几近排序”的序列时,表现更好,而快排是通过递归实现的,会为了极小的子序列产生很多的递归调用在区间长度小的时候经常不如插入排序效率高)
2.如果说我们的元素规模大于16,那就需要去判断如果是不是能采用快速排序,怎么判断呢?快排是使用递归来实现的,如果说我们进行判断我们的递归深度有没有到达递归深度的限制阈值2*lg(n),如果递归深度没达到阈值就使用快速排序来进行排序
3.如果说大于我们的最深递归深度阈值的话,这个时候说明快排复杂度退化了(比如很不巧基准元素多次选取到了当前区间中最小或最大的元素。这种情况下,每次划分只能将区间缩小1个元素,造成递归深度过深),就会采用我们的堆排序,堆排序是可以保证稳定O(nlogn)的时间复杂度的。