STL 标准模板库

一些常用数据结构和算法的模板的集合。
1.容器(Container)：是一种数据结构， 如list, vector, 和deques，以模板类的方法提供。
2.算法（Algorithm）：是用来操作容器中的数据的模板函数。
3.迭代器（Iterator）：提供了访问容器中对象的方法。
4.仿函数（Function object）：仿函数又称之为函数对象， 其实就是重载了操作符的struct。
5.适配器（Adaptor）：简单来说就是一种接口类，专门用来修改现有类的接口，提供一种新的接口。或调用现有的函数来实现所需要的功能。
6.空间配制器（Allocator）：为STL提供空间配置的系统。其中主要工作包括两部分：对象的创建与销毁；内存的获取与释放。

常见容器及原理

1.顺序容器
容器并非排序的，元素的插入位置同元素的值无关。
（1）​ vector：动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
（2）deque：双端队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。
（3）list：双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
2.关联式容器
​元素是排序的；通常以平衡二叉树的方式实现。
（1）set/multiset 头文件
​ set 即集合。红黑树。set中不允许相同元素，multiset中允许存在相同元素。
（2）map/multimap 头文件
map 的所有元素都是 pair，pair的第一元素被视为键值，第二元素被视为实值。根据key值对元素从小到大排序，并可快速地根据first来检索元素。
​map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。
3.容器适配器
封装了一些基本的容器，使之具备了新的函数功能
（1）stack 头文件
栈。后进先出。
（2）queue 头文件
​ 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。
（3）priority_queue 头文件
​ 优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部。最高优先级元素总是第一个出列。

空间配置器

空间配置器是用来实现内存空间分配的工具，它与容器联系紧密，每一种容器的空间分配都是通过空间分配器alloctor实现的。

迭代器什么时候会失效？怎么删除元素？

常用容器迭代器失效情形如下（怎么删除元素）：
1.对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。
2.对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。
3.对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。

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

迭代器的作用
1.用于指向顺序容器和关联容器中的元素
2.通过迭代器可以读取它指向的元素
3.通过非const迭代器还可以修改其指向的元素

​迭代器不是指针，是类模板。它封装了指针，是一个可遍历STL容器内元素的对象，可以根据不同类型的数据结构来实现不同的操作。它只是模拟了指针的一些功能，重载了指针的一些操作符。
迭代器产生的原因：Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。
stack、queue、priority_queue不支持迭代器

resize 和 reserve 的区别

1.resize既修改capacity大小，也修改size大小；reserve只修改capacity大小，不修改size大小。
2.两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留的大小。

map 和 unordered_map 的区别？底层实现

map：红黑树
unordered_map：哈希表，查找复杂度O（1）

vector 和 list 的区别，分别适用于什么场景？

vector：一维数组
list：双向链表

hashtable 扩容和如何解决冲突

（1）为什么要扩容
​ 使用链地址法封装哈希表时, 填装因子(loaderFactor)会大于1，理论上这种封装的哈希表是可以无限插入数据的，但是随着数据量的增多，哈希表中的每个元素会变得越来越长， 这时效率会大大降低。 因此，需要通过扩容来提高效率。
（2）如何扩容
​Hashtable每次扩容，容量都为原来的2倍加1，而HashMap为原来的2倍。此时，需要将所有数据项都进行修改(需要重新调用哈希函数，来获取新的位置)。 哈希表扩容是一个比较耗时的过程，但是一劳永逸。
（3）什么情况下扩容
​ 常见的情况是在填装因子(loaderFactor) > 0.75时进行扩容。

如何解决哈希冲突

解决哈希冲突通常有开放地址法和链地址法两种方法，分别如下：
1.开放定址法：即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法。
2.链地址法：采用数组和链表相结合的办法，将Hash地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。

push_back 和 emplace_back 的区别

push_back()需要先构造临时对象，再将这个对象拷贝到容器的末尾，而emplace_back()则直接在容器的末尾构造对象，这样就省去了拷贝的过程。

auto和decltype的区别

auto：用于定义变量，编译器自动判断类型
decltype：用于定义变量，编译器根据表达式自动判断类型

智能指针

动态内存管理容易造成的问题：1.忘记释放内存，会造成内存泄漏；2.尚有指针引用内存的情况下就释放了它，产生引用非法内存的指针
为了更安全地使用动态内存，引入了智能指针。智能指针的行为类似常规指针，重要的区别是它负责自动释放所指向的对象，当超出了类的作用域时，类会自动调用析构函数，析构函数会自动释放资源。所以，智能指针的作用原理就是在函数结束时自动释放内存空间，避免了手动释放内存空间。
四种智能指针：auto_ptr（C++11摒弃）, shared_ptr, weak_ptr, unique_ptr
1.auto_ptr：​ 采用所有权模式。存在潜在的内存崩溃问题。
2.unique_ptr：实现独占式拥有，保证同一时间内只有一个智能指针可以指向该对象。
3.shared_ptr：实现共享式拥有。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时释放。使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。
4.weak_ptr是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象。进行该对象的内存管理的是那个强引用的 shared_ptr。weak_ptr只是提供了对管理对象的一个访问手段。它的构造和析构不会引起引用记数的增加或减少。weak_ptr是用来解决shared_ptr相互引用时的死锁问题，如果说两个shared_ptr相互引用，那么这两个指针的引用计数永远不可能下降为0，资源永远不会释放。

转换语义（move）

将某个左值强制转化为右值

右值引用

左值可以取地址、位于等号左边；而右值没法取地址，位于等号右边。
引用是变量的别名，由于右值没有地址，没法被修改，所以左值引用无法指向右值。
const左值引用不会修改指向值，因此可以指向右值
右值引用可以对右值进行引用，并修改

类型转换

1.const_cast：将const变量转为非const
2.static_cast：主要用于内置数据类型之间的相互转换，也可以转换自定义类型。用于各种隐式转换，比如非const转const，类向上转换，向下转换
3.dynamic_cast：只能用于含有虚函数的类转换，用于类向上和向下转换。运行时处理的，运行时要进行类型检查。
dynamic_cast通过判断变量运行时类型和要转换的类型是否相同来判断是否能够进行向下转换。dynamic_cast可以做类之间上下转换，转换的时候会进行类型检查，类型相等成功转换，类型不等转换失败。运用RTTI技术，RTTI是”Runtime Type Information”的缩写，意思是运行时类型信息，它提供了运行时确定对象类型的方法。在c++层面主要体现在dynamic_cast和typeid，vs中虚函数表的-1位置存放了指向type_info的指针，对于存在虚函数的类型，dynamic_cast和typeid都会去查询type_info。
4.reinterpret_cast：可以做任何类型的转换，不过不对转换结果保证，容易出问题。