这是为秋招准备的一篇关于C++八股文的备忘录，记录了一些面试中被问到过或者没问到过，且本人觉得比较值得记的问题，此外还会有很容易被问到的基础算法（比如LRU，路径规划等等），并且会随着秋招进程的推进而更新。内容大多都参考了leetocode里的两本关于C++的leetbook（下血本充了三个月会员才看的）。一些相对常见并且比较基础的问题，比如多态怎么实现啊，堆和栈的区别啊，vector list底层原理等等，就不作记录了。
本篇内容
C++知识
1. 如何用宏来实现比大小函数？（小米面试）
这是我在面试小米的时候遇到的问题，由于这个岗位偏底层，所以面试官问的也是一些比较底层的问题，这道题我一开始答对了后来又改错了……心痛。
想要解决这个问题，首先需要明白宏实现的是简单的代码替换，并不会对正确性进行检查，因此函数里需要加入一些括号来避免歧义，同时也不需要写return之类的东西。所以应该这么写：#define MAX(X, Y) (X) > (Y) ? (X) : (Y)。
需要注意的是，在用宏实现函数的时候，变量外面要加上括号，因为如果X或者Y是表达式的话，可能会产生一些歧义，比如：
#define TEST(X, Y) X - Y
int main()
{
int x = 6, y = -1;
int z = TEST(x+y, x-y);
//如果宏里面没有加括号，那么等式右边替换之后变成这样了: x+y-x-y，算出来结果是0，很明显是不对的
}
那么如何利用宏来实现位运算呢？比如将某个四字节整数的最后四位全都设为0：
#define SET_BIT(X) (X) = (X) & (0xFF<<4)
2. 大端序和小端序（英特尔笔试）
其实就是数据在内存中的存储方式，大端序里，多位数的低位放在高地址，高位放在低地址；小端序就是反过来。英特尔笔试的一道编程题里考到了大端序和小端序的转换，虽然哪怕不知道大端序和小端序的概念也通过测试用例猜出来，我觉得还是稍微了解一下比较好。
3. 浮点数是怎么存储的？
在多个企业的笔试选择题里遇到了这个问题。在C++中，浮点数的存储遵循了IEEE 754标准，可以用value = sign × pow(2,exponent) × fraction的形式进行表示。其中sign就是符号位，而exponent表示指数偏移值，以float为例，这个偏移值占8位，其范围就是 -127~128。而剩下的23位表示的是fraction（尾数），就是1.xxx小数点之后二进制分数。
这么细节的东西都考吗，望天。
4. override关键字 （华为面试）
华子的面试问到了什么是override，我当时脑子一片混沌，只是依稀记得和虚函数继承有关系，然后就回答成了隐藏。。
我觉得弄清楚这三个容易混淆的概念很重要：重写（override），重载（overload）和隐藏（hide）。
其中，重载是针对在同一个可访问区里，具有相同的名字，不同的参数列表（哪怕仅仅是参数顺序不一样也是不同）的函数，调用的时候会根据参数列表来选择合适的函数。重载并不关心返回值，只关心参数列表的不同。而隐藏是指，当派生类中有一个和基类函数同名的函数时，如果这两个函数的返回类型或者参数列表不同，那么基类的函数会被隐藏，如果相同，但是该函数并不是虚函数，那么照样会被隐藏。如果想要在派生类中调用这个基类函数，则需要显式地注明此函数来自于基类，否则会默认调用派生类中的同名函数，这样的话可能会因为参数列表的不同而报错。
而重写是指在派生类中重新实现基类的虚函数，这二者的返回值，名称以及参数列表都相同，只是花括号里的实现内容不一样。
如果派生类中的某个函数声明的时候使用了override，那么该函数必须要重写基类中对应的虚函数，否则会报错。override的好处在于，可以避免想要重写，但是却一不小心在什么地方写错了，导致隐藏了基类函数的情况。与override对立的关键字是final，将它加在基类虚函数的后面，可以禁止该函数被重写。
5. inline的注意事项
关于inline的用法应该是一个高频考点，我在小米和华子的面试中都被问到过inline有关的问题。在这里我想写一些（我认为）不太容易被注意到的点。
假如class是在头文件里定义的，那可以在另一个cpp文件里定义inline函数吗？ 不可以。
inline可以去除函数只能定义一次的限制（可以在头文件里定义，然后头文件被多个其他文件include）。
虚函数不可以inline，因为虚函数是在运行期间确认的，而inline是在编译期间进行代码替换。
此外，并不是你要inline编译器就会听你的，而是会根据函数体的内容来决定是否inline。如果函数包含循环，递归，静态变量，switch或goto语句等，编译器可能不会接受inline的请求。
inline和宏相比，好处在于：inline有宏替换的效率，同时又弥补了宏无法安全检查的缺点，并且去除了函数无法在头文件里定义的限制。
此外，inline也是有一些缺陷的，比如：inline函数太多会导致有很多代码重复，可执行文件太大；内联函数中的变量需要额外的寄存器，会在寄存器资源利用方面产生额外的开销；由于内联函数会导致可执行文件增大，可能会造成内存抖动（也就是操作系统会频繁地将页面调入调出内存）。
6. 如何限制对象只能创建在堆或栈上？
栈一般用于存储局部变量，函数参数，返回地址等等，栈上的对象的构造和析构是由编译器完成，而堆的空间是由用户自行管理的，需要用new关键字来创建对象。
限制对象创建在堆上：那么就需要避免直接调用类的构造函数。我们可以将构造函数和析构函数设为protected（这样派生类仍然可以访问），如果构造函数是private或protected，那么编译器无法调用，就无法再栈上建立对象，如果析构函数是private或protected，编译器发现构造之后没法析构，那么也不会在栈上建立对象。
为了让对象能够建立在堆上，再重新写一个public的静态函数来完成构造，通过调用这个静态函数，可以完成对象在堆中的创建。以下是一个例子：
class A
{
protected:
A() {}
~A() {}
public:
static A *create()
{
return new A();
}
void destroy()
{
delete this;
}
};
限制对象创建在栈上：那么让new不能用就行了，在类的内部重载operator new()，将它设为private即可（同时delete也要重载）。
7. 如何禁止类的拷贝？
一个很简单的想法就是把类的拷贝构造函数和赋值运算符都设为private，但是仅仅这样可不够，因为友元是可以访问这些private成员的。所以在此基础上，我们还需要声明一个派生类私有继承它，这样的话，派生类无法重写拷贝构造函数和赋值运算符，在外部也不可以调用它们。
真是让人头皮发麻的骚操作。
8. 一些关键字
我感觉C++里面有些关键字很难记，因为平时也不怎么用到，光看字面意思也猜不出功能。
explicit： 用来声明类的构造函数是显式调用的，可以避免调用构造函数的时候发生隐式转换。只用于修饰单参构造函数（因为无参和多参本身就是显式的），以下是一个例子。
#include <iostream>
#include <cstring>
using namespace std;
class A
{
public:
int var;
A(int tmp)
{
var = tmp;
}
};
int main()
{
A ex = 10; // 发生了隐式转换
return 0;
}
如果把A的构造函数写成explicit A(int tmp)，此时A ex = 10就会报错了。
define和typedef的区别：
在前面曾经提到过，#define所做的是简单的文字替换，在编译预处理期间进行替换，不做类型检查，可以给常量、类型等定义别名，还可以定义编译开关等等。而typedef是一个关键字，在编译时处理，有类型检查功能，是给某个类型定义一个别名。
#define没有作用域限制，在头文件里用了#define，那么所有include它的cpp文件都可以使用。而typedef是有作用域限制的，如果在函数内部用了typedef，那么只能在函数内部起作用。
此外，在定义指针的时候，由于#define只是做了简单替换，可能会出现一些问题，比如：
#define PTR char*
int main()
{
PTR x, y, z;
//此时等价于char* x, y, z，只有x是char*，y和z都是char。如果用typedef就不会有这个问题。
}
volatile： volatile的作用是阻止编译器进行过度优化，从而可以提供对特殊地址的稳定访问。包括：阻止编译器为了提高速度将一个变量缓存到寄存器内而不写回（缓存一致性协议、轻量级同步），阻止编译器调整操作 volatile 变量的指令排序。要求使用 volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指令刚刚从该处读取过数据，而且读取的数据立刻被保存。
constexpr：告诉编译器应该去验证(函数或变量)在编译期是否就应该是一个常数，这样方便编译器进行优化。
mutable：类中的成员变量加上mutable之后，即使是const函数也可以对其进行修改。
9. 左值和右值
左值是指表达式结束之后仍然存在的对象，而右值是表达式结束后会被销毁的对象。左值可以通过&来取地址，而右值不可以。举一个简单的例子：
int a = 4;
其中a就是左值，而4是右值。函数的返回值既可以是左值，也可以是右值。左值引用的底层是通过指针实现，分为常量左值引用和非常量左值引用两种。常量左值的引用可以绑定到非常量左值，常量左值和右值，而非常量左值的引用只能绑定到非常量左值。如果非常量左值的引用绑定到右值上，可能会出现指向的对象被销毁的情况。比如，下面这种情况是不可以的：
int test(int& a)
{
return 2*a;
}
int main()
{
test(10); //非常量左值引用不可以绑定到右值上
//如果test的参数为const int& a，那么是可以的
return 0;
}
右值引用是C++ 11的新特性，右值引用只可以绑定到右值上，用&&来声明。它实现了转移语义和精确传递，可以消除两个对象交互时不必要的对象拷贝。
左值引用转换为右值引用
使用move()函数可以将左值转换为右值，move函数的步骤如下：
-
根据引用折叠原理传递参数，所谓引用折叠原理就是：
T&& &&相当于T&&，T&& &相当于T&，也就是经过&&传递之后，左值引用依旧是左值引用，右值引用依旧是右值引用。 -
通过
remove_reference移除引用，获得参数的具体类型type。 -
通过
static_cast进行强制类型转换，返回type &&右值引用。
这里提到了强制类型转换，那么强制类型转换有哪些呢，下一条里解释。
10. 强制类型转换
static_cast：是静态转换的意思，会在编译期间进行转换，如果失败抛出编译错误。通常用于：数据类型的强制转换，基本数据类型的转换；基类和派生类之间的指针或引用的转换（不一定要有虚函数），其中派生类转基类是安全的，而基类转派生类不安全，最好用dynamic_cast；将空指针转换为其他类型的空指针，将任意类型的表达值转换为void，但是不可以用于不同类型的指针的转换。
const_cast：主要用于const和非const，volatile和非volatile之间的转换，可以强制去掉指针或引用常量属性：将常量指针转化为非常量指针或者将常量引用转化为非常量引用，但是不可以改变其类型。
reinterpret_cast：改变指针或引用的类型，将指针或引用转换为一个足够长度的整型、将整型转化为指针或引用类型。是通过逐比特复制来实现的。
dynamic_cast：唯一一个在运行期执行的操作，会进行类型检查，只能用于带有虚函数的基类或派生类的指针或者引用对象的转换，如果失败了会返回NULL，不可用于基本类型的转换。在进行向上类型转换（也就是派生类到基类）时，其效果和static_cast一样。
11. sizeof()，strlen，以及各种求大小的问题
我对于这种问题可谓是深恶痛绝……在选择题里经常考，面试的时候也会被问到。我从网上搜罗了各种关于sizeof的问题罗列如下：
char s[] = "abc";
cout<<sizeof(s)<<endl; //输出4
cout<<strlen(s)<<endl; //输出3
sizeof是一个运算符，在编译器计算长度，而strlen是一个库函数，在运行时计算长度，前者测量的是对象或者表达式占用内存的大小，而后者测量的是字符串实际长度。由于字符串结尾处还有一个\0，所以sizeof的结果会比strlen大1。
void size_of(char arr[])
{
cout<<sizeof(arr)<<endl;
cout<<strlen(arr)<<endl;
}
int main()
{
char s[10] = "abc";
cout<<sizeof(s)<<endl; //输出10
size_of(s); //输出8和3
return 0;
}
如果把字符数组作为函数的形参，那么它就会被看成是一个字符指针，因此sizeof返回的是指针的大小，在64位机器中指针大小为8字节（32位是4字节）。而strlen依旧返回字符数组的实际长度。
然后再来看看这个：
int a[100];
cout << sizeof(a) << endl; //返回400
cout << sizeof(a[100]) << endl; //返回4
cout << sizeof(&a) << endl; //返回8
其中，第一条语句求得是整个数组的大小（同理，如果数组作为函数形参的话，那么会被当成指针来处理）。第二条虽然越界了，但是没有报错！因为C++不会对下标越界进行检查，主要是考虑到运行时的效率问题。由于数组是放在一块连续的空间里的，所以如果下标越界了，就会指向连在数组后面的那块内存。我们并不知道那块内存里放了什么东西，可能会返回一个未知的结果。而对于第三条语句，我们可以将变量的引用看成是变量的一个别名，也可以把它当成一个指向该变量的指针，因此这里返回的是指针的大小。
下面这种情况会产生溢出，是会报错的：
int a[100];
a[100] = 0; //这里运行的时候会报错
13. 关于delete[] 和delete （某个独立游戏工作室的笔试题）
首先说一句题外话，new和delete是会调用构造函数和析构函数的，而malloc和free只是分配和释放空间，不会对对象初始化。
我在做笔试的时候遇到这样一个问题，假设int* p = new int [100];，那么delete p和delete[] p的结果有什么区别呢？
答案是没有区别。delete和delete[]的区别在于，delete只会调用一次析构函数，而delete[]会对数组里的每个元素都调用一次析构函数。然而int这种自带的数据类型不需要析构，所以结果没有区别。如果数组中存放的是自定义类型，那么就得用delete[]。
14. 基类指针指向子类对象，调用的到底是谁的函数？
给你一串代码，其中包括函数的继承，并判断基类指针调用的到底是基类还是子类的函数。我回忆了一下，好像我面试过的游戏公司都考了相关的问题。
以下是一个简单的例子：
class A {
public:
void test()
{
cout << "this is class A" << endl;
}
};
class B : public A
{
public:
void test()
{
cout << "this is class B" << endl;
}
};
int main()
{
A* pa = new B();
pa->test(); //输出this is class A
delete pa;
return 0;
}
定义一个A类的指针指向B类对象，并调用test()函数。由于test并不是虚函数，所以pa调用的是A类里的函数。
此外，在代码上添加一些小的变动会造成不同的结果。如果在test前面加上virtual，那么就会调用B类里的相应函数，输出”this is class B”；如果B类私有继承了A，那么A* pa = new B()这一行会报错，因为B无法访问A，没法进行B*到A*的类型转换。
在这里就顺便提一下动态绑定和静态绑定这两个概念。静态绑定就是在编译期间确定对象的类型，而动态绑定是在运行时确定对象的类型。对于类的成员函数而言，虚函数是动态绑定的，非虚函数是静态绑定的。因此，对于A* pa = new B();这条语句而言，如果没有将test声明为虚函数，那么test是静态绑定，使用pa只能调用A类里的test，如果把它声明为虚函数了，那么就变成了动态绑定，导致pa调用的是B里的test。
常考查的算法
1. Dijkstra
dijkstra是一种单源最短路径算法，主要思想是贪心。dijkstra将节点分为两类：已经确定了从起点开始的最短路的节点，已经未确定最短路的节点。每次从未确定节点中取出到起点距离最短的那个，并用其来更新起点到其邻居节点的距离，直到所有节点都被归类为已确定节点。需要注意的是，dijkstra不适用于权重为负数的边。
有几种方法可以实现dijkstra。由于每次更新前，需要从未确定节点中取出到起点距离最短的那个点，我们很容易可以想到用优先队列来解决问题：
//输入：edges：表明两两相连的节点，dists：edges中每条边的权重，n：节点数量，start：起始点
vector<int> dijkstra(vector<vector<int>>& edges, vector<int>& dists, int n, int start)
{
vector<vector<pair<int,int>>> graph(n);
//首先根据edges建图
for (int i = 0; i < edges.size();i++)
{
graph[edges[i][0]].emplace_back(edges[i][1],dists[i]);
graph[edges[i][1]].emplace_back(edges[i][0],dists[i]);
}
//小顶堆
priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
vector<int> min_dists(n, INT_MAX);
min_dists[start] = 0;
q.emplace(0, start);
while (!q.empty())
{
//每次取出距离起始点最短的那个点
auto p = q.top();
int node = p.second, dist = p.first;
q.pop();
for (auto p : graph[node])
{
//距离变小了就更新
if (min_dists[p.first] < min_dists[node] + p.second)
{
min_dists[p.first] = min_dists[node] + p.second;
q.emplace(min_dists[node] + p.second, p.first);
}
}
}
return min_dists;
}
2. A-star 算法
A-star算法是游戏开发中很常用的一种算法，其对dijkstra进行了一些优化。
在dijkstra中，我们每次都从优先队列里取出距离起始点最近的那个点，并进行更新，而Astar算法中还增加了辅助判断的内容：计算该点到终点的曼哈顿距离，这样可以防止跑到一些过于偏远的地方。假设该点到起点的距离为$g(i)$，而到终点的曼哈顿距离为$h(i)$，那么最后用于估算的估价函数就是$g(i)+h(i)$。我们将估价函数连同节点存入优先队列，每次从里面取出估价函数最小的那个结点并向四周扩展，直到优先队列变空位置。
假设给定一个m×n的地图，需要从起始点走到终点，中间存在一些障碍物，则A-star算法的代码如下：
struct Node {
int x, y; //坐标
int G, H, F; //F = G + H
Node* prev = nullptr; //上一个格子
Node():x(-1),y(-1),G(INT_MAX),H(INT_MAX),F(INT_MAX),prev(nullptr){}
Node(int a, int b, int c, int d, int e):x(a),y(b),G(c),H(d),F(e),prev(nullptr){}
Node(int a, int b, int c, int d, int e, Node* n):x(a),y(b),G(c),H(d),F(e),prev(n){}
//用于优先队列比大小
bool operator < (const Node& n) const {
return F > n.F;
}
};
int print_route(Node* n)
{
//打印路径
int cnt = 0;
while (n != nullptr)
{
cout << n->x << " " << n->y << endl;
cnt++;
n = n->prev;
}
return cnt;
}
int Astar(vector<vector<int>>& map, vector<int>& st, vector<int>& ed)
{
//假设可走的地方值为0，障碍物为1.
//2表示将节点加入了openlist，3表示加入closelist
int dirs[4][2] = { 0,1,0,-1,1,0,-1,0 };
int m = map.size();
int n = map[0].size();
priority_queue<Node*> q;
int tmp = abs(ed[0] - st[0]) + abs(ed[1] - st[1]);
Node* head = new Node(st[0], st[1], 0, tmp, 0 + tmp);
q.push(head);
while (!q.empty())
{
auto p = q.top();
q.pop();
int x = p->x;
int y = p->y;
map[x][y] = 3;
if (x == ed[0] && y == ed[1]) //找到终点了
{
int r = print_route(p); //打印路径
return r;
}
for (int i = 0; i < 4; i++)
{
int x1 = x + dirs[i][0];
int y1 = y + dirs[i][1];
if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && map[x1][y1] == 0) //可访问
{
int g = p->G + 1;
int h = abs(ed[0] - x1) + abs(ed[1] - y1);
Node* n = new Node(x1, y1, g, h, g+h, p);
map[x1][y1] = 2;
}
}
}
}
3. topK问题
topK问题是一个很高频的面试问题，需要在一串数组中查找第k大的数字。我们知道快速排序中每次迭代会将数组分割成大于$num[i]$和小于$num[i]$两部分，这样可以确定$num[i]$在排序后数组中的位置。因此，我们可以借助快速排序来找到这第k个数，这个方法被称为“快速选择”。需要注意的是，我们不需要对整个数组进行排序，只需要找到$num[i]$左右两侧中第k个数字所在的那一侧，并迭代地进行查找即可。
int select(vector<int>& nums, int st, int ed, int k)
{
int i = st, j = ed;
int val = nums[i];
while (i < j)
{
while (i < j && nums[j] >= val)
j--;
if (i < j)
nums[i++] = nums[j];
while (i < j && nums[i] <= val)
i++;
if (i < j)
nums[j--] = nums[i];
}
nums[i] = val;
if (i == k)
return nums[i];
else if (i < k)
return select(nums, i + 1, ed, k);
else
return select(nums, st, i - 1, k);
}
int topK(vector<int>& nums, int k)
{
int n = nums.size();
return select(nums, 0, n - 1, k);
}
那么如果要在一个庞大的数据集里寻找topk呢？比如在10亿个数据里寻找最大的100个数，此时再使用快排耗时就会非常大。这个时候我们就要考虑牺牲一些内存来减小时间复杂度。我们可以选取前100个数建立一个最小堆（完全二叉树，所有父节点的值小于或等于两个子节点的值），然后将剩下的数与根节点比对：如果该数大于根节点，那么就把该数加入最小堆，把根节点删了，然后调整结构生成一个新的最小堆。
建立一个最小堆所需的时间复杂度是klogk，乘以遍历次数，最终得到的时间复杂度是nklogk。由于k远小于n，所以该种方法比采用快排（时间复杂度nlogn）要快得多。
4. 实现LRU缓存
LRU就是最近最少使用（least recently used）的意思，是操作系统中页面置换的一种算法，每次进行页面置换时，优先换出最近最少使用的页面。页面有key和value两个属性，要求可以根据key来修改value。LRU可以通过双向链表+哈希表来实现，其中双向链表用于存放页面，每次使用过一个页面之后，就将其放到链表的最顶端，而每次页面超过缓存，就把链表最尾部的页面置换出来，而哈希表用于根据key来获取页面。以下是LRU的代码：
//双向链表
struct DLinkedNode
{
int key, val;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode():key(0),val(0),prev(nullptr),next(nullptr){}
DLinkedNode(int k, int v):key(k),val(v),prev(nullptr),next(nullptr){}
DLinkedNode(int k, int v, DLinkedNode* p, DLinkedNode* n):key(k),val(v),prev(p),next(n){}
};
class LRU {
private:
unordered_map<int, DLinkedNode*> cache; //缓存
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity; //超过capacity就要进行页面置换
public:
LRU(int capacity)
{
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
tail = nullptr;
size = 0;
this->capacity = capacity;
}
void move_to_head(DLinkedNode* node) //将某个节点移到头部
{
remove_node(node);
add_to_head(node);
}
void remove_node(DLinkedNode* node) //移除节点
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void add_to_head(DLinkedNode* node) //在头部加入节点
{
node->next = head->next;
node->prev = head;
}
int get(int key) //调用页面
{
if (!cache.count(key))
return -1;
//将其移到头部
auto node = cache[key];
move_to_head(node);
return node->val;
}
int put(int key, int val) //存入新的页面
{
if (!cache.count(key))
{
DLinkedNode* node = new DLinkedNode(key, val);
add_to_head(node);
cache[key] = node;
size++;
if (size > capacity) //需要置换
{
auto lastnode = tail->prev;
remove_node(lastnode);
cache.erase(lastnode->key);
delete lastnode;
size--;
}
}
else
{
auto node = cache[key];
node->val = val;
move_to_head(node);
}
}
};
虽然我没在面试的时候被问到过，但是手写LRU是一道面试高频题，如何操作双向链表是关键。
5. 实现哈希映射
哈希表是面试中经常会被问到的一个知识点。首先先明确一下哈希的概念。哈希算法将复杂的输入信息映射到整数值域里，而哈希表由哈希算法以及数组或链表等数据结构实现，根据映射得到的整数值，我们可以在哈希表里进行高效的查找。在哈希算法中，相同的输入得到的整数一定是相同的，而不同的输入有可能会得到相同的整数，此时就会产生哈希冲突。面试官经常会问哈希冲突有什么解决方法（有开放地址，再哈希，链地址，建立公共溢出区，具体的就不阐述了）。
所谓哈希映射就是将键和值对应起来，而键是根据哈希函数计算出来的。假设键不存在重复的情况下，哈希映射主要需要实现三个功能：插入insert(key,value)，查找find(key)以及删除remove(key)。
以下是哈希映射的简单实现（LC706）：
class MyHashMap {
public:
MyHashMap() {
data.resize(maxlen);
}
void put(int key, int value) {
int h = hash(key);
for(auto it = data[h].begin(); it != data[h].end(); it++)
{
if(it->first == key)
{
it->second = value;
return;
}
}
data[h].push_back(make_pair(key,value));
}
int get(int key) {
int h = hash(key);
for(auto it = data[h].begin(); it < data[h].end(); it++)
{
if(it->first == key)
return it->second;
}
return -1;
}
void remove(int key) {
int h = hash(key);
for(auto it = data[h].begin(); it != data[h].end(); it++)
{
if(it->first == key)
{
data[h].erase(it);
return;
}
}
}
private:
vector<vector<pair<int,int>>> data;
int maxlen = 769; //选一个素数
int hash(int key)
{
return key%maxlen;
}
};