1、多态的表现

        定义：多态、封装和继承是面向对象的三大特性。多态需满足三个条件：（1）有继承；（2）有重写；（3）有父类引用指向子类对象。最终多态体现为父类引用可以指向子类对象：父类类型变量名 = new 子类类型()。

        ①运行时多态（虚函数）：运行时多态就是派生类重写基类的虚函数，在调用函数里，参数为基类的指针或引用，会构成多态。

举例：比如买票这个行为，成人去买就是全价，学生买就是半价票。但是不管成人还是学生都是人这个体系。所以我们需要根据谁来买票才能决定价格，这个时候就需要多态。

#include <iostream>

class ticket

{

public:

virtual void price() = 0;

};

class adult : public ticket

{

public:

virtual void price() override

{

std::cout << "成人全价！" << std::endl;

}

};

class student : public ticket

{

public:

virtual void price() override

{

std::cout << "学生半价！" << std::endl;

}

};

void BuyTicket(ticket& t)

{

t.price();

}

int main(void)

{

adult a;

student s;

BuyTicket(a);

BuyTicket(s);

return 0;

}

        ②编译时多态（模板）：编译时多态就是模板。在程序编译时，编译器根据参数的类型，就将生成某种类型的函数或类。

举例：Add() 函数是一个非常简单的函数，但是如果你写一个整型的 Add 函数，那么我想加 double 型的呢？你再写一个 double 型的 Add 函数，那么我想加 char 型的呢？

这个时候就用到了模板，我们先定义一个逻辑，具体类型等编译时再生成该类型的函数或类。

#include <iostream>

template<class T>

T Add(T lhs, T rhs)

{

return lhs + rhs;

}

int main(void)

{

Add(1, 2);

Add(2.0, 3.0);

Add('a', 'b');

return 0;

}

        ③重载：函数名相同，参数不同就构成了重载。重载主要用于函数，当某个函数的功能无法处理某些参数的情况时，我们就可以重载一个函数来单独处理。

举例：比如说上面的 Add 函数，当前内置类型都可以处理，但是如果我传两个字符串怎么办？就不可以像刚才那么加了。得重载一个函数单独处理。

#include <iostream>

#include <string>

int Add(int lhs, int rhs)

{

return lhs + rhs;

}

std::string Add(const std::string& lhs, const std::string& rhs)

{

std::string ans(lhs);

ans += rhs;

return ans;

}

int main(void)

{

Add(1, 2);

Add("abc", "def");

return 0;

}

        ④类型转换：

类型转换主要分为四种：

static_cast: 相当于隐式类型转换。

const_cast: 这个可以去除一个const变量的const性质，使可以改变它的值。

reinterpret_cast: 相当于强制类型转换。

dynamic_cast: 这个可以使子类指针或引用赋值给父类指针或引用。

2、构造函数和析构函数可以用虚函数吗？为什么

        构造函数不可以是虚函数，而析构函数可以且常常是虚函数。

        构造函数（不可以是虚函数）：

①从vptr角度解释：

虚函数的调用是通过虚函数表来查找的，而虚函数表由类的实例化对象的vptr指针(vptr可以参考C++的虚函数表指针vptr)指向，该指针存放在对象的内部空间中，需要调用构造函数完成初始化。如果构造函数是虚函数，那么调用构造函数就需要去找vptr，但此时vptr还没有初始化！

②从多态角度解释：

虚函数主要是实现多态，在运行时才可以明确调用对象，根据传入的对象类型来调用函数，例如通过父类的指针或者引用来调用它的时候可以变成调用子类的那个成员函数。而构造函数是在创建对象时自己主动调用的，不可能通过父类的指针或者引用去调用，因此使用虚函数也没有实际意义。并且构造函数的作用是提供初始化，在对象生命期仅仅运行一次，不是对象的动态行为，没有必要成为虚函数。

        析构函数（可以且常常是虚函数）：

此时 vtable 已经初始化了，完全可以把析构函数放在虚函数表里面来调用。C++类有继承时，基类的析构函数必须为虚函数。如果不是虚函数，则使用时可能存在内存泄漏的问题。假设我们有这样一种继承关系：

        如果我们以这种方式创建对象：

        SubClass* pObj =new SubClass();

        delete pObj;

        不管析构函数是否是虚函数(即是否加virtual关键词)，delete时基类和子类都会被释放；

        如果我们要实现多态，令基类指针指向子类，即以这种方式创建对象：

        BaseClass* pObj= new SubClass();

        delete pObj;

        若析构函数是虚函数(即加上virtual关键词)，delete时基类和子类都会被释放；

        若析构函数不是虚函数(即不加virtual关键词)，delete时只释放基类，不释放子类，会造成内存泄漏问题。

        因此，主动调用析构函数时，要注意以下几点：

