面试指南：C++之STL知识点

���关系列文章

（）

面试指南：C++之STL知识点

C++内存分配策略

（）

深入理解STL空间分配器(一): new_allocator

深入理解STL空间分配器(二)：mt_allocator

深入理解STL空间分配器(三)：pool_allocator
深入理解STL空间分配器(四)：bitmap_allocator

目录

1.讲讲STL的六大组件

2.vector

2.1.简单说说vector

2.2.vector底层原理

2.3.vector为什么要用加倍扩容而不是每次增加一个固定的扩容容量

2.4.vector扩容的过程

2.5.vector的扩容方式为什么是1.5倍或2倍

2.6.size、resize、reserve、capacity的区别

2.7.vector迭代器失效问题

2.8.对于vector可能导致其迭代器失效的操作有哪些

2.9.push_back和emplace_back的区别

2.10.频繁对vector调用push_back()对性能的影响和原因

3.list

3.1.聊聊STL库中的list

3.2.list的底层原理

3.3.list的常用函数

3.4.vector插入、list插入区别

3.5.vector和list的优缺点

3.6.vector和list中，如果删除末尾的元素，其指针和迭代器如何变化？若删除的是中间的元素呢？

3.7.总结一下vector和list具体是怎么实现的呢？常见操作的时间复杂度是多少？

4.deque

4.1.简单说说deque

4.2.详细讲讲deque实现原理

4.3.你了解deque的中控器吗

4.4.deque的迭代器是怎么回事呢

4.5.说一说deque的数据结构

4.6.deque常用的函数

4.7.vector、list、deque的选择原则

5.说说STL迭代器是怎么删除元素的

6.了解优先级队列吗？细节讲讲

7.你知道STL容器动态链接可能产生的问题吗

8.map、unordered_map和set

8.1.你了解map和unordered_map嘛？底层实现呢

8.2.map和unordered_map的优缺点

8.3.set的底层实现为什么不用哈希表而是用红黑树

8.4.为什么map和set和插入删除效率比其他序列容器高，而且每次insert之后，以前保存的iterator不会失效

8.5.为什么map和set不能像vector一样有个reserve函数来预分配数据

8.6.你知道map和set有什么区别嘛？分别是怎么实现的呢

8.7.vector越界访问下标，map越界访问下标，vector删除元素时会不会释放空间

8.8.map中[ ]与find的区别

8.9.hash_map与map的区别？什么时候用hash_map，什么时候用map

8.10.讲一讲set的用法和它的特点

9.你了解STL的内存优化吗

---

1.讲讲STL的六大组件

1. 容器（Containers）：各种数据结构，如Vector,List,Deque,Set,Map,用来存放数据，STL容器是一种Class Template,就体积而言，这一部分很像冰山载海面的比率。
2. 算法（Algorithms）：各种常用算法如Sort,Search,Copy,Erase,从实现的角度来看，STL算法是一种Function Templates。
3. 迭代器（Iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有五种类型，以及其它衍生变化，从实现的角度来看，迭代器是一种将：Operators*,Operator->,Operator++,Operator--等相关操作予以重载的Class Template。所有STL容器都附带有自己专属的迭代器——是的，只有容器设计者才知道如何遍历自己的元素，原生指针（Native pointer）也是一种迭代器。
4. 仿函数（Functors）：行为类似函数，可作为算法的某种策略（Policy）,从实现的角度来看，仿函数是一种重载了Operator()的Class 或 Class Template。一般函数指针可视为狭义的仿函数。
5. 适配器（配接器）（Adapters）：一种用来修饰容器（Containers）或仿函数（Functors）或迭代器（Iterators）接口的东西，例如：STL提供的Queue和Stack，虽然看似容器，其实只能算是一种容器配接器，因为 它们的底部完全借助Deque，所有操作有底层的Deque供应。改变Functor接口者，称为Function Adapter;改变Container接口者，称为Container Adapter;改变Iterator接口者，称为Iterator Adapter。配接器的实现技术很难一言蔽之，必须逐一分析。
6. 分配器（Allocators）：负责空间配置与管理，从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的Class Template。

