大家好,我是小林。
今天分享一位百度春招面经,读者的技术栈是C++。
这次的面经,主要都是问操作系统、网络编程、C++ 这三大方向。
能明显感觉到,C++面试和Java或者Go面试重点,Java/Go主要是问MySQL、Redis。
select缺点:
poll缺点:select第三四条缺点没有解决
epoll优点:epoll底层数据结构
红黑树增删改综合效率高
就绪的描述符的链表。当有的连接就绪的时候,内核会把就绪的连接放到 rdllist 链表里。这样应用进程只需要判断链表就能找出就绪进程,而不用去遍历整棵树。
进程是资源(包括内存、打开的文件等)分配的单位,线程是 CPU 调度的单位;
(关键词:进程独立空间、线程之前共享空间资源)进程拥有一个独立完整的资源平台,不和其他进程共享;而线程只独享必不可少的资源,如寄存器和栈,而一个进程里可以有多个线程,彼此共享同一个地址空间。
线程同样具有就绪、阻塞、执行三种基本状态,同样具有状态之间的转换关系;
线程能减少并发执行的时间和空间开销
对于,线程相比进程能减少开销,体现在:
所以,不管是时间效率,还是空间效率线程比进程都要高
心得:线程使用有一定难度,需要处理数据一致性问题,比如要使用互斥锁和条件变量等同步机制保证线程安全(原子性操作)
关键词:空类和空结构体都大小为1,这样可以确保两个不同的对象,拥有不同的地址。
class A {};
int main(){
cout<<sizeof(A)<<endl;// 输出 1;
A a;
cout<<sizeof(a)<<endl;// 输出 1;
return 0;
}
在C++中空类会占一个字节,这是为了让对象的实例能够相互区别。具体来说,空类同样可以被实例化,并且每个实例在内存中都有独一无二的地址,因此,编译器会给空类隐含加上一个字节,这样空类实例化之后就会拥有独一无二的内存地址。当该空白类作为基类时,该类的大小就优化为0了,子类的大小就是子类本身的大小。这就是所谓的空白基类最优化。
空类的实例大小就是类的大小,所以sizeof(a)=1字节**,如果a是指针,则sizeof(a)就是指针的大小,即4字节。**
class A { virtual Fun(){} };
int main(){
cout<<sizeof(A)<<endl;// 输出 4(32位机器)/8(64位机器);
A a;
cout<<sizeof(a)<<endl;// 输出 4(32位机器)/8(64位机器);
return 0;
}
因为有虚函数的类对象中都有一个虚函数表指针 __vptr,其大小是4字节
3.只含有一个int成员变量的类的大小(4)
class A { int a; };
int main(){
cout<<sizeof(A)<<endl;// 输出 4;
A a;
cout<<sizeof(a)<<endl;// 输出 4;
return 0;
}
只是一个int变量的大小——4字节
4.只含有一个静态成员变量的类的大小(1)
class A { static int a; };
int main(){
cout<<sizeof(A)<<endl;// 输出 1;
A a;
cout<<sizeof(a)<<endl;// 输出 1;
return 0;
}
静态成员存放在静态存储区,不占用类的大小, 普通函数也不占用类大小
class A { static int a; int b; };;
int main(){
cout<<sizeof(A)<<endl;// 输出 4;
A a;
cout<<sizeof(a)<<endl;// 输出 4;
return 0;
}
静态成员a不占用类的大小,所以类的大小就是b变量的大小 即4个字节
如果析构函数不被声明成虚函数,则编译器实施静态绑定,在删除基类指针时,只会调用基类的析构函数而不调用派生类析构函数,这样就会造成派生类对象析构不完全,造成内存泄漏。
所以在实现多态时,当用基类操作派生类,在析构时防止只析构基类而不析构派生类的状况发生,要将基类的析构函数声明为虚函数。
从存储空间角度:虚函数对应一个vtable,可是这个vtable其实是存储在对象的内存空间的。问题出来了,如果构造函数是虚的,就需要通过 vtable来调用,可是对象还没有实例化,也就是内存空间还没有,无法找到vtable,所以构造函数不能是虚函数。
从使用角度:虚函数的作用在于通过父类的指针或者引用来调用它的时候能够变成调用子类的那个成员函数。而构造函数是在创建对象时自动调用的,不可能通过父类的指针或者引用去调用,因此也就规定构造函数不能是虚函数。
sort()源码中采用的是一种叫做IntroSort内省式排序的混合式排序算法,
1.首先进行判断排序的元素个数是否大于stl_threshold,stl_threshold是一个常量值是16,意思就是说我传入的元素规模小于我们的16的时候直接采用插入排序。(为什么用插入排序?因为插入排序在面对“几近排序”的序列时,表现更好,而快排是通过递归实现的,会为了极小的子序列产生很多的递归调用在区间长度小的时候经常不如插入排序效率高)
2.如果说我们的元素规模大于16,那就需要去判断如果是不是能采用快速排序,怎么判断呢?快排是使用递归来实现的,如果说我们进行判断我们的递归深度有没有到达递归深度的限制阈值2*lg(n),如果递归深度没达到阈值就使用快速排序来进行排序
3.如果说大于我们的最深递归深度阈值的话,这个时候说明快排复杂度退化了(比如很不巧基准元素多次选取到了当前区间中最小或最大的元素。这种情况下,每次划分只能将区间缩小1个元素,造成递归深度过深),就会采用我们的堆排序,堆排序是可以保证稳定O(nlogn)的时间复杂度的。
推荐阅读: