STL的vector容器的实现原理是什么,他是怎么扩容的?详细图解展示!!!

发布时间 2023-04-28 18:45:10作者: 潘阳399

实现原理:

  vector底层实现原理是一维数组。

  vector通过一个连续的数组存放元素,如果这个数组的容量已满,再插入数据的时候,就要去申请一块更大的内存,然后把原来数组的数据复制到新数组中来,再释放原来数组的内存。

  那么申请(扩容)多大的空间的比较合适呢?

    如果我们扩容的空间太小了,比如原来的数组的容量是10000个数据,我们只扩容了10001了,那么我们再插入数据的时候,又要去去扩容,进行多次复制和释放,那么效率太低。

    如果我们扩容的空间太大了,比如原来数组的容量是10000个元素,我们扩容了50000的空间,那么我们后面可能很少扩容了,但我们可能只需要插入很少的数据,那就太浪费空间了。

    所以综合效率和空间的有效利用,可以进行适当的扩容。比如vs中扩容是1.5倍,g++编译器的扩容是2倍。

    vs中是1.5倍:   

   在g++编译器中扩容是2倍: