189 8069 5689
目录
1.STL知识梳理
2.c++知识梳理
3.数据结构知识梳理
STL知识掌握：
底层实现角度：六大组件。
上层用的角度：容器、算法、迭代器。
底层实现角度：
注：
1.可以认为迭代器是容器和算法的粘合剂，如果没有迭代器，那么算法要访问容器有两大问题：
（1）访问需要暴露容器底层结构及实现细节，封装性就不在了。
（2）使用门槛较高，比如要访问map，需要对二叉树遍历掌握，这个成本是很高的。
通过迭代器解决了上面的问题，迭代器优势如下：
（1）封装隐藏了底层实现细节。
（2）提供统一的方式去访问容器，极大降低了使用成本。
2.容器如果频繁的申请小块内存，就需要空间配置器来提高内存申请和释放的效率。
3.容器适配器：stack、queue、priority_queue等。适配器可以认为是一种特殊的容器，体现了复用的思想。
其他适配器：反向迭代器也是一种适配器，封装容器正向迭代器就可以实现这个容器的反向迭代器。
4.仿函数主要作用在容器和算法上，其本质上是实现了operator()的类，这个类对象可以像函数一样去使用。使用场景举例：
场景一：map/set的key比较大小规则。
场景二：unoredered_map/unoredered_set的key转换成整型的规则，影响冲突率。
场景三：sort排序比较规则。
上层用的角度：
注：
1.容器
重点熟练掌握的容器：vector、list、map、set、unoredered_map、unoredered_set。
map和set：
（1）需要熟练掌握这些容器的常见接口使用（增删查改：insert、erase、find、operator[]、iterator）
（2）常见经典问题，例如：
底层实现原理，即红黑树。掌握红黑树的规则、增删查改的效率。
（3）multi版本特点。
unoredered_map和unoredered_set：
（1）需要熟练掌握这些容器的常见接口使用（增删查改：insert、erase、find、operator[]、iterator）
（2）常见经典问题，例如：
（3）multi版本特点。
vector和list：
（1）需要熟练掌握这些容器的常见接口使用。
vector：push_back/pop_back、resize/reserve（注意二者区别）、insert/erase、[]+size()、iterator
list：push_back/pop_back、push_front/pop_front、insert/erase、iterator
（2）常见经典问题，例如：
其他容器：
（1）需要熟练使用，了解原理的容器。
string：+=、find、insert/erase、[]、迭代器、c_str、sub_str、reserve/resize、to_string/stoi
stack/queue：push/pop、top、front/back、empty/size
priority_queue：push/pop、top、size/empty
bitset：set、reset、test
（2）不需要熟练使用，稍微了解原理。
array(C++11)：核心价值相比c静态数组，[]绝对检查越界。委员会期望替代静态数组，实际效果不明显
forward_list(C++11)：只是头插头删，又想节省一点点空间，比起list有一点点优势
deque：头尾插入删除多，可能还需要一些下标的随机访问。要注意的是不要大量下表随机访问，否则不如用vector好
2.迭代器
（1）什么迭代器(熟练掌握)
答：行为像指针一样的类型。可能是指针可能是被类封装的指针，不关注容器底层细节的情况下轻松访问容器。
（2）迭代器价值是什么？(熟练掌握)
（3）什么是迭代器失效？(熟练掌握)
答：①迭代器指向的空间野指针。 ②迭代器指向的位置已经不是原来的位置，意义变了。
vector：①insert扩容，导致野指针。 ②insert不扩容，但是挪动数据，指向位置已经不是原来的位置。 ③erase数据以后，挪动数据，指向位置已经不是原来位置。
list：erase以后，节点删除，导致野指针。
map/set/unordered_map/unordered_set：erase以后，节点删除，导致野指针。
（4）反向迭代器的原理（了解）
答：适配器，封装正向迭代器实现。
（5）迭代器分类(了解)
答：迭代器被分成了五个类型，如下图所示，前两个类型只写input_iterator_tag和只读output_iterator_tag是抽象类型，STL中没有对应的实际类型。有实际对应类型的是后三个类型迭代器，单向forward_iterator_tag、双向bidirectional_iterator_tag、随机random_access_iterator_tag。
单向（支持++）：forward_list、unordered_map/unordered_set
双向（支持++/--）：map/set、list
随机（支持++/--/+/-）：string、vector、deque
注：如下图所示，算法库中函数的迭代器参数名暗示了要传迭代器的类型，所以使用函数前需确定了容器的迭代器的类型。
需要传单向迭代器的函数可以传单向迭代器、双向迭代器、随机迭代器，需要传双向迭代器的函数可以传双向迭代器、随机迭代器，需要传随机向迭代器的函数只能传随机迭代器。
3.算法
解释：
（1）next_permutation/prev_permutation的使用方式如下图所示，其中next_permutation进行全排列前要求数据是升序的，prev_permutation进行全排列前要求数据是降序的。
（2）lower_bound/upper_bound使用前需要进行排序。lower_bound函数返回数据中第一个大于等于给定数值的位置，upper_bound函数返回数据中第一个大于给定数值的位置。
4.仿函数/函数对象
问题：什么是仿函数？仿函数作用是什么(结合实际用场景讲解)
答：仿函数主要作用在容器和算法上，其本质上是实现了operator()的类，这个类对象可以像函数一样去使用。
5.STL原理
问题：说说你理解STL是什么？整体说一下六大组件是什么？互相之间关联关系？
答：前面底层实现角度的内容。
C++知识掌握：基础入门语法、类和对象、模板、继承和多态、异常、IO流、C++类型转换、C++11、STL、拓展学习。
注：
1.基础入门语法
（1）函数重载：①函数重载的规则要求。 ②为什么C语言不支持重载？C++支持
（2）引用(重点)：①什么是引用？ ②指针和引用区别是什么？ ③引用的使用场景是什么？
（3）inline：①inline价值和意义是什么？ ②宏的缺点？③C++用inline、const、enum去替代宏。
（4）缺省参数
（5）namespace
2.类和对象
（1）面向对象和面向过程的理解。结合实际样例解答。
（2）面向对象三大特性是什么？封装、继承、多态、你对他们理解是什么？结合实际样例解答。
（3）8个默认成员函数：①构造和析构 ②拷贝构造和拷贝赋值 ③移动构造和移动赋值 ④operator&不关注 ⑤什么情况下会默认生成？默认生成的都干了什么？ ⑥构造函数初始化列表（初始化列表价值，哪些成员必须在初始化列表初始化）
（4）对象实例化：①对象大小计算--内存对齐 ②空类的大小？为什么是1？
（5）this指针：①什么是this指针 ②this存在哪？
（6）运算符重载：①哪些运算符不能重载 ②运算符重载意义是什么？
（7）static成员
（8）友元
3.模板
（1）模板分类：函数模板、类模板
（2）模板的原理：模板的实例化
（3）让你写一个函数模板或者类模板检验语法掌握
（4）非类型模板参数
（5）模板的特化：unordered_map默认支持string做key就是特化一个场景
（6）为什么模板不支持分离编译？怎么解决？解决原理是什么？
4.继承和多态
（1）什么是继承？什么是多态？
（2）继承后成员权限
（3）派生中的默认成员函数
（4）子类到父类对象之间赋值兼容转换
（5）多继承--菱形继承：①菱形继承的问题是什么？如何解决？ ②虚继承是如何解决的？（切记不要跟虚函数多态混了，两个地方都用了virtual但是他们之间没有关联关系）
（6）继承和组合：is-a和has-a
（7）多态的条件是什么？原理是什么？
（8）还有一些问题。如：static是否可以是虚函数？inline是否可以是虚函数等等。
5.异常
（1）异常优缺点
（2）异常的使用规则
6.IO流
（1）笔试面试基本不考。从用的角度掌握一下文件流和字符串流，一些项目中可能会用。
7.C++类型转换
（1）四种强制类型转是什么？他们作用是什么
8.C++11
（1）右值引用：①右值引用和左值引用的区别？ ②移动构造和移动赋值 ③右值引用的使用场景？(push_back(T&& val)、传值返回的函数如to_string)如何减少拷贝？提高效率 ④完美转发解决什么问题？
（2）lamdba：①语法规则 ②使用场景和优势 ③底层实现原理
（3）智能指针：①发展历史 ②auto_ptr/unique_ptr/shared_ptr/weak_ptr原理及简单模拟实现 ③什么是循环引用？如何解决？解决原理 ④定制删除器
（4）其他：①线程库 ②列表初始化 ③STL中容器变化（新容器、移动构造和移动赋值、插入接口的变化例如push_back(T&& val)和empalce等） ④可变参数模板 ⑤auto ⑥范围for
9.STL
10.拓展学习
（1）《effctive C++》值得去读一遍
（2）《C++ primer》第五版，推荐手边留一本作为语法字典
（3）《STL源码剖析》有时间可以结合源代码进行学习
（4）设计模式：①单例模式 ②工厂模式 ③适配器模式 ④迭代器模式 ⑤观察者模式
数据结构知识掌握：线性表、树型结构、哈希、排序、图、扩展学习
注：
1.线性表
（1）顺序表
（2）链表
（3）栈和队列
（4）串
2.树型结构
（1）基础二叉树：①二叉树概念及性质 ②常见OJ题，下去手撕一遍 ③堆（topK、堆排序）
（2）搜索树：①二叉搜索树（缺陷） ②AVL树（规则、如何旋转平衡、效率） ③红黑树（规则、如何旋转平衡、效率、对比AVL树的优势是什么？） ④B树系列
3.哈希
（1）什么是哈希/散列
（2）什么是哈希冲突？
（3）哈希表①闭散列开放定址法（线性探测、二次探测） ②哈希桶（单个桶冲突很多怎么办？改成挂红黑树） ③负载因子 ④跟红黑树会有一些对比
（4）位图
（5）布隆过滤器：①在是准确的？还是不在是准确的？不在是准确的 ②是否支持删除
（6）海量数据处理：①位图问题 ②topk问题 ③哈希切分问题
4.排序
（1）常见排序思想及实现：①插入排序 ②希尔排序 ③选择排序 ④堆排序 ⑤冒泡排序 ⑥快速排序（什么时候最坏且如何优化、非递归） ⑦归并排序 ⑧计数排序
（2）复杂度
（3）稳定性
5.图
6.扩展学习
（1）跳表
（2）LRUCahe
（3）并查集
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
