vector的底层数据结构是动态数组,因此,vector的数据安排以及操作方式与std::array十很相似,它们间的唯一差别在于对空间的运用灵活性上。array为静态数组,有着静态数组最大的缺点:每次只能分配一定大小的存储空间,当有新元素插入时,要经历 “找到更大的内存空间”->“把数据复制到新空间” ->“销毁旧空间” 三部曲, 对于std::array而言,这种空间管理的任务压在使用它的用户身上,用户必须把握好数据的数量,尽量在第一次分配时就给数据分配合理的空间(这有时很难做到),以防止“三部曲”带来的代价,而数据溢出也是静态数组使用者需要注意的问题。而vector用户不需要亲自处理空间运用问题。vector是动态空间,随着新元素的插入,旧存储空间不够用时,vector内部机制会自行扩充空间以容纳新元素,当然,这种空间扩充大部分情况下(几乎是)也逃脱不了“三部曲”,只是不需要用户自己处理,而且vector处理得更加安全高效。vector的实现技术关键就在于对其大小的控制以及重新配置时数据移动效率。
迭代器类型对于C_style数组,我们使用普通指针就可以对数组进行各种操作。vector维护的是一个连续线性空间,与数组一样,所以无论其元素型别为何,普通指针都可以作为vector的迭代器而满足所有必要的条件。vector所需要的迭代器操作,包括operator*,operator->,operator++,operator--,operator+=,operator-=等,普通指针都具有。因此,普通指针即可满足vector对迭代器的需求。所以,vector提供了Random Access Iterators。
内存分配策略标准库的实现者使用了这样的内存分配策略:以最小的代价连续存储元素。为了使vector容器实现快速的内存分配,其实际分配的容量要比当前所需的空间多一些(预留空间),vector容器预留了这些额外的存储区用于存放添加的新元素,于是不必为每个新元素进行一次内存分配。当继续向容器中加入元素导致备用空间被用光(超过了容量 capacity),此时再加入元素时vector的内存管理机制便会扩充容量至两倍,如果两倍容量仍不足,就扩张至足够大的容量。容量扩张必须经历“重新配置、元素移动、释放原空间”这个浩大的工程。按照《STL源码剖析》中提供的vector源码,vector的内存配置原则为:
如果vector原大小为0,则配置1,也即一个元素的大小。
如果原大小不为0,则配置原大小的两倍。
当然,vector的每种实现都可以自由地选择自己的内存分配策略,分配多少内存取决于其实现方式,不同的库采用不同的分配策略。
迭代器失效问题vector管理的是连续的内存空间,在容器中插入(或删除)元素时,插入(或删除)点后面的所有元素都需要向后(或向前)移动一个位置,指向发生移动的元素的迭代器都失效。这里以插入操作示例:
随着元素的插入,原来分配的连续内存空间已经不够且无法在原地拓展新的内存空间,整个容器会被copy到另外一块内存上,此时指向原来容器元素的所有迭代器通通失效。
删除元素后,指向被删除元素的迭代器失效,这是显而易见的。
deque 底层数据结构vector是单向开口的线性连续空间,deque则是一种双向开口的连续数据空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作。当然vector也可以在头尾两端进行操作,但是其头部操作效果奇差,所以标准库没有为vector提供push_front或pop_front操作。与vector类似,deque支持元素的快速随机访问。deque的示意图如下:
现在问题来了:如果deque以数组来实现,如何做到在头部的常数时间插入?如果是采用链表来实现,又如何做到快速随机访问?deque的内部数据结构到底如何?想必你已经猜到了,要实现如上需求,需要由一段一段的连续空间链接起来的数据结构才能满足。
内存分配策略接着上面讲。deque由一段一段的连续空间所链接而成,一旦需要在deque的前端或尾端增加新空间,便配置一段定量的连续空间,并将该空间串接在deque的头部或尾部。deque复杂的迭代器架构,构建出了所有分段连续空间”整体连续“的假象。
既然deque是由一段一段定长的连续空间所构成,就需要有结构来管理这些连续空间。deque采用一块map(非STL中的map)作为主控,map是一块小的连续空间,其中每个元素都是指针,指向一块较大的线性连续空间,称为缓冲区。而缓冲区才是存储deque元素的空间主体。示例图:
map本身也是一块固定大小的连续空间,当缓冲区数量增多,map容不下更多的指针时,deque会寻找一块新的空间来作为map。
deque的迭代器