# c++_相关面试笔记整理

**Repository Path**: understand-lijie/c--organize-interview-notes

## Basic Information

- **Project Name**: c++_相关面试笔记整理
- **Description**: 自己准备面试的过程中的一些记录
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 2
- **Created**: 2021-08-27
- **Last Updated**: 2021-08-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

c++整理

#### 1、**STL的基本组成**

- STL主要由：以下几部分组成：
  - **容器**  **迭代器  仿函数**  **算法**  **分配器**  **配接器（适配器）**
- 他们之间的关系：
  - **分配器**给**容器**分配存储空间，**算法**通过**迭代器**获取容器中的内容，**仿函数**可以协助**算法**完成各种操作，**配接器**用来套接适配仿函数

#### 2、RAII是什么
RAII全称是“Resource Acquisition is Initialization”，直译过来是“**资源获取即初始化**”，也就是说**在构造函数中申请分配资源，在析构函数中释放资源**。
因为C++的语言机制保证了，当一个对象创建的时候，自动调用构造函数，当对象超出作用域的时候会自动调用析构函数。所以，在RAII的指导下，我们应该使用类来管理资源，将资源和对象的生命周期绑定。

#### 3、使用智能指针管理内存资源

智能指针（std::shared_ptr和std::unique_ptr）即RAII最具代表的实现，使用智能指针，可以实现自动的内存管理，再也不需要担心忘记delete造成的内存泄漏。
毫不夸张的来讲，有了智能指针，代码中几乎不需要再出现delete了。

##### 对四个智能指针的简单介绍
	shared_ptr, unique_ptr, weak_ptr, auto_ptr
C++里面的四个智能指针： auto_ptr, shared_ptr, weak_ptr, unique_ptr 
其中后三个是c++11支持，并且第一个(auto_ptr)已经被c++11弃用。
为什么要使用智能指针：

智能指针的作用是管理一个指针，因为存在以下这种情况：申请的空间在函数结束时忘记释放，造成内存泄漏。使用智能指针可以很大程度上的避免这个问题，**因为智能指针就是一个类，当超出了类的作用域时，类会自动调用析构函数，析构函数会自动释放资源。**
所以智能指针的作用原理就是**在函数结束时自动释放内存空间，不需要手动释放内存空间**。

**1、unique_ptr（替换auto_ptr）**
unique_ptr实现独占式拥有或严格拥有概念，**保证同一时间内只有一个智能指针可以指向该对象。**它对于避免资源泄露(例如“以new创建对象后因为发生异常而忘记调用delete”)特别有用。
    采用所有权模式：

```c++
unique_ptr<string> p3 (new string ("auto"));   
//#4 unique_ptr<string> p4；                       
//#5 p4 = p3;//此时会报错！！
```

编译器认为 p4=p3 非法，避免了p3不再指向有效数据的问题，即此时p3变成一个悬挂指针。因此，unique_ptr比auto_ptr更安全。
另外unique_ptr还有更聪明的地方：当程序试图将一个 unique_ptr 赋值给另一个时，如果源 unique_ptr 是个临时右值，编译器允许这么做；如果源 unique_ptr 将存在一段时间，编译器将禁止这么做，比如：

```c++
unique_ptr<string> pu1(new string ("hello world"));
unique_ptr<string> pu2; 
pu2 = pu1;        // #1 not allowed，can do it using std::move().                  

unique_ptr<string> pu3;
pu3 = unique_ptr<string>(new string ("You"));    // #2 allowed
```

其中 #1留下悬挂的 unique_ptr(pu1)，这可能导致危害。
而 #2不会留下悬挂的unique_ptr，因为它调用 unique_ptr 的构造函数，该构造函数创建的临时对象在其所有权让给 pu3 后就会被销毁。这种随情况而异的行为表明，unique_ptr 优于允许两种赋值的auto_ptr 。
注：如果确实想执行类似于 #1的操作，要安全的重用这种指针，可给它赋新值。C++有一个标准库函数std::move()，让你能够将一个unique_ptr赋给另一个。例如：

