宝典2"/>
面试宝典2
1、请你来说一下map和set有什么区别，分别又是怎么实现的
map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。
map和set区别在于：
- map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。
- set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。
- map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find函数，所有元素都会根据元素的值自动被排序，且不允许重复。
底层实现：红黑树
set 底层是通过红黑树（RB-tree）来实现的，由于红黑树是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的 STL 的 set 即以 RB-Tree 为底层机制。又由于 set 所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 set 操作行为，都只有转调用 RB-tree 的操作行为而已。
2、说一说STL迭代器删除元素
对于容器（vector、deque、list）,删除当前iterator会使后面所有元素的iterator都失效。这是因为vector、deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。使用erase方法后，返回的是下一个有效的iterator。
对于容器（map、set），删除当前的iterator仅仅会使当前的iterator失效。只要在erase时，递增当前的iterator即可。这是因为，map和set采用的是红黑树，删除一个节点不会对其它节点造成影响。
3、请你讲讲STL有什么基本组成
组成：
容器、迭代器、仿函数、算法、分配器、配接器
他们之间的关系：
- 分配器给容器分配存储空间
- 算法通过迭代器获取容器中的内容
- 仿函数可以协助算法完成各种操作
- 配接器用来套接适配仿函数
4、说说STL中map和unordered_map的区别及优缺点
内部实现不同：
map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。
map的优点：
- 有序性。这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
- 红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高
map的缺点：
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
unordered_map的优点：
内部实现的哈希表，因此查找速度非常的快。
unordered_map的缺点：
哈希表的建立比较耗费时间。
内存占有率的问题：
unordered_map占用的内存要高。但是unordered_map执行效率要比map高很多。
5、STL中的vector和list有什么区别，分别在什么场景下应用
vector：顺序表
优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高其时间复杂度O(1)。
缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O（n），另外当空间不足时还需要进行扩容。
list：链表
优点：底层实现是循环双链表，当对大量数据进行插入删除时，其时间复杂度O(1)
缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O（n），没有提供[]操作符的重载。
应用场景：
vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。
6、STL中迭代器的作用，有指针为何还要迭代器
作用：
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。
迭代器和指针的区别：
- 迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，重载了指针的一些操作 符，->、*、++、–等。
- 迭代器封装了指针，是一个“可遍历STL（ Standard Template Library）容器内 全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升（lift），提供了比指针更高 级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，–等操作。
7、STL容器中resize和reserve的区别
resize(n)
- 调整容器的长度大小，使其能容纳n个元素。
- 如果n小于容器的当前的size，则删除多出来的元素。
- 否则，添加采用值初始化的元素。
reserve(n)
- 预分配n个元素的存储空间。它不会生成元素，只是确定这个容器允许放入多少对象。
8、说一下c++中类成员的访问权限
public：
被public修饰的成员变量和函数，可以被该类的函数、子类的函数、友元函数访问，也可以由类的对象来访问（即可以用成员运算符来访问）。
proctected：
被proctected修饰的成员变量和函数，可以被该类的函数、子类的函数访问。但是不能被类对象所访问（即不能通过类对象的成员运算符来访问）。
private：
被private修饰的成员变量和函数，可以被该类的函数访问。不能被子类的函数访问，也不能被类对象访问。
9、C++类内可以定义引用成员变量吗
可以，但要遵循以下三个规则：
- 不用用默认构造函数初始化，必须提供构造函数来初始化
- 构造函数的形参也必须是引用类型
- 不能在构造函数里初始化，必须在初始化列表中初始化
10、什么是右值引用，跟左值又有什么区别
右值引用是C++11中引入的新特性 , 它实现了转移语义和精确传递。它的主要目的有两个方面：
- 消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率。
- 能够更简洁明确地定义泛型函数。
左值和右值的概念：
左值：能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。
右值：不能对表达式取地址，或匿名对象。一般指表达式结束就不再存在的临时对象。
右值引用和左值引用的区别：
- 左值可以寻址，而右值不可以。
- 左值可以被赋值，右值不可以被赋值，可以用来给左值赋值。
- 左值可变,右值不可变（仅对基础类型适用，用户自定义类型右值引用可以通过成员函数改变）。
11、说一下c++源文件从文本到可执行文件经历的过程
- 预处理（生成.i文件）
- 编译（生成.s文件）
- 汇编（生成.o文件）
- 链接（生成.out或.exe文件）
12、include头文件双引号("")和尖括号(<>)的区别
编译器预处理阶段查找头文件的路径不一样。
双引号：
- 当前头文件目录
- 编译器设置的头文件路径
- 系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径
尖括号：
- 编译器设置的头文件路径
- 系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径
13、内存溢出和内存泄漏的概念
内存溢出：
就是内存越界。例如：递归调用栈。比如说c++标准库有个strcpy，会一直复制内存，直到遇到\0。
内存泄漏：
就是内存申请后，用完没有释放，造成可用内存越来越少。
14、C++11有哪些新特性
- auto自动类型推导
- lambda表达式
- 右值引用 int && iii = 10; (消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率)
- 移动语句 std::move （转移语义可以将资源(堆、系统对象等)从一个对象转移到另一个对象，这样可以减少不必要的临时对象的创建、拷贝及销毁。）
- 智能指针
- std::thread 多线程编程
- nullptr
- for循环语句
- std::array、std::forward_list、std::unordered_map、std::unordered_set
15、 红黑树和AVL树（平衡二叉树）的定义、特点以及两者的区别
定义：
AVL树：平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。
AVL树中所有结点为根的树的左右子树高度之差的绝对值不超过1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
红黑树：红黑树是在AVL树的基础上发展而来的。红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。
红黑树的性质：
- 每个结点非红即黑；
- 根节点是黑的；
- 每个叶节点（叶节点即树尾端NULL指针或NULL结点）都是黑的；
- 如果一个结点是红色的，则它的子节点必须是黑色的；
- 对于任何结点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑结点。
红黑树较AVL树的优点：
AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。
16、map低层为什么要用红黑树实现
AVL是严格平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率降低；红黑树是弱平衡的，算是一种折中，插入最多旋转2次，删除最多旋转3次。
所以红黑树在查找、插入删除的复杂度都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层都是使用的红黑树。
17、请你介绍一下B+树
B+是一种多路搜索树，主要为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，每个节点的可以有多个孩子，并且按照关键字大小有序排列。
18、请你说说红黑树的性质还有左右旋转
红黑树：
红黑树是在AVL树的基础上发展而来的。红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。
性质：
- 每个节点非红即黑
- 根节点是黑的;
- 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次。
红黑树旋转：
旋转：红黑树的旋转是一种能保持二叉搜索树性质的搜索树局部操作。有左旋和右旋两种旋转，通过改变树中某些结点的颜色以及指针结构来保持对红黑树进行插入和删除操作后的红黑性质。
左旋：对某个结点x做左旋操作时，假设其右孩子为y而不是T.nil：以x到y的链为“支轴”进行。使y成为该子树新的根结点，x成为y的左孩子，y的左孩子成为x的右孩子。
右旋：对某个结点x做右旋操作时，假设其左孩子为y而不是T.nil：以x到y的链为“支轴”进行。使y成为该子树新的根结点，x成为y的右孩子，y的右孩子成为x的左孩子。
更多推荐
面试宝典2
发布评论