C++STL的vector源码分析、内存管理及问答

标准模板库由三个部分组成：容器、迭代器、算法

Q：容器分为哪几种？

A：顺序容器、关联容器、容器适配器

Q：简要阐述一下你理解的vector容器

A：它相当于一个会自动增长的数组。与数组比较起来，它花费更多的内存去有效的管理存储和动态增长。

在问其他问题之前，我们先来理解一下vector的push_back源码

vector的push_back源码

1.首先先判断该值的地址是否位于vector当前已有数据的地址范围内

2.如果存在，计算出它与首地址的偏移量，使用这个值来初始化数据

3.如果不存在，那么先查看当前容量是否已满

4.如果没有可用空间了，重新申请内存（reserve）

5.如果有可用空间，就使用construct来初始化数据

6.最后，尾指针向后移动

7.析构函数释放原有的vector内存

下面我们来看一下是如何重新申请内存的

1.如果当前可使用的容量小于要插入的数量（1），那么就需要重新申请内存

2.如果最大容量减去当前容量小于1，那么抛出vector过长异常

3.申请内存之前，容量需要按照增长50%或为插入的数量（1，这是在当前容量等于0的情况下）

4.申请新内存，将原始空间析构函数释放，重新计算头尾指针的偏移量

Q：分析一下push_back与c11的emplace_back

A:push_back(A("cc")) 此时它创建一个临时局部A类对象。而emplace_back("cc")可以在内存中直接创建对象而不需要传入对象。

  总的来说，再插入值的时候，push_back会拷贝元素，emplace_back会构造元素。但是当插入的是对象的时候，emplace_back的形参里的参数应该与对象的构造函数相对应

Q：vector的erase函数是如何实现的？

A：因为vector是以array为底层实现，那么vector也是一段连续的代码块，所以当我们按照某个位置擦除掉某个元素/某几个元素时，容器会重新迁移剩余的元素，使它们依旧紧凑在一起。其中使用了copy算法（传入要删除的元素串的尾部、vector的尾部：注意这不是容量的尾部是大小的尾部、传入要删除的元素串的尾部），这样就会把元素串的尾部到vector的尾部的元素串复制到地址从元素串的首部开始。

vector的resize函数（size）和reserve函数（capacity）

c++文档中reserve函数有一个简短的定义“Request a change in capacity”，这可以看出reserve函数主要是在容量上进行增加。

前面已经解释过了reserve的源码，现在来看一看resize的源码

1.如果传入的新的大小大于旧的大小，那么在旧的大小的尾部插入长度为它们之间差值的元素串。

2.如果小于旧的大小，那么把旧的大小大于新大小的那一部分的元素删去

所以resize是改变size大小（有可能改变capacity的大小，当需要扩容的时候），而reserve是改变capacity大小。

那么它们哪个性能更优呢？

因为resize可能会改变capacity的大小，那么这个时候它就需要扩容，扩容的关键就是新建一个vector对象，再将原本的数据拷贝进入该对象中，再把要插入的值写入。因为新创建了对象所以它的性能会比较低下。reserve表示容器预留空间，在改变capacity大小时，因为没有给该内存进行初始化，所以不会去新建对象，所以它不能引用容器内的元素，如果需要引用就需要使用push_back和insert。

如果还不理解它们之间的关系，这里有一个小例子：

            正在建造的一辆公交车，车里面可以设置40个座椅（reserve(40);），这是它的容量，但并不是说它里面就有了40个座椅，只能说明这部车内部空间大小可以放得下40张座椅而已。而车里面安装了40个座椅(resize(40);)，这个时候车里面才真正有了40个座椅，这些座椅就可以使用了

总的来说，reserve（预留空间、改变内存、不建对象）

    resize（改变size、可能改变内存、新建对象）

Q：vector的大小（vector::size）与它的容量（vector::capacity）是一样的吗？

