c++-第26节-c++知识梳理-创新互联

目录

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）常见经典问题，例如：

底层实现原理，即红黑树。掌握红黑树的规则、增删查改的效率。

operator[ ]的返回值是什么？答：value的引用。

一个类型要做map和set的K有什么要求？答：要支持比较大小，因为底层是搜索树。

map和set有什么特点？答：查找效率，遍历时按key排序的，可以对key去重。

（3）multi版本特点。

unoredered_map和unoredered_set：

（1）需要熟练掌握这些容器的常见接口使用（增删查改：insert、erase、find、operator[]、iterator）

（2）常见经典问题，例如：

底层实现原理，即哈希表。

一个类型要做unoredered_map和unoredered_set的K有什么要求？答：能取模或者配一个哈希的仿函数支持转成整型取模，支持==比较。

unoredered_map和unoredered_set相比map和set的特点是什么？答：查找平均是O(1)（更快），遍历是无序的。

（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）常见经典问题，例如：

vector和list的区别？答：vector优点是适合尾插尾删和下标的随机访问，vector缺点是头部中间插入删除需要挪动数据效率低，并且扩容也有代价。list优点是任意位置O(1)的插入删除，并且可以按需申请释放，list缺点是不支持随机访问。

vector如何扩容？答：一般是2倍扩容，但不一定非得是2倍，只是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.算法

sort（熟练掌握）

stable_sort（了解）

reverse(熟练掌握)

swap(熟练掌握)：c++98推荐使用容器中的swap，不推荐使用算法库中swap；c++11容器中的swap和算法库中swap效率一样，都可以使用。

max/min(熟练掌握)

find(熟练掌握)

next_permutation/prev_permutation(熟练掌握)：全排列

binary_search(了解)

lower_bound/upper_bound(了解)：找上/下界

set_union/set_intersection/set_difference(了解)：求两个集合的并集/交集/差集

解释：

（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元起，快前往官网查看详情吧