C   STL/ (3) vector

本節我們主要講一下幾個部分:

  • vector容器的基本概念

    • 什麼是vector容器
    • vector容器的功能
    • vector容器的實現原理
  • vector容器常用API

    • vector容器建構函式
    • vector賦值
    • vector元素存取
    • vector大小
    • vector插入刪除
    • vector的swap方法及小技巧

  • 什麼是vector?
    vector是一個單口容器。vector相當於一個動態的陣列,可以向其中新增元素而不需要考慮是否超出陣列的容量。

  • vector的功能
    用一張圖表示:
    vector

  • vector實現原理
    我們知道vector可以實現記憶體自動增長。那這是怎麼實現的呢?
    例如:我們現在有一個vector容量為100,存100個資料。現在第101個資料push進來了,這時候發生的什麼讓vector仍然正常的執行呢?
    過程如下:

    • 新建一個vector,容量為原來的1-2倍之間。一般為1.5倍。
    • 將舊記憶體空間的值copy到新記憶體空間中,並將新增的元素push進新的vector中。
    • 銷燬原來的vector

    我們可以通過判斷vector的首地址來判斷是否生成了新的vector。
    跟這一實現原理密切相關的是vector大小。我們在後面會詳細敘述這一部分。


  • vector常用API

    • vector建構函式

      vector<int> v1;    //預設建構函式
      vector<int> v2(10,1);    //帶引數的建構函式
      vector<int> v3(v2);    //拷貝建構函式
      vector<int> v4(v2.begin(),v2.end()); 
      vector<int> v5=v2;    //過載運算子=
    • vector賦值

      vector<int> v1,v3,v4;
      vector<int> v2(10,1);
      v1.assign(v2.begin(),v2.end());
      v3.assign(10,1);
      v4=v2;
      
    • vector 元素存取

      vector<int> v1(10,1);
      for(int i=0;i<v1.size();i  ){
      cout<<v1[i]<<endl;
      }
      for(int i=0;i<v1.size();i  ){
      cout<<v1.at(i)<<endl;
      }
      cout<<v1.front()<<endl;
      cout<<v1.back()<<endl;
    • vector大小

      //描述vector大小主要有一下幾種方法
      vector<int> v1(10,1);
      cout<<v1.size()<<endl;    //size方法輸出vector中元素的個數
      cout<<v1.capacity()<<endl;    //capacity方法輸出vector的可用記憶體空間個數
      if(v1.empty()){    //empty方法判斷容器是否為空
      cout<<"v1 is empty"<<endl;
      }
      else{
      cout<<"v1 is not empty"<<endl;
      }
      v1.resize(5);    //resize方法重定義容器可用空間個數
      for(int i=0;i<v1.size();i  ){
      cout<<v1.at(i)<<" ";
      }
      cout<<endl;
      //reserve方法的功能
      vector<int> v2,v3;
      int *p=NULL;
      int *q=NULL;
      int count_p=0;
      int count_q=0;
      v2.reserve(100000);
      v2.push_back(0);
      v3.push_back(0);
      p=&v2[0];
      q=&v3[0];
      for(int i=1;i<100000;i  ){
      v2.push_back(i);
      v3.push_back(i);
      if(p!=&v2[0]){
      count_p  ;
      p=&v2[0];
      }
      if(q!=&v3[0]){
      count_q  ;
      q=&v3[0];
      }
      }
      cout<<"allocate memory "<<count_p<<" times "<<v2.size()<<" "<<v2.capacity()<<endl;
      cout<<"allocate memory "<<count_q<<" times "<<v3.size()<<" "<<v3.capacity()<<endl;
      //總結:reserve方法和resize方法的不同在於,resize是對已有的容器進行操作,改變容器的大小。如果有多餘元素,則捨去;如果不足,則填充0,或其他指定資料。而reserve常用在初始化容器,通過reserve一次性分配一個較大的記憶體空間,避免反覆開闢記憶體空間,從而節省時間。
    • vector 插入刪除
      vector增的方法:

      • push_back();
      • insert(const_iterator,target);
      • insert(const_iterator,num,target);
    • vector刪的方法:

      • pop_back();
      • erase(const_iterator start,const_iterator end);
      • erase(const_iterator pos);
      • clear();
      vector<int> v11;
      v11.push_back(10);
      v11.push_back(20);
      v11.push_back(30);
      for(int i=0;i<v11.size();i  ){
      cout<<v11.at(i)<<" ";
      }
      cout<<endl;
      v11.insert(v11.begin(),1);
      v11.insert(v11.end(),2,9);  //const_iterator start , num ,ele
      for(int i=0;i<v11.size();i  ){
      cout<<v11.at(i)<<" ";
      }
      cout<<endl;
      cout<<"pop out"<<v11.at(v11.size()-1)<<endl;
      v11.pop_back();
      cout<<"pop out"<<v11.at(v11.size()-1)<<endl;
      v11.pop_back();
      cout<<"pop out"<<v11.at(v11.size()-1)<<endl;
      v11.pop_back();
      for(int i=0;i<v11.size();i  ){
      cout<<v11.at(i)<<" ";
      }
      cout<<endl;
      v11.erase(v11.begin(),v11.begin() 2);//在STL演算法中,只要接收兩個迭代器,均為左閉右開。
      for(int i=0;i<v11.size();i  ){
      cout<<v11.at(i)<<" ";
      }
      cout<<endl; 
      v11.clear();    //清空
      for(int i=0;i<v11.size();i  ){
      cout<<v11.at(i)<<" ";
      }
      cout<<endl;
      
    • vector swap使用技巧
          vector<int> v22;
      int *pp=NULL;
      int count_pp=0;
      v22.reserve(100000);
      v22.push_back(0);
      pp=&v22[0];
      for(int i=1;i<100000;i  ){
      v22.push_back(i);
      if(pp!=&v22[0]){
      count_pp  ;
      pp=&v22[0];
      }
      }
      cout<<"allocate memory "<<count_pp<<" times "<<v22.size()<<" "<<v22.capacity()<<endl;
      //這裡我們發現size 和capacity不相等,這就導致了記憶體的浪費,我們能不能通過某種方法讓capacity變的和size一樣大呢?
      vector<int> (v22).swap(v22);//使用匿名物件,用過即毀。
      cout<<"v22.size: "<<v22.size()<<" v22.capacity: "<<v22.capacity()<<endl;
      

  • 容器中即能儲存標準資料型別變數,也能儲存物件和指標。
    我們在stl介紹中寫過相關程式碼,這裡就不重複寫了。