```C++
unique_ptr<string> ps1, ps2;
ps1 = demo("hello");
ps2 = move(ps1);
ps1 = demo("alexia");
cout << *ps2 << *ps1 << endl;
```

**2、shared_ptr**
shared_ptr 实现共享式拥有概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。
shared_ptr使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。除了可以通过new来构造，还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。当我们调用release()时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。

成员函数：
use_count 返回引用计数的个数
unique 返回是否是独占所有权( use_count 为 1)
swap 交换两个 shared_ptr 对象(即交换所拥有的对象)
reset 放弃内部对象的所有权或拥有对象的变更, 会引起原有对象的引用计数的减少
get 返回内部对象(指针), 由于已经重载了()方法, 因此和直接使用对象是一样的.如 shared_ptr
**3、weak_ptr**
weak_ptr 是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象，进行该对象的内存管理的是那个**强引用的 shared_ptr.**  

weak_ptr只是提供了对管理对象的一个访问手段。weak_ptr 设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构**不会引起引用记数的增加或减少**。**weak_ptr是用来解决shared_ptr相互引用时的死锁问题,**如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0，资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用**lock**函数来获得shared_ptr。
```c++
#include <iostream> 
#include <memory>
using namespace std;

class B;
class A {
    public:
    shared_ptr<B> pb_;
    // weak_ptr<B> pb_; 正确的使用就是将其中一个设置为 weak_ptr 指针
    ~A(){     
        cout << "A delete\n";
        }
};
class B{
    public: 
    shared_ptr<A> pa_;
    ~B(){    
        cout << "B delete\n";
        }
};
void fun(){    
    shared_ptr<B> pb(new B());    

    shared_ptr<A> pa(new A());    
    pb->pa_ = pa;    
    pa->pb_ = pb;
    
    cout<<pb.use_count()<<endl;
    cout<<pa.use_count()<<endl;
    
    cout << "delete: by PI" << endl;
    
    // delete(pb.get()); 
    // 若执行这一句，可以让pa的引用数变为1，当函数推出后引用数会变成0，此时会调用析构函数
    // cout<<pb.use_count()<<endl;
    // cout<<pa.use_count()<<endl;
}
 int main(){
     fun();

     return 0;
}
```
可以看到fun函数中pa ，pb之间互相引用，两个资源的引用计数为2，当要跳出函数时，智能指针pa，pb析构时两个资源引用计数会减一，但是两者引用计数还是为1，导致跳出函数时资源没有被释放（A B的析构函数没有被调用）。
如果把其中一个改为weak_ptr就可以了，我们把类A里面的 **shared_ptr pb_**; 改为 **weak_ptr pb_**; 这样的话，资源B的引用开始就只有1，当pb析构时，B的计数变为0，B得到释放，B释放的同时也会使A的计数减1，同时pa析构时使A的计数减1，那么A的计数为0，A得到释放。

我们不能通过weak_ptr直接访问对象的方法，比如B对象中有一个方法 print() ,我们不能这样访问，`pa->pb_->print();` 
因为pb_是一个weak_ptr，应该先把它转化为shared_ptr,如：
`shared_ptr p = pa->pb_.lock(); `
`p->print();`

#### 4、**++i 和 i++ 的区别及实现**

> 前置自增，先自增，后返回原对象的对象；没有产生任何临时对象；
> 而后置自增，先保存原对象，然后自增，最后返回该原临时对象，它需要创建和销毁，效率降低；
> 在不进行赋值的情况下，内置类型前置和后置自增的汇编都是一样的呢！

1. 前置返回一个引用，后置返回一个对象

```c++
// ++i实现代码为：
int& operator++()
{

  *this += 1;
  return *this;

} 
```

2. 前置不会产生临时对象，后置必须产生临时对象，临时对象会导致效率降低

```C++
//i++实现代码为：                 
int operator++(int)                 
{
int temp = *this;                   

   ++*this;                       

   return temp;                  
} 
```
一个简单的例子可以说明两者区别，还能引出左值、右值的问题