A：不一样。当vector有特定容量且vector数据已经存满的时候，它们的大小和容量是相同的。但是如果此时再插入一个数据，容量会按照一定的增长方式增加，此时大小就会小于容量。

Q：详细描述一下vector的内存管理

A：为了避免每一次插入都要扩容，vector在初始化时会让容量大于预装入的数据长。

      当插入数据的时候，如果此时容量已满，那么就实现扩容（扩容并不是在原vector的基础上，而是新建一个大小是旧容量的150%的新vector，然后再将旧vector的值拷贝到新vector，再将插入的值拷贝进vector。然后调用析构函数释放旧vector的内存）。

Q：erase后的vector，它的容量依旧是不变的，只是存储的数据变少了，所以如果存在容量100000的vector，释放了99999的数据，那么此时它的容量依旧一样，而有效size只剩1。那么如何强制释放vector的缓冲区？

A：方法1：std::vector<int>().swap(arr)  arr是待释放的vector

      解释：首先vector()使用默认构造函数建立了一个临时的vector对象，当这个临时对象调用swap时，arr的大小变为默认构造对象的大小，而临时对象的大小为arr的大小，因为临时对象很快就会通过析构函数被释放掉，所以占用的空间就被释放了。

    方法2：<vector> int temp; arr.swap(temp);

      解释：此时temp为临时对象，大小为0，arr与temp相交换，arr的缓冲区就变为0了。因为临时变量会被析构，所以占用的空间也被释放了。

Q：vector的容量过小后，是如何实现扩增容量的？

A：先按照一定的增长方式增加容量大小，重新分配一个符合该大小的vector，再将原本vector的数组拷贝进新的vector，再插入新的值。因为每一次重新分配vector和拷贝十分耗时，所以vector并不会在每次增加新数据时都重新分配，那么这就意味着我们需要定义一个比我们预期存储范围还大出一部分（这一部分用于可能的范围增长）的vector，这样就可以避免每次重新分配vector。

Q：在多线程时，对vector写时可能会出现什么错误？

A：程序崩溃，因为线程A vector进行写时，如果内存已满会重新申请内存，此时它的地址已经改变，而线程B依旧在写入/读入已经无效的地址，就会造成崩溃。

有两种解决办法：1.暴力解决法：直接给vector定义一个较大的内存，避免重新申请

                            2.加同步锁，每次写入前都锁住，执行完本次写入操作后，其他线程才能再次写入或读入。

所以！对容器的modify操作应该是原子性（一旦操作开始，到结束之前都不会切换到其他线程）的！

Q：我们使用sort算法时，传入容器的起始及结束。一般在没有特殊约束下，sort都是由小到大排列，那么如何让它由大到小排列？

A：sort还有另外一个函数，存在第三个形参，可以传入谓词。谓词有很多种，比如书上有写到的库定义的函数谓词对象，也就是std::greater<int>() ，将它作为第三个形参传入，就可以实现由大到小。还有很多种实现方式（函数谓词，函数指针谓词，函数对象谓词，lambda表达式）

Q：vector里的重要函数

A：push_back  pop_back  erase  clear  insert

Q：vector如何进行初始化

A：1.直接赋值

    vector<int> num(20,3）包含20个值为3的数

    2.使用数组进行遍历赋值

Q：vector如何访问元素

A：可以通过迭代器访问元素、下标访问、at(i)访问

Q：简要阐述一下deque

A：和vector类似，但是它可以在队列的首部和尾部添加或删除元素（push_front  pop_front），因为它内存管理比较复杂，所以执行速度慢于

Q：简要阐述一下list容器

A：适合频繁插入删除元素，但是查找比较复杂。除了和vector一样可以正向遍历之外，还能使用rbegin rend反向遍历，和deque一样的就是也含有push_front pop_front等

Q：映射容器map可以用两种方法插入，一种是insert，一种是下标运算符，插入有重复键值的数据时，它们的效果是否相同？

A：不相同，insert会插入失败，而下标运算符会覆盖以前重复键值对应的对象