概述

舍友面试时候遇到的一个有意思的问题，面试官问，如果一个vector我们push了10000个元素进去，然后pop出来9000个，那么它的容量是多少？如何消除多余的容量？

分析

首先，容量大小这个问题，大家一般都知道vector在push元素的时候，如果容量不足以支撑这次的size增加，那么会扩充成原来的两倍，但是缩减的时候呢，如果size降低到了当前的1 / 2，那么会把capacity降低到一半吗？

答案是否定的。最近有点忙，不太有时间仔细看这部分源码，不过实验是表明capacity不会降低的，并且也可以从这几个方面推测不会降低容量的原因：

  1. 如果用户reserve了vector的容量，然后再pop一部分元素，这时候如果把capacity降低了，那么用户reserve这个行为产生了意义模糊。
  2. 不方便扩展，因为vector的内存管理并不是直接在vector里面定义的，而是有专门的allocator。
  3. 极端情况下效率降低。

那么回到刚才这个问题，很容易出现两个错误答案：

  1. 容量是1024 * 16 = 16384.
  2. 可以用reserve来降低容量。

首先容量不会真的是16384，不过是个差不多的数字，这个原因是在size本身就很大的情况下按照两倍分配可能会浪费太多的空间，到后面就不是一直两倍来分配了。

其次，reserve是不能用来降低容量的，这一点可以通过简单的实验就可以证明。

正确答案我想有两种：

  1. 调用vector的shrink_to_fit成员函数。
  2. 假设我们有一个vector<int> v，那么调用vector<int>(v).swap(v)即可。

可行性通过简单的实验就能得证，不过这里有一个问题，这两种方法效率是一样的吗？

首先，第二种方法肯定是出现了剩余所有元素的复制的，而第一种方法则是让我们看看这个函数的源码（在Windows下，MSVC编译器）：

    _CONSTEXPR20 void shrink_to_fit() { // reduce capacity to size, provide strong guarantee
        auto& _My_data         = _Mypair._Myval2;
        const pointer _Oldlast = _My_data._Mylast;
        if (_Oldlast != _My_data._Myend) { // something to do
            const pointer _Oldfirst = _My_data._Myfirst;
            if (_Oldfirst == _Oldlast) {
                _Tidy();
            } else {
                _Reallocate_exactly(static_cast<size_type>(_Oldlast - _Oldfirst));
            }
        }
    }

咱不得不说，STL这源码真不是给碳基生物看的东西，不过其核心就是最内层的if-else，意思是说，如果size已经是0了，那么全部内存清空，如果size不是0，那么就按照这个size分配合适大小的空间。

那么_Reallocate_exactly这个函数到底做了什么呢？其源码如下：

    _CONSTEXPR20 void _Reallocate_exactly(const size_type _Newcapacity) {
        // set capacity to _Newcapacity (without geometric growth), provide strong guarantee
        auto& _Al         = _Getal();
        auto& _My_data    = _Mypair._Myval2;
        pointer& _Myfirst = _My_data._Myfirst;
        pointer& _Mylast  = _My_data._Mylast;

        const auto _Size = static_cast<size_type>(_Mylast - _Myfirst);

        const pointer _Newvec = _Al.allocate(_Newcapacity);

        _TRY_BEGIN
        if constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {
            _Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);
        } else {
            _Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);
        }
        _CATCH_ALL
        _Al.deallocate(_Newvec, _Newcapacity);
        _RERAISE;
        _CATCH_END

        _Change_array(_Newvec, _Size, _Newcapacity);
    }

最近实在没时间再深入去看，不过大概可以看出，有这样三个步骤：

  1. 内存分配：第10行的const pointer _Newvec = _Al.allocate(_Newcapacity);。
  2. 内存拷贝：第13-17行。
  3. 数组重定位：第23行的_Change_array(_Newvec, _Size, _Newcapacity);。

这个过程应该是，先分配一个合适大小的空间，把现有vector元素拷贝过去，然后使现有vector指向这片新内存作为自己的存储空间，然后释放原本的内存。

那么据此推断，前面说的两种做法效率是基本一致的，下面用简单的实验证明：

#include <chrono>
#include <iostream>
#include <vector>

using namespace std;
using namespace chrono;

int main() {
  vector<int> t;
  for (int i = 0; i < 100000; i++) t.push_back(999);
  for (int i = 0; i < 9000; i++) t.pop_back();
  auto start = system_clock::now();
  //   vector<int>(t).swap(t);  // way 2
  t.shrink_to_fit();  // way 1
  auto end = system_clock::now();
  auto duration = duration_cast<nanoseconds>(end - start);
  cout << static_cast<double>(duration.count()) << endl;
}

在Ubuntu20.04和gcc9.3下编译运行，两种方式时间相差不会超过10%，可以验证结论，这两种方式时间复杂度和实现上的耗时基本一样。