多态是指不同继承关系的类对象，去调用同一函数，产生了不同的行为。在继承中要想构成多态需要满足两个条件：

1. 必须通过基类的指针或者引用调用虚函数。
2. 被调用的函数必须是虚函数，且派生类必须对基类的虚函数进行重写。

虚函数重写的两个例外

协变（基类与派生类虚函数的返回值类型不同）

派生类重写基类虚函数时，与基类虚函数返回值类型不同。即基类虚函数返回基类对象的指针或者引用，派生类虚函数返回派生类对象的指针或者引用，称为协变。

析构函数的重写（基类与派生类析构函数的名字不同）

如果基类的析构函数为虚函数，此时派生类析构函数只要定义，无论是否加virtual关键字，都与基类的析构函数构成重写，虽然基类与派生类析构函数名字不同。

那父类和子类的析构函数构成重写的意义何在呢？试想以下场景：分别new一个父类对象和子类对象，并均用父类指针指向它们，然后分别用delete调用析构函数并释放对象空间。

int main()
{//分别new一个父类对象和子类对象，并均用父类指针指向它们Person* p1 = new Person;Person* p2 = new Student;//使用delete调用析构函数并释放对象空间delete p1;delete p2;return 0;
}

C++11 override和final
从上面可以看出，C++对函数重写的要求比较严格，有些情况下由于疏忽可能会导致函数名的字母次序写反而无法构成重写，而这种错误在编译期间是不会报错的，直到在程序运行时没有得到预期结果再来进行调试会得不偿失，因此，C++11提供了final和override两个关键字，可以帮助用户检测是否重写。

final：修饰虚函数，表示该虚函数不能再被重写。

override：检查派生类虚函数是否重写了基类的某个虚函数，如果没有重写则编译报错。

抽象类

在虚函数的后面写上=0，则这个函数为纯虚函数。包含纯虚函数的类叫做抽象类（也叫接口类），抽象类不能实例化出对象。

#include <iostream>
using namespace std;
//抽象类（接口类）
class Car
{
public://纯虚函数virtual void Drive() = 0;
};
int main()
{Car c; //抽象类不能实例化出对象，errorreturn 0;
}

接口继承和实现继承

实现继承： 普通函数的继承是一种实现继承，派生类继承了基类函数的实现，可以使用该函数。

接口继承： 虚函数的继承是一种接口继承，派生类继承的是基类虚函数的接口，目的是为了重写，达成多态。

建议： 所以如果不实现多态，就不要把函数定义成虚函数。

多态的原理

下面Base类当中有三个成员函数，其中Func1和Func2是虚函数，Func3是普通成员函数，子类Derive当中仅对父类的Func1函数进行了重写。

#include <iostream>
using namespace std;
//父类
class Base
{
public://虚函数virtual void Func1(){cout << "Base::Func1()" << endl;}//虚函数virtual void Func2(){cout << "Base::Func2()" << endl;}//普通成员函数void Func3(){cout << "Base::Func3()" << endl;}
private:int _b = 1;
};
//子类
class Derive : public Base
{
public://重写虚函数Func1virtual void Func1(){cout << "Derive::Func1()" << endl;}
private:int _d = 2;
};
int main()
{Base b;Derive d;return 0;
}

对象模型分析如下：

Func2是虚函数，所以继承下来后放进了子类的虚表，而Func3是普通成员函数，继承下来后不会放进子类的虚表。此外，虚函数表本质是一个存虚函数指针的指针数组，一般情况下会在这个数组最后放一个nullptr。

总结一下，派生类的虚表生成步骤如下：

1. 先将基类中的虚表内容拷贝一份到派生类的虚表。
2. 如果派生类重写了基类中的某个虚函数，则用派生类自己的虚函数地址覆盖虚表中基类的虚函数地址。
3. 派生类自己新增加的虚函数按其在派生类中的声明次序增加到派生类虚表的最后。

为什么必须使用父类的指针或者引用去调用虚函数呢？为什么使用父类对象去调用虚函数达不到多态的效果呢？

Person* p1 = &Mike;
Person* p2 = &Johnson;

使用父类指针或者引用时，实际上是一种切片行为，切片时只会让父类指针或者引用得到父类对象或子类对象中切出来的那一部分。

Person p1 = Mike;
Person p2 = Johnson;

使用父类对象时，切片得到部分成员变量后，会调用父类的拷贝构造函数（类型Person必定调用父类的拷贝构造函数）对那部分成员变量进行拷贝构造，而拷贝构造出来的父类对象p1和p2当中的虚表指针指向的都是父类对象的虚表。因为同类型的对象共享一张虚表，他们的虚表指针指向的虚表是一样的。

动态绑定和静态绑定

静态绑定： 静态绑定又称为前期绑定(早绑定)，在程序编译期间确定了程序的行为，也成为静态多态，比如：函数重载。

