stl-vector詳解

stl-vector是應用最廣泛的一種容器，類似於array，都將數據存儲於連續空間中，支持隨機訪問。相對於array，vector對空間應用十分方便、高效，迭代器使vector更加靈活、安全。設計皆由vector起，鍵盤之下盡vector。

1 vector本質

    vector數據結構如下，通過三個迭代器start, finish, end_of_storage的系列public接口，可很好地完成數據存儲、溢出判斷(iter >= iv.end())、大小、容量(容量與大小不等，以免不斷申請空間耗費資源)、重載操作符[]、判空、最前元素、最後元素等等。

 vector{

…

:

    iterator  start ; 

    iterator  finish; 

    iterator  end_of_storage;

:

    iterator  begin () {   start ; } 

    iterator  end() {   finish; } 

    size_type size()  {  size_type( end() - begin()); } 

    size_type capacity()  {  size_type(end_of_storage - begin()); } 

     empty ()  {  begin() == end(); } 

    reference [] (size_type n) {  *(begin() + n); } 

    reference front () {   *begin(); } 

…

}

    由於vector是用連續空間存儲數據，不斷擴容將導致大量的新空間申請、元素拷貝和釋放原有空間，十分耗時，vector申請空間時，都將多申請部分空間備用，如下圖的[finish, end_of_storage)所示。只有當finish == end_of_storage時，再申請新的空間(2*capacity()), 圖2就是在圖1的基礎上，再插入元素引起的空間變化時的數據存儲情景。