（1）基类的析构函数不是虚函数的话，删除指向子类的基类指针时，只有基类的内存被释放，派生类的没有。这样就内存泄漏了。

（2）析构函数不是虚函数的话，因为指针类型是基类，所以直接调用基类析构函数代码。

（3）养成习惯：基类的析构函数一定有virtual。

3、分别讲一下vector、list和map

Vector：

    特点：地址不变，内存空间连续，所以在中间进行插入和删除时会造成内存块拷贝，如果插入的是结构体或者类，则会造成构造和析构，性能不是特别高，对结尾元素操作最快。

    优点：支持随机访问，即下标访问和迭代器访问，所以查询效率高。

    缺点：往头部或中部插入或删除元素时，为了保持原本的相对次序，插入或删除之后的所有元素都必须移动，所以插入效率比较低。

    适用场景：适用于对象简单，变化较小，并且频繁随机访问的场景。

List：

    特点：List是双向链表实现而成。元素存放与堆区，每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问。没有提供迭代器，每删除一个元素都会释放它占用的内存，可以在任意地方插入和删除，访问头尾两个元素最快，其他元素的访问时间一样。

    优点：内存不连续，动态操作，可以在任意位置插入或删除且效率高。

    缺点：不支持随机访问。

    适用场景：经常进行插入和删除并且不经常随机访问的场景。

Map：

    Map由红黑树实现，其元素都是“键值/实值”，所形成的一个对祖（key/value paris)。每个元素都有一个键，是排序准则的基础。每个键只能出现一次，不允许重复。Map主要用于资料一对一映射的情况，Map内部自建一棵红黑树，这棵树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。比如一个班级中，每个学生的学号跟他的姓名就存在着一对一映射的关系。

    优点：使用平衡二叉树实现，便于元素查找，且能把一个值映射成另一个值。

    缺点：每次插入都需要调整红黑树，效率有一定影响。

4、map和unordered_map的区别

    ①需要引入的头文件不同：

map：#include< map >

unordered_map：#include < unordered_map >

    ②内部实现机理不同：

map：map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map：unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。

    ③优缺点及用处：

Map优点：

    ·有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。

    ·红黑树，内部实现一个红黑树使得map的很多操作在logn的时间复杂度下就可以实现，因此效率非常的高。

缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间。

适用处：对于那些有顺序要求的问题，用map会更高效一些。

unordered_map：

    优点：因为内部实现了哈希表，因此其查找速度非常的快。

    缺点：哈希表的建立比较耗费时间。

    适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。

总结：

内存占有率的问题就转化成红黑树 VS hash表, 还是unorder_map占用的内存要高。但是unordered_map执行效率要比map高很多。对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的。

5、静态库和动态库的区别

静态库：

    其在链接阶段，会将生成的目标文件.o与引用到的库一起链接打包到可执行文件中，因此对应的链接方式是静态链接。

静态库特点：

    ①静态库对函数库的链接是放在编译时期完成的。

    ②程序在运行时与函数库再无瓜葛，移植方便。

    ③浪费空间和资源，因为所有相关的目标文件与牵扯到的函数库被链接合成一个可执行文件。

动态库：

    动态库在程序编译时并不会被链接到目标代码中，而是在程序运行时才被载入。不同的应用程序如果调用相同的库，那么在内存里面只需要有一份该共享库的示例，规避了空间浪费问题。

动态库特点：

    ①动态库把对一些库函数的链接载入推迟到程序运行时期。

    ②可以实现进程之间的资源共享。

    ③将一些程序升级变得简单。

6、Class和struct的区别

    class和struct最本质的区别: class是引用类型，它在堆中分配空间，栈中保存的只是引用；而struct是值类型，它在栈中分配空间。

什么是Class？

    class（类）是面向对象编程的基本概念，是一种自定义数据结构类型，通常包含字段、属性、方法、构造函数、索引器、操作符等。在.NET中，所有的类都最终继承自 System.Object 类，因此是一种引用类型，也就是说，new 一个类的实例时，在栈（stack）上存放该实例在托管堆（Managed Heap）中的地址，而实例的值保存在托管堆（Managed Heap）中。

托管堆（Managed Heap）：托管堆分配在被操作系统保留的一段内存区域中，这段内存区域是由 CLR 来管理的，这段内存称之为托管堆。