动态绑定： 动态绑定又称为后期绑定(晚绑定)，在程序运行期间，根据具体拿到的类型确定程序的具体行为，调用具体的函数，也称为动态多态。

相比不构成多态时的代码，构成多态时调用函数的那句代码翻译成汇编后就变成了八条汇编指令，主要原因就是我们需要在运行时，先到指定对象的虚表中找到要调用的虚函数，然后才能进行函数的调用。

bitset

 bitset（位图）的介绍与使用

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

要判断一个数是否在某一堆数中，我们可能会想到如下方法：

• 将这一堆数进行排序，然后通过二分查找的方法判断该数是否在这一堆数中。
• 将这一堆数插入到unordered_set容器中，然后调用find函数判断该数是否在这一堆数中。

位图解决

实际在这个问题当中，我们只需要判断一个数在或是不在，即只有两种状态，那么我们可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。

无符号整数总共有2的32次方个，因此记录这些数字就需要2的32次方个比特位，也就是512M的内存空间，内存消耗大大减少。

#include <iostream>
#include <bitset>
using namespace std;int main()
{bitset<8> bs;bs.set(2); //设置第2位bs.set(4); //设置第4位cout << bs << endl; //00010100bs.flip(); //反转所有位cout << bs << endl; //11101011cout << bs.count() << endl; //6cout << bs.test(3) << endl; //1bs.reset(0); //清空第0位cout << bs << endl; //11101010bs.flip(7); //反转第7位cout << bs << endl; //01101010cout << bs.size() << endl; //8cout << bs.any() << endl; //1bs.reset(); //清空所有位cout << bs.none() << endl; //1bs.set(); //设置所有位cout << bs.all() << endl; //1return 0;
}

bitset类的模拟实现

在构造位图时，我们需要根据所给位数N，创建一个N位的位图，并且将该位图中的所有位都初始化为0。

namespace xwy
{//模拟实现位图template<size_t N>class bitset{public://构造函数bitset();//设置位void set(size_t pos);//清空位void reset(size_t pos);//反转位void flip(size_t pos);//获取位的状态bool test(size_t pos);//获取可以容纳的位的个数size_t size();//获取被设置位的个数size_t count();//判断位图中是否有位被设置bool any();//判断位图中是否全部位都没有被设置bool none();//判断位图中是否全部位都被设置bool all();//打印函数void Print();private:vector<int> _bits; //位图};
}

其构造函数与设置位函数：

//构造函数
bitset()
{_bits.resize(N / 32 + 1, 0);
}//设置位
void set(size_t pos)
{assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] |= (1 << j); //将该位设置为1（不影响其他位）
}

布隆过滤器

在注册账号设置昵称的时候，为了保证每个用户昵称的唯一性，系统必须检测你输入的昵称是否被使用过，这本质就是一个key的模型，我们只需要判断这个昵称被用过，还是没被用过。

• 方法一：用红黑树或哈希表将所有使用过的昵称存储起来，当需要判断一个昵称是否被用过时，直接判断该昵称是否在红黑树或哈希表中即可。但红黑树和哈希表最大的问题就是浪费空间，当昵称数量非常多的时候内存当中根本无法存储这些昵称
• 方法二：用位图将所有使用过的昵称存储起来，虽然位图只能存储整型数据，但我们可以通过一些哈希算法将字符串转换成整型，比如BKDR哈希算法。当需要判断一个昵称是否被用过时，直接判断位图中该昵称对应的比特位是否被设置即可。

位图虽然能够大大节省内存空间，但由于字符串的组合形式太多了，一个字符的取值有256种，而一个数字的取值只有10种，因此无论通过何种哈希算法将字符串转换成整型都不可避免会存在哈希冲突。

布隆过滤器的实现

首先，布隆过滤器可以实现为一个模板类，因为插入布隆过滤器的元素不仅仅是字符串，也可以是其他类型的数据，只有调用者能够提供对应的哈希函数将该类型的数据转换成整型即可，但一般情况下布隆过滤器都是用来处理字符串的，所以这里可以将模板参数K的缺省类型设置为string。布隆过滤器中的成员一般也就是一个位图，我们可以在布隆过滤器这里设置一个非类型模板参数N，用于让调用者指定位图的长度

//布隆过滤器
template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter
{
public://...
private:bitset<N> _bs;
};

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？给出近似算法。

题目要求给出近视算法，也就是允许存在一些误判，那么我们就可以用布隆过滤器。

• 先读取其中一个文件当中的query，将其全部映射到一个布隆过滤器当中。
• 然后读取另一个文件当中的query，依次判断每个query是否在布隆过滤器当中，如果在则是交集，不在则不是交集。

如何扩展BloomFilte使得它支持删除元素的操作。

布隆过滤器一般不支持删除操作，原因如下：

