STL中vector的实现原理

STL中vector的实现原理

vector的数据安排以及操作方式&＃xff0c;与array非常相似。两者的唯一区别在于空间的运用的灵活性。array是静态空间&＃xff0c;一旦配置了就不能改变&＃xff1b;要换个大&＃xff08;或小&＃xff09;一点的房子&＃xff0c;可以&＃xff0c;一切琐细都得由客户端自己来&＃xff1a;首先配置一块新空间&＃xff0c;然后将元素从旧址一一搬往新址&＃xff0c;再把原来的空间释还给系统。vector是动态空间&＃xff0c;随着元素的加入&＃xff0c;它的内部机制会自行扩充空间以容纳新元素。因此&＃xff0c;vector的运用对于内存的合理利用与运用的灵活性有很大的帮助&＃xff0c;我们再也不必因为害怕空间不足而一开始要求一个大块头的array了&＃xff0c;我们可以安心使用array&＃xff0c;吃多少用多少。

vector的实现技术&＃xff0c;关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧有空间满载&＃xff0c;如果客户端每新增一个元素&＃xff0c;vector的内部只是扩充一个元素的空间&＃xff0c;实为不智。因为所谓扩充空间&＃xff08;不论多大&＃xff09;&＃xff0c;一如稍早所说&＃xff0c;是” 配置新空间/数据移动/释还旧空间 “的大工程&＃xff0c;时间成本很高&＃xff0c;应该加入某种未雨绸缪的考虑。稍后我们便可看到SGI vector的空间配置策略了。

另外&＃xff0c;由于 vector维护的是一个连续线性空间&＃xff0c;所以vector支持随机存取 。

注意&＃xff1a;vector动态增加大小时&＃xff0c;并不是在原空间之后持续新空间&＃xff08;因为无法保证原空间之后尚有可供配置的空间&＃xff09;&＃xff0c;而是以原大小的两倍另外配置一块较大的空间&＃xff0c;然后将原内容拷贝过来&＃xff0c;然后才开始在原内容之后构造新元素&＃xff0c;并释放原空间。因此&＃xff0c; 对vector的任何操作&＃xff0c;一旦引起空间重新配置&＃xff0c;指向原vector的所有迭代器就都失效了 。这是程序员易犯的一个错误&＃xff0c;务需小心。