C++之STL的面试题

1.unordered_map、unordered_set 底层原理

（1）底层原理

     unordered_map内部实现了一个哈希表,也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用。因此，其元素<key,value>的排列顺序是无序的。
unordered_set底层也是哈希表，只是存储的是value，而不是<key,value>

      c++中对unordered_set描述大体如下：无序集合容器（unordered_set）是一个存储唯一(unique，即无重复）的关联容器（Associative container），容器中的元素无特别的秩序关系，该容器允许基于值的快速元素检索，同时也支持正向迭代。
在一个unordered_set内部，元素不会按任何顺序排序，而是通过元素值的hash值将元素分组放置到各个槽(Bucker，也可以译为“桶”），这样就能通过元素值快速访问各个对应的元素（均摊耗时为O（1））。

就是说我们只需要通过某个函数将关键字和其存储位置相对应起来即可：

存储位置 = f(关键字)

我们通过查找关键字不需要比较就可以获得需要记录的存储位置，这是一种新的存储技术----散列存储技术（将记录存储到其关键字对应的f(key)内存位置）

这种对应关系f称为哈希函数（Hash）,然后以这种散列存储方式将记录存储到一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表（Hash Table)。

 2.map,set和unordered_map,unordered_set的区别和使用场景

（1）map和unordered_map的区别

头文件加载

map: #include < map >

unordered_map: #include < unordered_map >

实现机理

      map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
       unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。

优缺点以及适用处

map：

1. 优点：

   1.1 有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
   1.2 红黑树，内部实现一个红黑树使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高

2. 缺点：

   空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

3. 适用处：
   对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

1、优点： 因为内部实现了哈希表，因此其查找速度非常的快
2、缺点： 哈希表的建立比较耗费时间，可能存在哈希冲突
3、适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map
总结：

1. 内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。

2. 但是unordered_map执行效率要比map高很多

3. 对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的

（2）set，unordered_set的区别

1.set，

    所有元素都会根据元素的值自动被排序，且不允许重复。

    底层实现：红黑树

    set 底层是通过红黑树（RB-tree）来实现的，由于红黑树是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的 STL 的 set 即以 RB-Tree 为底层机制。又由于 set 所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 set 操作行为，都只有转调用 RB-tree 的操作行为而已。

    适用场景：有序不重复集合

2.unordered

    unordered_set 容器，可直译为“无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
总的来说，unordered_set 容器具有以下几个特性：

1. 不再以键值对的形式存储数据，而是直接存储数据的值；

2. 容器内部存储的各个元素的值都互不相等，且不能被修改。

3. 不会对内部存储的数据进行排序

3 STL 中迭代器的作用，有指针为何还要迭代器

1） Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

2） 迭代器不是指针，是类模板，表现得像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、--等，相当于一种智能指针。

3） 迭代器产生原因：

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

4 STL 迭代器是怎么删除元素的呢

1） 对于序列容器vector,deque来说，使用erase(itertor)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器；

2） 对于关联容器map set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

3） 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，

5平衡二叉树（AVL树）和红黑树

1）平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。

2）红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑），红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。

3）所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。

6 栈溢出的原因

栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数。

1） 局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出，局部变量是存储在栈中的。

2） 递归调用层次太多。

3） 指针或数组越界。例如进行字符串拷贝，或处理用户输入等等。

7 堆和栈的区别

C语言的内存模型分为5个区：栈区、堆区、静态区、常量区、代码区。

1） 栈区：存放函数的参数值、局部变量等，由编译器自动分配和释放。栈由系统自动分配，速度快，但是程序员无法控制。

2） 堆区：就是通过new、malloc、realloc分配的内存块，编译器不会负责它们的释放工作。一般是由程序员分配释放，未被释放可能引起内存泄漏。堆是有程序员自己分配，速度较慢，容易产生碎片，不过用起来方便。

3） 全局变量和静态变量的存储是放在一块的。

4） 常量区：常量存储在这里，不允许修改。

5） 代码区：存放函数体的二进制代码。

8 哈希表（hash表）

哈希表的实现主要包括构造哈希和处理哈希冲突：构造哈希，主要包括直接地址法，除留余数法。

处理哈希冲突：当哈希表关键字集合很大时，关键字值不同的元素可能会映射到哈希表的同一地址上，这样的现象称为哈希冲突。常用的解决方法有：

1） 开放定址法，冲突时，用某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。（如，线性探测，平方探测）

2） 再哈希法：当发生冲突时，用另一个哈希函数计算地址值，直到冲突不再发生。

3） 链地址法：将所有哈希值相同的key通过链表存储，key按顺序插入链表中。

部分引用于：C++面试之STL - Lucky& - 博客园 (cnblogs.com)