2.vector

2.1.简单说说vector

动态开辟的二维数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。

2.2.vector底层原理

• 数据安排及操作方式与array非常相似。两者的唯一差别在于空间运用的灵活性。
• 静态空间，一旦配置好了就不能改变了，如果程序需要一个更大的array，只能自己再申请一个更大的array，然后将以前的array中的内容全部拷贝到新的array中。
• 动态开辟的空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。vector的关键技术在于对大小的控制以及重新分配时的数据移动效率。
• 采用的数据结构是线性的连续空间（泛型的动态类型顺序表），他以两个迭代器start和finish分别指向配置得来的连续空间中目前已将被使用的空间。迭代器end_of_storage指向整个连续的尾部。
• 在增加元素时，如果超过自身最大的容量，vector则将自身的容量扩充为原来的两倍。扩充空间需要经过的步骤：重新配置空间，元素移动，释放旧的内存空间。一旦vector空间重新配置，则指向原来vector的所有迭代器都失效了，因为vector的地址改变了。

  2.3.vector为什么要用加倍扩容而不是每次增加一个固定的扩容容量

  • vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度，相对于增长指定大小的O(n)时间复杂度更好。
  • 为了防止申请内存的浪费，现在使用较多的有2倍与1.5倍的增长方式，而1.5倍的增长方式可以更好的实现对内存的重复利用。

    2.4.vector扩容的过程

    • 完全弃用现有的内存空间，重新申请更大的内存空间；
    • 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
    • 最后将旧的内存空间释放。

      2.5.vector的扩容方式为什么是1.5倍或2倍

      • 假如说我们是以2倍方式扩容（1，2，4，8，16），则第i次扩容期间所需要的空间总量就是2^i次方，如果第4次扩容时总共需要8个元素大小的空间，但是前3次已经释放的空间加起来的总量，刚好是7，而7小于8，不足以我们第4次扩容时所需要的空间，也就是说，如果恰巧以2倍方式扩容，那么每次扩容时前面释放的空间它都不足以支持本次的扩容！！！那么如果是以更高倍数的方式进行扩容，则这个空间它的浪费情况就会更高！！！也就是说，以2倍或者更高倍数的方式进行扩容，会存在2个问题：
        • 空间浪费可能比较大
        • 无法使用前面已经释放的空间
      • STL标准没有严格说明我们应该按照哪一种方式进行扩容，因此不同STL的实现厂商都是按照自己的方式进行扩容的。
      • 一般情况下，在Windows的VS系列编译器下，是按照1.5倍的方式进行扩容，在Linux的g++中，是按照2倍的方式进行扩容的。

        2.6.size、resize、reserve、capacity的区别

        • size表示当前vector中有多少个元素（即finish – start）；当前容器所存储的个数，
        • resize可以改变有效空间的大小，也有改变默认值的功能。capacity的大小也会随着改变。可以有多个参数。创建指定数量的元素并指定vector的存储空间。既分配空间又创建对象。
        • reserve是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化push_back），从而达到提高效率的目的，其次还可以减少多次要拷贝数据的问题。reserve它只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n。并且它只有一个参数。指定vector的元素总数，不创建对象。
        • capacity函数表示它已经分配的内存中可以容纳多少元素（即end_of_storage – start）。即容器在分配新的存储空间能存储的元素总数。返回vector中能存储元素的最大数。

          2.7.vector迭代器失效问题

          迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器， 程序可能会崩溃)。

          2.8.对于vector可能导致其迭代器失效的操作有哪些

          • resize、reserve、insert、assign、push_back等会引起其底层空间改变的操作，都有可能使迭代器失效。
          • 指定位置元素的删除操作--erase

            #include using namespace std;#include int main(){    int a[] = { 1, 2, 3, 4 };    vector v(a, a + sizeof(a) / sizeof(int));    // 使用find查找3所在位置的iterator    vector::iterator pos = find(v.begin(), v.end(), 3);    // 删除pos位置的数据，导致pos迭代器失效。    v.erase(pos);    cout