• 因为布隆过滤器判断一个元素存在时可能存在误判，因此无法保证要删除的元素确实在布隆过滤器当中，此时将位图中对应的比特位清0会影响其他元素。
• 此外，就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素。

如果要让布隆过滤器支持删除，就必须要做到以下两点：

1. 保证要删除的元素在布隆过滤器当中，比如在删除一个用户的信息前，先遍历数据库确认该用户确实存在。
2. 保证删除后不会影响到其他元素，比如可以为位图中的每一个比特位设置一个对应的计数值，当插入元素映射到该比特位时将该比特位的计数值++，当删除元素时将该元素对应比特位的计数值–即可。

哈希切分

利用哈希函数，让相同query进入到同一个小文件中。Ai= hash(query)%200.map<string,,int>可以统计 每个string出现的次数。

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？给出精确算法。

还是刚才那道题目，但现在要求给出精确算法，那么就不能使用布隆过滤器了，此时需要用到哈希切分。

• 首先需要估算一下这里一个文件的大小，便于确定将一个文件切分为多少个小文件。
• 假设平均每个query为20字节，那么100亿个query就是200G，由于我们只有1G内存，这里可以考虑将一个文件切分成400个小文件。
• 这里我们将这两个文件分别叫做A文件和B文件，此时我们将A文件切分成了A0~A399共400个小文件，将B文件切分成了B0~B399共400个小文件。

由于切分A文件和B文件时采用的是同一个哈希函数，因此A文件与B文件中相同的query计算出的 i ii 值都是相同的，最终就会分别进入到Ai和Bi文件中，这也是哈希切分的意义。

那各个小文件之间又应该如何找交集呢？

• 经过切分后理论上每个小文件的平均大小是512M，因此我们可以将其中一个小文件加载到内存，并放到一个set容器中，再遍历另一个小文件当中的query，依次判断每个query是否在set容器中，如果在则是交集，不在则不是交集。
• 当哈希切分并不是平均切分，有可能切出来的小文件中有一些小文件的大小仍然大于1G，此时如果与之对应的另一个小文件可以加载到内存，则可以选择将另一个小文件中的query加载到内存，因为我们只需要将两个小文件中的一个加载到内存中就行了。
• 但如果两个小文件的大小都大于1G，那我们可以考虑将这两个小文件再进行一次切分，将其切成更小的文件，方法与之前切分A文件和B文件的方法类似。

请设计一个类，只能创建一个对象（单例模式）

单例模式有两种实现方式，分别是饿汉模式和懒汉模式：

饿汉模式

单例模式的饿汉实现方式如下：

1. 将构造函数设置为私有，并将拷贝构造函数和赋值运算符重载函数设置为私有或删除，防止外部创建或拷贝对象。
2. 提供一个指向单例对象的static指针（可以为对象，但是单例模式一般返回指针对象），并在程序入口之前完成单例对象的初始化。
3. 提供一个全局访问点获取单例对象。

class Singleton
{
public://3、提供一个全局访问点获取单例对象static Singleton* GetInstance(){return _inst;}
private://1、将构造函数设置为私有，并防拷贝Singleton(){}Singleton(const Singleton&) = delete;Singleton& operator=(const Singleton&) = delete;//2、提供一个指向单例对象的static指针static Singleton* _inst;
};//在程序入口之前完成单例对象的初始化
Singleton* Singleton::_inst = new Singleton;

懒汉模式

单例模式的懒汉实现方式如下：

1. 将构造函数设置为私有，并将拷贝构造函数和赋值运算符重载函数设置为私有或删除，防止外部创建或拷贝对象。
2. 提供一个指向单例对象的static指针，并在程序入口之前先将其初始化为空。
3. 提供一个全局访问点获取单例对象。

class Singleton
{
public://3、提供一个全局访问点获取单例对象static Singleton* GetInstance(){//双检查if (_inst == nullptr){_mtx.lock();if (_inst == nullptr){_inst = new Singleton;}_mtx.unlock();}return _inst;}
private://1、将构造函数设置为私有，并防拷贝Singleton(){}Singleton(const Singleton&) = delete;Singleton& operator=(const Singleton&) = delete;//2、提供一个指向单例对象的static指针static Singleton* _inst;static mutex _mtx; //互斥锁
};//在程序入口之前先将static指针初始化为空
Singleton* Singleton::_inst = nullptr;
mutex Singleton::_mtx; //初始化互斥锁

懒汉模式还有一种比较经典的实现方式：

1. 将构造函数设置为私有，并将拷贝构造函数和赋值运算符重载函数设置为私有或删除，防止外部创建或拷贝对象。
2. 提供一个全局访问点获取单例对象。

class Singleton
{
public://2、提供一个全局访问点获取单例对象static Singleton* GetInstance(){static Singleton inst;return &inst;}
private://1、将构造函数设置为私有，并防拷贝Singleton(){}Singleton(const Singleton&) = delete;Singleton& operator=(const Singleton&) = delete;
};