STL序列式容器之vector

序列式容器

序列式容器：可序列叢集，其中的元素都可序，但未必有序。

vector概述

vector的資料安排以及操作方式，與array非常相似。兩者的唯一差别在于空間的運用的靈話性，array 是靜态空間，一旦配置了就不能改變；要換個大(或小)一點的房子，可以，一切瑣細得由用戶端自己來:首先配置一塊新空間， 然後将元素從舊址搬往新址， 再把原來的空間釋還給系統。 vector 是動态空間，随着元素的加人，它的内部機制會自行擴充空間以容納新元素。是以，vector 的運用對于記憶體的合理利用與運用的靈活性有很大的幫助，我們再也不必因為害怕空間不足而一開始就要求 一個大塊頭array 了，我們可以安心使用vector,吃多少用多少。

vector的實作技術，關鍵在于其對大小的控制以及重新配置時的資料移動效率.一旦vector舊有空間滿載，如果用戶端每新增一個元素，vector内部隻是擴充一個元素的空間，實為不智，因為所謂擴充空間(不論多大) .一如精早所說，是“配置新空間/資料移動,釋還舊空間”的大工程，時間成本很高，應該加入某種未雨綢缪的考慮。

vector定義源碼摘錄

// alloc是SGI STL的空間配置器
template <class T, class A11oc . alloc>
class vector {
public:
// vector的嵌套型别定義
typedef T  value_ type;
typedef value_ type* pointer;
typedef value_ type* iterator ;
typedef value_ type& reference;
typedef size_ .t  size_ type;
typedef ptrdiff_ _t  di fference_ type;
protected:
//以下，simple. allc是sGI STL的空間配置器
typedef simple_alloc<value_type,Alloc>data_allocator;
iterator start;//表示目前使用空間的頭
iterator finish;//表示目前使用空間的尾
iterator end_of_storage; //表示目前可用空間的尾
void insert_ aux(iterator position, const T& x) ;
void deallocate() 
{
      if (start)
      data_ ,allocator: :deallocate(start, end_ _of_ storage - startl;
}
void fill_ initialize(size_ type n, const T& value) 
{
      start = allocate_ ,and_ fill(n, value) ;finish = start + n;
      end_ of_ storage = finish;
}
public:
      iterator begin() {return start;}
      iterator end() { return finish;}
      size_ type size() const { return size_ .typelend() - begin());}
      size_ type capacity() const{ return size_ type(end_ of_ storage begin());}
      bool empty() const { return beginl) == end();}
      reference operator[](size_type n){ return *(begin() + n); }
      vector() : start(0), finish(0), end_ of_ storage(0) {}
      vector(size_ type n, const T& value) {fill_ initialize(n, value);}
      vector(int n, const T& value) { fill_ initialize(n, value); }
      vector(long n, const T& value) { fill_ initialize(n, value); }
      explicit vector(size_ .type n) { fill_ initialize(n, T()); }
      ~vector() {
      destroy (start, finish);
      deallocate();}
      reference front(){return *begin();}//第一個 元素
      reference back(){return *(end()-1);}//最後一個元素
      void push_back(const T& x)
      {
            if(finsh !=end_of_storage)
            {
                construct(finsh, x);
                ++finish;
            }
            else
               insert_aux(end(),x);
       }
       void pop_back()
       {
            --finish;
            destory(finish);
       }
       iterator erase(iterator position)
       {
         if(position+1!=end())//清除某位置上的元素
         {
            copy(position+1,finish,position);
         }
          --finish;//後續元素往前移動
          destory(finish);
          return position;
       }
       void resize(size_type new_ size, const T& x) 
       {
           if (new_ size < sizel)
               erase(beginl + new_ size, endll;
           else
               insert(endl), new_ size - sizel), x);
        }
       void resize(size_ _type new_ size) {resize(new_ size, TIl; }
       void clear() {erase(beginl), end(l);}
protected:
        //配置空間并填滿内容
       iterator allocate_ and_ fill(size_ type n, const T& x) 
       {
           iterator result = data_ allocator: :allocate(n) ;
           uninitialized_ fill_ n(result, n, x); 
           return result;
       }

           

vector的疊代器

vector 維護的是一個連續線性空間，是以不論其元素型别為何種，普通指針都可以作為vector的疊代器而滿足所有必要條件。

vector<int>::iterator ac;
vector<Shape>::iterator  ab;
//ac 的型别就是int*;ab的型别就是Shape*。
           

vector的資料結構

vector 所采用的的資料結構非常簡單：線性連續空間，它的兩個疊代器start和finish分别指向配置得來的連續空間中目前已使用的範圍，并以疊代器end_of_storage指向整塊連續的空間的尾端，如下圖所示：