面试问题整理

项目相关 项目中用到的C++技术栈

1.vector扩容机制（扩容用到的STL器件？没答出来）

• 两倍扩容问题:
  • 为什么呈倍数扩容(时间复杂度更优)
    • 对于n次插入操作, 采用成倍方式扩容可以保证时间复杂度O(n), 而指定大小扩容的时间复杂度为O(n^2)
  • 为什么是1.5倍扩容(空间可重用)
    • 当k == 2时:
      • 第n次扩容的时候需要分配的内存是：an = a1*q^(n-1) = 4*2^(n-1)
      • 而前n-1项的内存和为：Sn = a1*(1-q^(n-1))/(1-q) = 4*(1-2^(n-1)) /(1-2) = 4*2^(n-1)-4
      • 差值 = an - Sn = 4 > 0
      • 所以第n次扩容需要的空间恰好比前n-1扩容要求的空间总和要大，那么即使在前n-1次分配空间都是连续排列的最好情况下，也无法实现之前的内存空间重用
    • 当k = 1.5时:
      • 第n次扩容的时候需要分配的内存是：an = a1*q^(n-1) = 4*1.5^(n-1)
      • 而前n-1项的内存和为：Sn = a1*(1-q^(n-1))/(1-q) = 4*(1-1.5^(n-1)) /(1-1.5) = 8*1.5^(n-1)-8
      • 差值 = an - Sn = 8 - 4*1.5^(n-1)
      • 当n增长到一定的数值后，差值就会变为小于0，那么如果前n-1次分配的空间都是连续的情况下, 就可以实现内存空间复用

　　　   1) 新增元素：vector 通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；

　　　　2) 对vector 的任何操作，一旦引起空间重新配置，指向原vector 的所有迭代器就都失效了；

　　　　3) 初始时刻vector 的capacity 为0，塞入第一个元素后capacity 增加为1；

　　　　4) 不同的编译器实现的扩容方式不一样，VS2015 中以1.5 倍扩容，GCC 以2 倍扩容。对比可以发现采用采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。　

2.讲讲static关键字

• 主要可以分为五个类型: 全局静态变量, 局部静态变量, 静态函数, 静态成员变量, 静态成员函数
  1. 全局静态变量
  • 在全局变量前加上关键字static，全局变量就定义成一个全局静态变量.
  • 内存中的位置：静态存储区，在整个程序运行期间一直存在。
  • 初始化：未经初始化的全局静态变量会被自动初始化为0(对于自动对象,如果没有显示初始化,会调用零参数构造函数,如不存在则编译失败);
  • 作用域：全局静态变量在声明他的文件之外是不可见的，准确地说是从定义之处开始，到文件结尾。
    1. 局部静态变量
  • 在局部变量之前加上关键字static，局部变量就成为一个局部静态变量。
  • 内存中的位置：静态存储区
  • 初始化：未经初始化的全局静态变量会被自动初始化为0(对于自动对象,如果没有显示初始化,会调用零参数构造函数,如不存在则编译失败)；
  • 作用域：作用域仍为局部作用域，
    • 当定义它的函数或者语句块结束的时候，作用域结束。
    • 但是当局部静态变量离开作用域后，并没有销毁，而是仍然驻留在内存当中，只不过我们不能再对它进行访问，直到该函数再次被调用，并且值不变；

1. 静态函数
   • 在函数返回类型前加static，函数就定义为静态函数。函数的定义和声明在默认情况下都是extern的，但静态函数只是在声明他的文件当中可见，不能被其他文件所用。
   • 函数的实现使用static修饰，那么这个函数只可在本cpp内使用，不会同其他cpp中的同名函数引起冲突；
   • warning：不要再头文件中声明static的全局函数，不要在cpp内声明非static的全局函数，如果你要在多个cpp中复用该函数，就把它的声明提到头文件里去，否则cpp内部声明需加上static修饰；
