stl-vector詳解，stlvector

stl-vector詳解，stlvector

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

1 vector本質

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

class vector{
…
protected:
    iterator  start ; 
    iterator  finish; 
    iterator  end_of_storage;
public:
    iterator  begin () { return  start ; } 
    iterator  end() { return  finish; } 
    size_type size() const { return size_type( end() - begin()); } 
    size_type capacity() const { return size_type(end_of_storage - begin()); } 
    bool empty () const { return begin() == end(); } 
    reference operator[] (size_type n) { return *(begin() + n); } 
    reference front () { return  *begin(); } 
…
}

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

圖1 vector數據存儲-1