Boolan_C++面向对象高级编程(下)-第7周

通过学习，知道了C++的vector容器可以说是Array的一个高级抽象版本。我们知道C和C++里面的Array都是不能动态增加大小的，所以我们在编C程序的时候要么先预先设好一个大数组，要么在需要的时候再根据所需大小在堆上malloc，事后还要记得free。
我觉得C++的vector容器的好处就是它可以实现动态增长。vector一开始申明的时候会有个初始大小n。然后我们开始给vector添加新的元素，比如push_back()，慢慢的元素越来越多，初始vector空间不够用了，这时候再调用push_back()的话，其内部代码就会向内存管理系统索要大小为2n的内存空间。这期间用到了vector的allocator，其内部实际上也是调用的malloc()。当新的内存分配好了之后，原vector的内容会被拷贝到新的空间，也就是新的vector所指向的空间，并且原vector的内容会被清空。
这里有好几点需要注意： 1）vector空间不够用时，每次申请双倍的内存。当vector size很大时，可能会把系统内存耗尽，严重影响效率。 2）vector尺寸变大后，原vector的内容移动到新vector。这里会涉及到大量的拷贝构造函数和析构函数。因为每个元素会被拷贝到新空间，然后被清空。所以效率会很低。 2）对vector的操作如果导致空间重新配置，指向原vector的所有iterator就都失效*，因为iterator其实就是指针。
其实这个以2为底的指数增长是一种对可用空间试探性的探测，在工程应用中很多地方都会用到这种以2为底的指数增长（因为速度快嘛)，比如说TCP的拥塞控制机制里面，slow start过程一开始带宽也是以2为底的指数增长，直到遇到丢包或达到一个门限值带宽才开始线性增长。
不过这种以２为底数有个问题，那就是每次的新size会大于以前所有的size的和，比如说1->2->4->8， 那么8>1+2+4。 这样，以前分配的内存就不能重用了。
但是凡事皆有利弊。以２为底数也是有好处的，每次增长一倍，所以可以用的空间也比较多，下次再需要分配空间的可能性也就变小了。
事实上我个人觉得到底是用2还是1.5，跟本地操作系统的内存管理系统很有关系。比如说Linux的buddy system，其将所有的空闲Page(每个页大小 4KB )分组为11个块链表组，每个块链表分别包含大小为1，2，4，8，…，1024个连续的Page。内核会把内核大小为b的一对空闲Page合并为一个大小为2b的单独块，然后挂在对应大小为2b的块链表上。可以想象这种内存管理系统会很适合以2为底数的指数增长。