什么是struct？

    struct（结构）是一种值类型，用于将一组相关的变量组织为一个单一的变量实体。 所有的结构直接派生自System.ValueType，间接派生自System.Object，但结构是隐式密封的，不能作为基类再派生出其他的结构，也不能从类派生，但可以从接口派生。struct实例在创建时分配在线程的栈（stack）上，它本身存储了值。所以在使用struct 时，我们可以将其当作 int、char 这样的基本类型对待。

    class是引用类型，struct是值类型；既然 class 是引用类型，class 可以设为 null；但是我们不能将struct 设为 null，因为它是值类型。

    当你实例化一个 class，它将创建在【堆】上。而你实例化一个 struct，它将创建在【栈】上。

    你使用的是一个对 class 实例的引用。而你使用的不是对一个 struct 的引用（而是直接使用它们）。

    当我们将 class 作为参数传给一个方法，我们传递的是一个引用。struct 传递的是值而非引用。

    class可以定义析构器，但是struct不可以。

    class可以有显示的无参构造器，但是struct不可以。

    class的构造器不需要初始化全部字段，struct的构造器必须初始化所有字段。

    struct在声明时不能对实例字段进行赋值。

    class使用前必须new关键字实例化(静态类除外)，struct不需要。

    class支持继承和多态，struct 不支持。注意：但是 struct 可以和类一样实现接口。

    既然struct不支持继承，其成员不能以protected 或 protected internal 修饰。

    class 比较适合大的和复杂的数据，struct 适用于作为经常使用的一些数据组合成的新类型。

    struct 类型总是隐式密封的，因此在定义结构时不能使用 sealed 和 abstract 关键字。

    struct的函数成员不能声明为 abstract 和 virtual，但是可以使用 override 关键字，用以覆写它的基类 System.ValueType 中的方法。

适用场合：

    struct 有性能优势，class 有面向对象的扩展优势.

    由于结构是值类型，并且直接存储数据，因此在一个对象的主要成员为数据且数据量不大的情况下，使用结构会带来更好的性能.

    将一个结构变量赋值给另一个结构变量，就是把数据从一个结构复制到另一个结构。而类则不同，在类的变量之间，复制的是引用，而不是类数据.

    当把一个结构类型的变量赋值给另一个结构时，对性能的影响取决于结构的大小，当数据比较大的时候，这种数据复制机制会带来较大的开销.

    对于点、矩形和颜色这样的轻量对象，假如要声明一个含有许多个颜色对象的数组，则 CLR 需要为每个对象分配内存，在此情况下，使用结构的成本较低.

    当堆栈的空间很有限，且有大量的逻辑对象时，创建类要比创建结构好一些.

    在表现抽象和多级别的对象层次时，类是最好的选择，因为结构不支持继承.

    用于底层数据存储的类型设计为 struct 类型，将用于定义应用程序行为的类型设计为 class。如果对类型将来的应用情况不能确定，应该使用class.

7、Vector在超过当前容量时会做什么？为什么重新分配的大小空间是原来的两倍？

    扩容原理：

vector以连续的数组存放数据，当vector空间已满时会申请新的空间并将原容器中的内容拷贝到新空间中，并销毁原容器。

存储空间的重新分配会导致迭代器失效。

因为分配空间后需要进行拷贝，编译器会预分配更多空间以减少发生拷贝影响程序效率。

扩容的大小叫做扩容因子，扩容因子由编译器决定，VS的扩容因子为1.5，g++中，扩容因子为2。

    扩容因子：

·容因子大，每次需要分配的新内存空间越多，分配空间耗时。空闲空间较多，内存利用率低。

·扩容因子小，需要再分配的可能性更高，扩容耗时少。空闲空间较少，内存利用率较。

一般认为扩容因子1.5优于2.0，原因是以1.5作为扩容因子可以实现复用释放的内存空间。

    原因：

①vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度，相对于增长指定大小的O(n)时间复杂度更好。

②为了防止申请内存的浪费，现在使用较多的有2倍与1.5倍的增长方式，而1.5倍的增长方式可以更好的实现对内存的重复利用。

8、全局变量的优缺点

    定义：

全局变量也称为外部变量，它是在函数外部定义的变量。它不属于哪一个函数，它属于一个源程序文件。其作用域是整个源程序。在函数中使用全局变量，一般应作全局变量说明。只有在函数内经过说明的全局变量才能使用。全局变量的说明符为extern。但在一个函数之前定义的全局变量，在该函数内使用可不再加以说明。

    优点：

