如何避免vector动态扩容？

        vector的扩容机制：当向vector插入元素时，如果元素的有效个数和空间容量相等时，vector内部会自动触发扩容机制，而扩容主要分3步骤：开辟新空间，拷贝元素，释放旧空间。
但是每次扩容时，新空间的开辟不能太大，也不能太小，太大容易造成空间的浪费，太小了则会导致扩容频繁而影响程序的运行效率。
        那既然扩容会影响程序的运行效率，那我们如何来避免呢？
        在插入元素之前，我们可以预估vector里面要存储多少个元素，我们提前将这个空间给它开辟好就可以了！！！
        比如说，我们需要向vector中插入100个元素，在执行push_back之前，我们进行reserver预留空间，只要空间大小给的足够，在整个插入的过程中就不需要进行任何的扩容！
如果没有进行reserver预留空间，那么程序的运行结果相比执行了reserver的结果是会有很大的差别，造成边插入边扩容的情况，导致程序的运行效率极其低下！！！

        我们查看到，在Windows的VS系列编译器下，是按照1.5倍的方式进行扩容，在Linux的g++中，是按照2倍的方式进行扩容的。
都是以倍数的方式来进行扩容，为什么要选择以倍数的方式进行扩容？

        那接下来我们以等长个数的方式和倍数的方式，这2种方式进行对比：

        对于等长个数的分布方式：也就是说，新空间的大小将为原空间大小加上一个固定的长度。
也就是说：新空间的大小：capacity+k
        那如果我们向vector中插入100个元素，假如说k的值是10，我们总共需要扩容10次。而每次扩容都需要将旧空间中的元素一个一个搬移到新的空间中。
        第i次扩容，需要搬移的元素的个数就是下图中的ki：

        因为第一次我们实际上有10个大小的空间，此时新空间大小就是20个，扩容期间我们需要将旧空间中的10个元素拷贝到新的空间中。第二次扩容时，旧空间大小是20，新空间大小是30，那么我们就需要将旧空间中的20个元素一个一个拷贝到新空间中。
那么假设元素插入和元素搬移为一个单位的操作，则n个元素在它push_back期间，所需要的总的操作数就是上图中的表达式，也是下图中的表达式：

        该表达式：n表示的是n个元素它在插入时所耗费的总的操作。
        k+2k+3k+…+n/k *k，表示每次扩容我们需要搬移元素的操作，也就是搬移元素的总的操作数，然后我们对式子进行化简。然后进行均摊。
平均时间复杂度是O(N)

        如果是按倍数的方式进行扩容：

        假如我们有n个元素向vector中插入，倍增因子是m，在n个元素的插入期间，总共需要扩容log以m为底的n次，假如是，我们现在有1000个元素需要向vector中进行插入，而倍增因子是2，那么总共需要扩容的次数是：log以2为底的1000，来一个向上取整，也就是算出来是10，总共需要扩容10次。

        同理，第i次扩容期间，我们的空间里已经有mi个元素，具体需要将这么多元素搬到新空间中去，因此n次push_back它所耗费的总的操作数是n+m^ 1+m^ 2+…+m^ log以m为底的n
同样的，n表示n个元素在它插入期间所耗费的总的次数，m^ 1+m^ 2+…+m^ log以m为底的n表示：等比数列，算出结果，代表n个元素以等比方式扩容所需要耗费的总操作数，然后进行均摊，单个元素所耗费的总的操作数就是表达式/n，因为m是常量，所以时间复杂度是O(1)

        所以，以倍数的方式扩容比以等长的方式扩容效率要高得高。