```c++
#include <iostream>
using namespace std;
int main()
{
    int a = 0;
    int b = 0;
    int *c = &(a++);  // 第7行
    int *d = &(++b);
    return 0;
}
// 编译后报错
main.cpp:7:19: error: lvalue required as unary ‘&’ operand
     int *c = &(a++);
// 说 & 作用于 左值，也就是说 a++ 的结果并非左值，但 ++b 的结果是 左值
// 左值和右值的简单理解：
// 左值：有名对象，可赋值
// 右值：临时对象，不可被赋值
```

#### **5、C++ STL 的内存优化**

两级配置器结构

STL内存管理使用两级内存配置器。**那为什么需要二级内存配置器呢？**

动态开辟内存时，要在堆上申请，但若是我们需要频繁的在堆开辟释放内存，则就会**在堆上造成很多外部碎片**，浪费了内存空间；

每次都要进行调用**malloc、free**函数等操作，使空间就会增加一些附加信息，降低了空间利用率；

随着外部碎片增多，内存分配器在找不到合适内存情况下需要合并空闲块，浪费了时间，大大降低了效率。

于是就设置了二级空间配置器，**当开辟内存<=128bytes时，即视为开辟小块内存，则调用二级空间配置器。**

关于STL中一级空间配置器和二级空间配置器的选择上，一般默认**选择的为二级空间配置器**。 如果大于128字节再转去一级配置器器。

**1) 第一级配置器**

第一级配置器以 malloc()，free()，realloc()等C函数执行实际的内存配置、释放、重新配置等操作，并且能在内存需求不被满足的时候，调用一个指定的函数。

一级空间配置器分配的是大于128字节的空间，如果分配不成功，调用句柄释放一部分内存，如果还不能分配成功，抛出异常。

这里给出阿秀的图（**拓跋阿秀，一个c++博主有很多不错的文章 推荐**）。

<img src="https://camo.githubusercontent.com/7f45972a6aa04a046e4888fcd950b30f6a476d460375c9e1fbddbd99a9f050ce/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f666f7274686573706164612f6d65646961496d6167653240322e362f3230323130342f632b2b2d3138392d312e706e67" alt="img" style="zoom:80%;" />

**2) 第二级配置器**

在STL的第二级配置器中多了一些机制，避免太多小区块造成的内存碎片，小额区块带来的不仅是内存碎片，配置时还有额外的负担。区块越小，额外负担所占比例就越大。

**3) 分配原则**

如果要分配的区块大于128bytes，则移交给第一级配置器处理。

如果要分配的区块小于128bytes，则以内存池管理（memory pool），又称**次层配置**（sub-allocation）：每次配置一大块内存，并维护对应的16个空闲链表（free-list）。下次若有相同大小的内存需求，则直接从free-list中取。如果有小额区块被释放，则由配置器回收到free-list中。

当用户申请的空间小于128字节时，将字节数扩展到8的倍数，然后在自由链表中查找对应大小的子链表:

如果在自由链表查找不到或者块数不够，则向内存池进行申请，一般一次申请20块，

如果内存池空间足够，则取出内存，

如果不够分配20块，则分配最多的块数给自由链表，并且更新每次申请的块数，

如果一块都无法提供，则把剩余的内存挂到自由链表，然后向系统heap申请空间，如果申请失败，则看看自由链表还有没有可用的块，如果也没有，则最后调用一级空间配置器。