2. 类的静态成员
   • 在类中，静态成员可以实现多个对象之间的数据共享，并且使用静态数据成员还不会破坏隐藏的原则，即保证了安全性。
   • 因此，静态成员是类的所有对象中共享的成员，而不是某个对象的成员。对多个对象来说，静态数据成员只存储一处，供所有对象共用
3. 类的静态函数
   • 静态成员函数和静态数据成员一样，它们都属于类的静态成员，它们都不是对象成员。因此，对静态成员的引用不需要用对象名。
   • 在静态成员函数的实现中不能直接引用类中说明的非静态成员，可以引用类中说明的静态成员(这点非常重要)。*如果静态成员函数中要引用非静态成员时，可通过对象来引用。从中可看出，调用静态成员函数使用如下格式：::();*参数表>静态成员函数名>类名>
   • 不能被virtual修饰,静态成员函数没有this 指针，虚函数的实现是为每一个对象分配一个vptr 指针，而vptr 是通过this 指针调用的，所以不能为virtual；虚函数的调用关系，this->vptr->ctable->virtual function

3.C++ STL容器和区别 迭代器

• vector 底层数据结构为数组，支持快速随机访问
• list 底层数据结构为双向链表，支持快速增删
• deque 底层数据结构为一个中央控制器和多个缓冲区，详细见STL 源码剖析P146，支持首尾(中间不能)快速增删，也支持随机访问, deque 是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式 如下:[堆1] --> [堆2] -->[堆3] --> ..., 每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list 和vector 的结合品.
• stack 底层一般用list 或deque 实现，封闭头部即可，不用vector 的原因应该是容量大小有限制，扩容耗时
• queue 底层一般用list 或deque 实现，封闭头部即可，不用vector 的原因应该是容量大小有限制，扩容耗时(stack 和queue 其实是适配器,而不叫容器，因为是对容器的再封装)
• priority_queue 的底层数据结构一般为vector 为底层容器，堆heap 为处理规则来管理底层容器实现
• set 底层数据结构为红黑树，有序，不重复
• multiset 底层数据结构为红黑树，有序，可重复
• map 底层数据结构为红黑树，有序，不重复
• multimap 底层数据结构为红黑树，有序，可重复
• hash_set 底层数据结构为hash 表，无序，不重复
• hash_multiset 底层数据结构为hash 表，无序，可重复
• hash_map 底层数据结构为hash 表，无序，不重复
• hash_multimap 底层数据结构为hash 表，无序，可重复

4.智能指针，shared_ptr 怎么解决其线程安全问题（weak_ptr）

5.程序从源代码到可执行文件的过程

6.防止内存泄露的方法

使用智能指针

7.C和C++申请动态内存的方法和不同

8.C++内存空间

• 栈区(stack)— 由编译器自动分配释放，存放函数的参数值，局部变量的值等其操作方式类似于数据结构中的栈。
• 堆区(heap) — 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS(操作系统)回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
• 全局区(静态区)(static)—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
• 文字常量区—常量字符串就是放在这里的。程序结束后由系统释放。
• 程序代码区—存放函数体的二进制代码

9.数组和链表的区别

10.C++多态的几种方式

理解的虚函数和多态

• 多态的实现主要分为动态多态和静态多态, 静态多态就是重载, 在编译的时候就已经确定了, 动态多态是用虚函数机制实现的, 在运行期间动态绑定. 例如如果父类中定义了虚函数,而派生类重写了此函数,此时通过一个指向派生类对象的父类指针调用此函数式, 子类中重写的函数将被调用.
• 虚函数的实现: 在存在虚函数的类中会存在一个指向虚函数表的指针, 虚函数表中存放了虚函数的地址,当子类继承父类时也会继承其虚函数表, 当子类重写父类的虚函数时, 会将其继承的虚函数表中的地址替换为重写的函数地址. 使用虚函数,会增加访问内存的开销, 降低效率.

11.基类析构函数可以声明为虚函数吗