1）全局变量顾名思义全局可见的变量，全局变量生命周期长，自开始时创建直到全部函数运行结束后才被释放。

2）任何一个函数或线程都可以读写全局变量，在一定程度上使得函数之间变量的同步变得更为简单。

3）对于初学者较为友好，定义和使用起来都较为简单，且在项目只包含单个或少数几个源文件和头文件时弊端并不明显。

4）全局变量内存地址固定，读写效率比较高。

5）可以减少变量的个数，减少由于实际参数和形式参数的数据传递带来的时间消耗。

    缺点：

1）长期占用内存

由于之前提到的全局变量生命周期长，这使得在整个程序运行的过程中全局变量一直存在，始终占有那块存储区，难以被释放。

2）难以定位修改

由于全局变量定义在函数之外，使得全局变量是公共的，即全部函数都可以访问，难以定位全局变量在哪里被修改，加大了调试的难度。

3）不利于后期的维护

在前期编写全局变量时确实是一种“快捷通道”，但是在后期维护程序时哪怕仅是增加修改删除小功能，往往要从上到下掘地三尺地修改，涉及大多数模块，而原有的代码注释却忘了更新修改，而这对于后来的维护者，就像一团迷雾一样。

4）降低函数的可读性

使用全局变量的函数，需要关注全局变量的值，增加了理解的难度。

5）破坏函数的封装性能

函数类似于一个黑匣子，一般是通过函数参数和返回值进行输入输出，函数内部实现相对独立。但函数中如果使用了全局变量，那么函数体内的语句就可以绕过函数参数和返回值进行存取，这种情况增加了耦合性，也破坏了函数的独立性，使函数对全局变量产生依赖。同时，也降低了该函数的可移植性。

6）降低函数的可移植性

原因与上一条差不多，破坏了函数的封装性能以及增加了函数对全局变量的依赖的同时，也就使得将函数移植到可操作性降低。

7）增加程序之间的耦合性

使用全局变量会修改全部变量会影响所有用到它的模块，不利于调试，这种弊端在初学时仅有单个源程序和头文件的情况不明显，但是在以后代码量上来了之后，可能会被相互间错的全局变量的使用搞到头秃。

9、如何定位内存泄漏

    常见的内存错误：

（1）内存分配未成功，却使用了它

（2）内存分配成功，但尚未初始化就引用它

（3）内存分配成功且初始化，但操作越过了内存的边界

（4）忘记释放内存，造成内存泄漏

（5）释放了内存却继续使用它

    以发生的方式来分类：

（1）常发性内存泄漏，发生内存泄漏的代码会被多次执行到，每次执行都会导致一块内存泄漏

（2）偶发性内存泄漏

（3）一次性内存泄漏，发送泄漏的代码只会被执行一次

（4）隐式内存泄漏，程序在运行过程中不停地分配内存，但直到结束时才释放内存。

    方法：

一、重载new/delete操作符

重载new/delete操作符，用list或者map记录对内存的使用情况。new一次，保存一个节点，delete一次，就删除节点。

最后检测容器里是否还有节点，如果有节点就是有泄漏。也可以记录下哪一行代码分配的内存被泄漏。

类似的方法：在每次调用new时加个打印，每次调用delete时也加个打印。

二、用mtrace定位内存泄漏

三、查看进程maps表

在实际调试过程中，怀疑某处发生了内存泄漏，可以查看该进程的maps表，看进程的堆或mmap段的虚拟地址空间是否持续增加。如果是，说明可能发生了内存泄漏。如果mmap段虚拟地址空间持续增加，还可以看到各个段的虚拟地址空间的大小，从而可以确定是申请了多大的内存。

四、valgrind工具

10、多线程

11、class

①class A{ }    sizeof(A) = ?

sizeof(A) = 1

②class A{ public:   void fun(); }    sizeof(A) = ?

sizeof(A) = 1

12、手撕代码

二叉树的最小深度

int minDepth(TreeNode* root) {

    if(root == nullptr)

        return 0;

    if(root->left == nullptr)

        return minDepth(root->right) + 1;

    if(root->right == nullptr)

        return minDepth(root->left) + 1;

    else

        {

        return min(minDepth(root->left), minDepth(root->right))+1;

        }

    }

二叉树的最大深度

int maxDepth(TreeNode* root) {

    if(root == nullptr)

      return 0;

    return max(maxDepth(root->left), maxDepth(root->right)) + 1;//左支或右支最大长度加一

    }