![img](https://camo.githubusercontent.com/0378a3ae19a20d4cfa141e8d9004cf3b4b5ae28589d8bd7af86a37a3db776c68/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f666f7274686573706164612f6d65646961496d6167653240322e362f3230323130342f432b2b2d3138392d322e706e67)

二级内存池

二级内存池采用了16个空闲链表，这里的16个空闲链表分别管理大小为8、16、24……120、128的数据块。这里空闲链表节点的设计十分巧妙，这里用了一个**联合体**既可以表示下一个空闲数据块（存在于空闲链表中）的地址，也可以表示已经被用户使用的数据块（不存在空闲链表中）的地址。

​	1、维护16条链表，分别是0-15号链表，最小8字节，以8字节逐渐递增，最大128字节，你传入一个字节参数，表示你需要多大的内存，会自动帮你校对到第几号链表（如需要13bytes空间，我们会给它分配16bytes大小），在找到第n个链表后查看链表是否为空，如果不为空直接从对应的free_list中拔出，将已经拨出的指针向后移动一位。

​	2、对应的free_list为空，先看其内存池是不是空时，如果内存池不为空： 

​		（1）先检验它剩余空间是否够20个节点大小（即所需内存大小(提升后) * 20），若足够则直接从内存池中拿出20个节点大小空间，将其中一个分配给用户使用，另外19个当作自由链表中的区块挂在相应的free_list下，这样下次再有相同大小的内存需求时，可直接拨出。 		（2）如果不够20个节点大小，则看它是否能满足1个节点大小，如果够的话则直接拿出一个分配给用户，然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。 

​		（3）如果连一个节点内存都不能满足的话，则将内存池中剩余的空间挂在相应的free_list中（找到相应的free_list），然后再给内存池申请内存，转到3。 

​	3、内存池为空，申请内存 此时二级空间配置器会使用malloc()从heap上申请内存，（一次所申请的内存大小为2 * 所需节点内存大小（提升后）* 20 + 一段额外空间），申请40块，一半拿来用，一半放内存池中。 

​	4、malloc没有成功 在第三种情况下，如果malloc()失败了，说明heap上没有足够空间分配给我们了，这时，二级空间配置器会从比所需节点空间大的free_list中一一搜索，从比它所需节点空间大的free_list中拔除一个节点来使用。如果这也没找到，说明比其大的free_list中都没有自由区块了，那就要调用一级适配器了。

- 空间配置函数allocate

  首先先要检查申请空间的大小，如果大于128字节就调用第一级配置器，小于128字节就检查对应的空闲链表，如果该空闲链表中有可用数据块，则直接拿来用（拿取空闲链表中的第一个可用数据块，然后把该空闲链表的地址设置为该数据块指向的下一个地址），如果没有可用数据块，则调用refill重新填充空间。

-  空间释放函数deallocate

  首先先要检查释放数据块的大小，如果大于128字节就调用第一级配置器，小于128字节则根据数据块的大小来判断回收后的空间会被插入到哪个空闲链表。

-  重新填充空闲链表refill

  在用allocate配置空间时，如果空闲链表中没有可用数据块，就会调用refill来重新填充空间，新的空间取自内存池。

  **缺省取20个数据块**，如果内存池空间不足，那么能取多少个节点就取多少个。

 **总结：**

1. 使用allocate向内存池请求size大小的内存空间，如果需要请求的内存大小大于128bytes，直接使用malloc。

2. 如果需要的内存大小小于128bytes，allocate根据size找到最适合的自由链表。
    1. 如果链表不为空，返回第一个node，链表头改为第二个node。
    2. 如果链表为空，使用blockAlloc请求分配node。
       a. 如果内存池中有大于一个node的空间，分配尽可能多的node(但是最多20个)，将一个node返回，其他的node添加到链表中。
       b. 如果内存池只有一个node的空间，直接返回给用户。
       c. 如果连一个node都没有，再次向操作系统请求分配内存。

       ① 分配成功，再次进行b过程。
       ② 分配失败，循环各个自由链表，寻找空间。

       ​	找到空间，再次进行过程b。
        	找不到空间，抛出异常。
3. 用户调用deallocate释放内存空间，如果要求释放的内存空间大于128bytes，直接调用free。
4. 否则按照其大小找到合适的自由链表，并将其插入。

#### 6、vector 与 list 的比较

**STL 中 vector 的实现**

vector 是一个动态数组，底层实现是一段连续的线性内存空间。

扩容的本质：当 vector 实际所占用的内存空间和容量相等时，如果再往其中添加元素需要进行扩容。其步骤如下：

- 首先，申请一块更大的存储空间，一般是增加当前容量的 50% 或者 100%，和编译器有关；
- 然后，将旧内存空间的内容，按照原来的顺序放到新的空间中
- 最后，将旧内存空间的内容释放掉，本质上其存储空间不会释放，只是删除了里面的内容。
- 从 vector 扩容的原理也可以看出：vector 容器释放后，与其**相关的指针、引用以及迭代器会失效**的原因。

vector 使用的注意点及其原因，频繁对 vector 调用 push_back() 对性能的影响和原因

​		主要是在插入元素方面：插入元素需要考虑**元素的移动问题**和**是否需要扩容的问题**

​		频繁的调用 push_back() 也是扩容的问题对性能的影响

**Vector**

- **连续存储**的容器，动态数组，在**堆**上分配空间
- 底层实现：数组
- 两倍容量增长：
  - vector 增加（插入）新元素时，如果未超过当时的容量，则还有剩余空间，那么直接添加到最后（插入指定位置），然后调整迭代器。

- 如果没有剩余空间了，则会重新配置原有元素个数的**两倍空间（不一定是准确的2倍关系，各个版本的值可能存在差异）**，然后将原空间元素通过**复制的**方式初始化新空间，再向新空间增加元素，最后**析构并释放原空间**，**之前的迭代器会失效**。

- 性能：

  - 访问：O(1)

  - 插入：在最后插入（空间够）：很快

  - 在最后插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。

  - 在中间插入（空间够）：**内存拷贝**

  - 在中间插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。

  - 删除：在最后删除：很快 

    ​            在中间删除：**内存拷贝**

- 适用场景：经常随机访问，且不经常对**非尾节点进行插入删除**。

  vector内存由_M_impl中的 **M_start，_M_finish，_M_end_of_storage**三个指针管理，所有关于地址，容量大小等操作都需要用到这三个指针：

![vector的内存图](https://images.gitee.com/uploads/images/2021/0611/110649_3058904f_9012586.png "image-20210611105941788.png")


**List**

- 动态链表，在**堆**上分配空间，每插入一个元素都会分配空间，每删除一个元素都会释放空间。
- 底层：**双向链表**
- 性能：
  - 访问：随机访问性能很差，只能快速访问**头尾节点**。
  - 插入：很快，一般是常数开销
  - 删除：很快，一般是常数开销
- 适用场景：**经常插入删除大量数据**

<img src="http://raw.githubusercontent.com/Light-City/cloudimg/master/list_1.png" alt="img" style="zoom:80%;" />



![list_all](https://raw.githubusercontent.com/Light-City/cloudimg/master/list_a.png)

双向环状链表从节点值为3开始插入，红色框表示最后一个节点(end()指向的节点)。黄色线条表示指向前驱节点，黑色线条表示指向后继节点。

**区别：**

- 1）vector底层实现是数组；list是双向链表。
- 2）vector支持随机访问，list不支持。
- 3）vector是顺序内存，list不是。
- 4）vector在中间节点进行插入删除会导致内存拷贝，list不会。
- 5）vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。
- 6）vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

**应用**

- vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机访问，而不在乎插入和删除的效率，使用vector。
- list拥有一段不连续的内存空间，如果需要**高效的插入和删除**，而不关心随机访问，则应使用list。

##### Vector如何释放空间?

由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。

如果**需要空间动态缩小**，可以考虑使用**deque**。如果vector，可以用swap()来帮助你释放内存。

```C++
vector(Vec).swap(Vec); //将Vec的内存清除； 
vector().swap(Vec); //清空Vec的内存；
```



#### 7、容器内部删除一个元素

​	**顺序容器**（序列式容器，比如**vector、deque**）

​	erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效(list除外)，所以不能使用erase(it++)的方式，但是erase的返回值是**下一个有效迭代器；** It = c.erase(it);

​	**关联容器**(关联式容器，比如**map、set、multimap、multiset**等)

​	erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器； c.erase(it++)



#### 8、STL迭代器如何实现

​	1、 迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器，除此之外，STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。

​	2、 迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器内部必须保存一个**与容器相关联的指针**，然后重载各种运算操作来遍历，其中最重要的是*****运算符与**->**运算符，以及**++**、**--**等可能需要重载的运算符重载。这和C++中的**智能指针很像**，**智能指针也是将一个指针封装**，然后通过引用计数或是其他方法完成自动释放内存的功能。

3、最常用的迭代器的相应型别有五种：value type、difference type、pointer、reference、iterator catagoly;



#### **9、STL中迭代器的作用，有指针为何还要迭代器**

**迭代器的作用**

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

或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

**有指针了为何还要迭代器**

由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。

**迭代器和指针的区别**

- 迭代器不是指针，是**类模板**，表现的像指针。

- 它只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、-- 等。

- 迭代器封装了指针，是一个“可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象， **本质是封装了原生指针**，是指针概念的一种提升（lift），提供了比指针更高级的行为，相当于一种智能指针，可以根据不同类型的数据结构来实现不同的++，-- 等操作。

- 迭代器返回的是**对象引用**而不是对象的值，所以cout只能输出迭代器使用 ***** 取值后的值而不能直接输出其自身。

- 迭代器产生原因

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



#### 10、常见容器性质总结？

- 1.vector 底层数据结构为数组 ，支持快速随机访问
- 2.list 底层数据结构为**双向链表**，支持快速增删
- 3.deque 底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问
- deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
- [堆1] --> [堆2] -->[堆3] --> ...
- 每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来**像是list和vector的结合**.
- 4.stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
- 5.queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）
- 6.priority_queue 的底层数据结构一般为**vector为底层容器**，**堆heap为处理规则**来管理底层容器实现
- 7.set 底层数据结构为红黑树，有序，不重复
- 8.multiset 底层数据结构为红黑树，有序，可重复
- 9.map 底层数据结构为红黑树，有序，不重复
- 10.multimap 底层数据结构为红黑树，有序，可重复
- 11.unordered_set 底层数据结构为hash表，无序，不重复
- 12.unordered_multiset 底层数据结构为hash表，无序，可重复
- 13.unordered_map 底层数据结构为hash表，无序，不重复
- 14.unordered_multimap 底层数据结构为hash表，无序，可重复
- 

#### 11、STL每种容器对应的迭代器

| 容器                                   | 迭代器         |
| -------------------------------------- | -------------- |
| vector、deque                          | 随机访问迭代器 |
| stack、queue、priority_queue           | 无             |
| list、(multi)set/map                   | 双向迭代器     |
| unordered_(multi)set/map、forward_list | 前向迭代器     |

#### 12、哈希表什么时候rehash

C++的hash表中有一个负载因子loadFactor，当loadFactor<=1时，hash表查找的期望复杂度为O(1).
 因此，每次往hash表中添加元素时，我们必须保证是在loadFactor <1的情况下，才能够添加。

因此，当Hash表中loadFactor==1时，Hash就需要进行rehash。rehash过程中，会模仿C++的vector扩容方式，Hash表中每次发现loadFactor ==1时，就开辟一个原来桶数组的两倍空间，称为新桶数组，然后把原来的桶数组中元素全部重新哈希到新的桶数组中。



#### 13、虚函数可以是内联函数吗

**内联函数：在函数前面添加inline关键字，则该函数被称为内联函数。**

内联函数在调用时并不通过函数调用的机制，而是通过将函数体直接插入调用处来实现的，这样可以大大减少由函数调用带来的开销，从而提高程序的运行效率。

需要注意的是：inline声明对编译器来说只是一种建议，编译器可以选择忽略这个建议。比如将一个1000多行的函数指定为inline，编译器就会忽略这个inline，将这个函数还原成普通函数。

因此，并不是说把一个函数定义为inline函数就一定会被编译器识别为内联函数，具体取决于编译器的实现和函数体的大小。



虚函数**可以是内联函数**，内联是可以修饰虚函数的，但是**当虚函数表现多态性的时候不能内联。**
内联是在编译时建议编译器内联，而虚函数的多态性在运行期，编译器无法知道运行期调用哪个代码，因此虚函数表现为多态性时（运行期）不可以内联。
inline virtual 唯一可以内联的时候是：编译器知道所调用的对象是哪个类（如 Base::who()），这只有在编译器具有实际对象**而不是对象的指针或引用时才会发生。**